단일 연결 리스트

Junho Yun·2022년 11월 16일
알고리즘
0

알고리즘

목록 보기
15/18
post-thumbnail

단일 연결 리스트 소개

  • 단방향 연결 리스트가 무엇인가?
  • 내장 어레이 구조와의 비교
  • 많은 메소드와 기능을 추가해보겠습니다.

단방향 연결 리스트가 무엇인가요?

데이터를 저장하는 자료구조의 한 예입니다.

각각의 엘리먼트를 "노드"라고 부릅니다.
각 노드에는 문자열이나 숫자와 같은 데이터가 저장되어 있습니다.
또한 노드에는 다음 노드를 가리키는 정보도 저장되어 있습니다.
만약 다음 노드가 없다면 "null"을 저장하게 됩니다.

  • 헤드 : 맨 앞, 연결 리스트의 시작 노드
  • 테일 : 맨 뒤, 연결 리스틔의 마지막 노드
  • 길이 : 노드의 개수

단방향 연결 리스트는 헤드 노드가 어디있는지만 알고 있습니다.
만약 위의 그림에서 값 8에 접근을 하기 위해서는 헤드노드 -> 다음노드 -> 다음노드(8)
이런식으로 접근을 해야합니다.

(마치 엘리베이터 없는 고층 빌딩과 같습니다 5층가려면 1층부터 2,3,4 층 모두 들려야하죠)

배열하고 뭐가 다른거죠?

Lists

  • 인덱스를 갖고 있지 않습니다. 대신 헤드 포인터는 무조건 갖고 있습니다 (테일은 선택적)

  • 각 노드는 next 포인터를 통해 연결되어 있습니다.

  • 랜덤하게 접근이 불가능합니다. 순차적으로 접근해야하죠

  • 장점은 삽입과 제거를 쉽게 할 수 있습니다.

    Arrays

  • 정렬된 인덱스를 갖고있습니다.

  • 삽입과 제거가 어려울 수 있습니다. (0번에 삽입하면 뒤에 값들의 인덱스가 다 변경되죠)

  • 특정 인덱스에 쉽게 접근이 가능합니다.

코드 스타터

// piece of data - val
//reference to next node - next

class Node{
constructor(val){
this.val = val;
this.next = null;
}
}

class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(val){

}

}

// var first = new Node("Hi")
// first.next = new Node("there")
// first.next.next = new Node("how")
// first.next.next.next = new Node("are")
// first.next.next.next.next = new Node("you")

var list = new SinglyLinkedList()
list.push("HELLO")
list.push("GOODBYE")

위의 코드는 기본 뼈대가 되는 코드 입니다. 이제 여기다가 각종 기능을 추가해보도록하겠습니다.

push

push 메소드 소개

가장 마지막에 새로운 노드를 생성해주는 메소드 입니다.

의사코드

  • 입력할 값을 받아들입니다.
  • 해당 값을 이용해서 새로운 노드를 만듭니다.
  • 만약 헤드가 없다 -> 리스트가 비어있다는 것, 이때는 헤드와 테일 모두 새롭게 생성된 노드를 가르키도록 합니다.
  • 만약 헤드가 있다, 마지막 노드의 next를 새롭게 생선된 노드를 가르키도록 합니다. 그리고 테일도 새롭게 생성된 노드를 가르키도록 해야합니다.
  • 마지막으로 리스트의 길이 값을 +1 해줍니다.
  • 이렇게 완성된 리스트를 반환합니다.

push 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}

var list = new SinglyLinkedList()
// list.push("HELLO")
// list.push("GOODBYE")

pop

pop 메소드 소개

가장 마지막 노드를 제거하는 메소드 입니다.

간단할 것 같지만 쉽지 않습니다. 왜냐하면 마지막 노드를 제거한 후 테일로 부터 전 노드를 바로 알아낼 수 없기 때문입니다

의사 코드

  • 만약 노드가 없다면, undefined을 반환 합니다.
  • 노드가 있을 경우 "테일"을 찾을 때 까지 루프를 돌려줍니다.
  • 마지막에서 두번째 노드의 next를 null로 설정해 줍니다.
  • 그리고 마지막에서 두번째 노드를 테일로 설정해 줍니다.
  • 길이를 -1 해주고,
  • 제거한 노드를 반환합니다 (새로운 변수가 필요)

pop 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;

    }
}


var list = new SinglyLinkedList()
list.push("HELLO") 
list.push("GOODBYE")
list.push("!")

shift

shift 메소드 소개

맨 앞 (헤드)에 있는 노드를 제거하고 두번째에 있는 노드에 헤드를 가리키도록 합니다.

  • 노드 없으면, undefined 반환
  • 해드 값을 반환할 변수에 저장해 줍니다.
  • 2번째 노드를 헤드가 가리키도록 합니다.
  • 길이값을 -1
  • 변수에 저장했던 초기 헤드값을 반환 합니다.

shift 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
}


var list = new SinglyLinkedList()
list.push("HELLO") 
list.push("GOODBYE") 
list.push("!")

unshift

unshift 메소드 소개

리스트 맨 앞 (헤드)에 새로운 노드를 추가 합니다.

  1. 값을 받습니다
  2. 받은 값을 활용해서 새로운 노드를 생성합니다
  3. 값을 받았을때 헤드가 없다면, 받을 값을 헤드와 테일로 지정합니다.
  4. 이미 노드가 있을 경우, 새롭게 생선된 노드의 NEXT를 현재의 헤드 값으로 설정하고, 헤드를 새롭게 생성된 노드를 가르키도록 합니다.
  5. 리스트 길이를 +1
  6. 연결 리스트를 반환 합니다

unshift 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

var list = new SinglyLinkedList()
list.push("HELLO") 
list.push("GOODBYE") 
list.push("!")

get

get 메소드 소개

주어진 위치에 있는 노드를 반환하는 메소드
만약 0을 주면 헤드노드를 반환하겠죠

  1. index 로 사용할 값을 받습니다.
  2. 받은 값이 0보다 작거나, 리스트의 길이보다 길다면 -> null을 반환합니다
  3. index값으로 받은 숫자 만큼 이동한 다음 해당 위치에 있는 노드를 반환합니다.

get 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
}

var list = new SinglyLinkedList()

list.push("HELLO")  
list.push("GOODBYE") 
list.push("!") 
list.push("<3")
list.push(":)")

set

set 메소드 소개

인덱스와 업데이트할 값을 받아서 해당 인덱스의 노드 값을 업데이트 해주는 메소드
인덱스 0, 값 9 을 받는다면 헤드 노드의 값을 9로 변경 해줍니다.

  1. 업데이트할 값과 수정할 index 값을 받아야합니다 (총 2개의 값)
  2. get 메소드를 이용해서 특정 노드를 찾습니다.
  3. get 메소드로 해당 노드를 찾을 수 없다면, false를 반환해줍니다.
  4. 만약 노드를 찾는다면, 받은 값으로 해당 노드에 업데이트해줍니다.

set 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
}

var list = new SinglyLinkedList()

list.push("HELLO")  
list.push("GOODBYE") 
list.push("!") 
list.push("<3")
list.push(":)")

insert

insert 메소드 소개

인덱스와 값을 받아서, 해당 위치에 새로운 노드를 만들어 줍니다.

  1. 인덱스로 받은 값이 0보다 작거나 리스트의 길이보다 길면, false 반환
  2. 만약 인덱스로 받은 값이 리스트의 길이와 같다면 이미 정의된 push() 메소드를 호출
  3. 마찬가지로 인덱스로 받은 값이 0 -> unshift() 메소드 호출
  4. 인덱스로 받은 값이 1이상 리스트 길이 이하 일 경우 get()을 호출합니다.
    대신에 get(인덱스로 받은 값 - 1)
  5. 해당 위치에 새로운 노드를 만들고 이전 노드의 next와 새로 만든 노드의 next를 각각 다음 노드로 지정해줍니다.
  6. 길이를 +1
  7. return true

insert 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
}

var list = new SinglyLinkedList()

list.push(100)
list.push(201)
list.push(250)
list.push(350)

remove

remove 메소드 소개

인덱스를 받아서 해당 위치에 있는 노드를 제거하고 주위에 있는 노드들을 연결해줍니다.

  1. 인덱스로 받은 값이 0보다 작거나, 리스트의 길이보다 길다면 -> undefined 반환합니다
  2. 인덱스로 받은 값 == 리스트의 길이 -1 일 때, pop()
  3. 인덱스로 받은 값 == 0 일 때, shift()
  4. 나머지 경우 get() 메소드를 이용해서 인덱스-1 위치에 있는 노드를 찾습니다.
  5. 제거할 위치 이전에 있는 노드의 next를 해당 위치 이후에 있는 노드로 연결해 줍니다.
  6. 리스트의 길이 - 1
  7. 제거된 노드의 값을 반환 합니다.

remove 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }
}

var list = new SinglyLinkedList()

list.push(100)
list.push(201)
list.push(250)
list.push(350)

reverse

reverse 메소드 소개

면접 주요 질문 중 하나 입니다.
리스트의 위치를 역으로 하는 메소드 입니다.
(테일 -> 헤드 / 헤드 -> 테일)

  1. 해드와 테일을 서로 교환합니다.
  2. next라는 변수를 생성합니다.
  3. prev라는 변수를 생성합니다.
  4. node라는 변수를 만들고 현재의 헤드 값으로 초기화 합니다.
  5. 리스트 전체를 루프로 돌면서
  6. 현재 node의 next를 node의 next.next 로 설정하는 작업을 반복
  7. 현재 node의 next를 이전에 바로 앞에 있던 node를 가리키도록 설정
  8. 마지막으로 현재의 node 값을 prev에 저장하고 node 변수에 .next값을 저장합니다.

reverse 메소드 솔루션

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }
    reverse(){
      var node = this.head;
      this.head = this.tail;
      this.tail = node;
      var next;
      var prev = null;
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;
    }
    print(){
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
        console.log(arr);
    }
}

var list = new SinglyLinkedList()

list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)

단일 연결 리스트 빅오 복잡도

  • Insertion = O(1)
  • Removal = O(1) or O(N)
  • Searching - O(N)
  • Access - O(N)

위와 같이 특정 상황에서 좋은 성능을 보입니다.
맨앞이나 맨뒤를 추가 및 삭제할 때 좋은 성능입니다.
따라서 위와 같은 상황이 많을 때 사용하면 좋은 자료구조라고 할 수 있습니다.

RECAP

  • 맨 앞이나 맨 뒤에서 제거와 삽입이 많은 상황에서 좋은 구조입니다. 임의의 접근은 단일 연결 리스트에게는 단점입니다.
  • 배열은 인덱스를 갖고 있지만, 리스트는 인덱스가 없고 노드 간의 연결참조를 이용하는 구조입니다.
  • 왜 이걸 사용하냐에 있어서, 추후에 스택이나 큐 같은 자료구조를 이해하기에 도움이 되기 때문입니다.
profile
Junho Yun
의미 없는 코드는 없다.
이전 포스트

자료구조

다음 포스트

17. 스택 (Stack) - 알고리즘

0개의 댓글