[자료구조]양방향(이중) 연결 리스트

목표

• 양방향 연결 리스트의 정의
• 단방향 연결 리시트와 비교하기
• 양방향 연결 리스트의 기본적인 기능 구현하기

✅ 양방향(이중) 연결 리스트(Doubly Linked List)란?

노드가 이중으로 즉, 양방향으로 연결되어 있는 리스트를 말한다. 단일 리스트와 달리 포인터가 추가되므로 메모리가 더 사용 된다. 

구현

기본적인 뼈대

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

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.lenght = 0;
    }
}

prev 속성이 추가되었다.

🟢 1. Push

리스트의 맨 뒤에 노드를 추가한다.

• 값을 가지는 새 노드를 만든다.
• head 속성이 null이라면, head와 tail을 새 노드로 설정한다.
• 현재 tail의 next 속성을 새 노드로 설정한다.
• 새 노드의 prev 속성을 이전 tail로 설정한다. 
• tail 속성을 새 노드로 설정해준다.

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

🟢 2. Pop

리스트의 맨 뒤 노드를 제거한다.

• head가 없다면, undefined 반환
• 현재 tail을 나중에 반환할 수 있도록 변수에 저장해둔다.
• 리스트의 길이가 1이라면, head와 tail을 null로 설정한다.
• tail을 이전 tail의 prev 노드로 업데이트 한다.
• 새 tail의 next 속성을 null로 설정한다. 
• 길이 1 감소.
• 제거한 노드를 반환한다.

class DoublyLinkedList {
    constructor() {
	  // ...
    }
    pop() {
        if(!this.head) return undefined;
        let poppedNode = this.tail;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
}

🟢 3. Shift

리스트의 맨 앞의 노드를 제거한다.

• 길이가 0이면, undefeind 반환
• (old head라고 부르는)변수에 현재 head 속성을 저장한다.
• 길이가 1이라면, head와 tail속성을 null로 설정
• old head의 next를 현재 head로 업데이트 한다. 
• 현재 head의 prev를 null로 설정
• old head의 next를 null로 설정하여 포인터를 끊어줌.
• 길이 1 감소

class DoublyLinkedList {
    constructor() {
      //...
    }
    shift() {
        if(!this.head) return undefined;
        let oldHead = this.head;
        if(this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = oldHead.next;
            this.head.prev = null;
            oldHead.next = null
        }
        this.length--;
        return oldHead;
    }
}

🟢 4. UnShift

리스트의 맨 앞에 새로운 노드를 추가한다.

• 값을 받아서 새로운 노드를 생성한다.
• 길이가 0이라면, head와 tail을 새 노드로 설정한다.
• 그게 아니라면, 현재 head의 prev 값을 새 노드로 설정한다.
• 새 노드의 next 속성을 이전 head로 설정한다.
• head를 새 노드로 업데이트 한다.
• 길이를 1 증가, list 반환

class DoublyLinkedList {
    constructor() {
      //...
    }
    unshift(val) {
        let newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

🟢 5. Get

리스트의 해당 위치에 있는 노드에 접근할 수 있다. index를 받아서 해당 인덱스 위치에 있는 노드를 받아온다. 양방향 연결 이기 때문에 뒤에서 접근할 수 있고 앞에서 접근할 수 있다. 그러므로 최적화된 루트로 접근할 수 있는 이점이 존재한다.

• index가 유효한지 확인한다. 음수이거나 리스트의 길이와 같거나 클 때, null 반환
• index가 리스트의 절반보다 작거나 같으면, loop를 head에서부터 middle까지 반복하여, 찾은 노드를 반환한다.
• index가 리스트의 절반보다 크다면,  loop를 tail에서부터 middle까지 반복하여, 찾은 노드를 반환한다.

class DoublyLinkedList {
    constructor() {
      //...
    }
    get(index) {
        if(index < 0 || index >= this.length) return null;
        let count, cur;
        if(index <= this.length / 2) {
            count = 0;
            cur = this.head;
            while (count !== index) {
                cur = cur.next
                count++;
            }
        } else {
            count = this.length - 1
            cur = this.tail
            while (count !== index) {
                cur = cur.prev
                count--;
            }
        }
        return cur;
    }
}

🟢 6. Set

특정 위치의 node 값을 변경한다.

• get 메서드를 통해 얻은 결과를 변수에 담는다. 
• 해당 노드의 값을 우리가 입력한 값으로 바꾼 후 true를 반환한다.
• 아니라면 false 

set(index, val) {
    let foundNode = this.get(index);
    if(foundNode != null) {
        foundNode.val = val;
        return true
    }
    return false;
}

🟢 7. Insert

특정 위치에 노드를 추가한다.

• 인덱스가 유효한지 확인한다. 틀리면 false
• 인덱스가 0이면, unshift
• 인덱스가 list의 길이와 같다면, push
• get을 사용해서 삽입하려고하는 값 이전에 오는 값(index - 1)에 접근해야 한다.
• next와 prev 속성을 이용해서 노드들을 올바르게 연결한다. 
• 길이 1 증가
• true 반환

insert(index, val) {
    if(index < 0 || index > this.length) return false;
    if(index === 0) return !!this.unshift(val);
    if(this.length === index) return !!this.push(val);

    let newNode = new Node(val);
    let beforeNode = this.get(index-1);
    let afterNode = beforeNode.next;

    beforeNode.next = newNode, newNode.prev = beforeNode;
    newNode.next = afterNode, afterNode.prev = newNode;
    this.length++;
    return true
}

🟢 8. Remove

특정 위치의 노드를 제거한다.

remove(index) {
    if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length -1) return this.pop();

    let removedNode = this.get(index);
    let beforeNode = removedNode.prev;
    let afterNode = removedNode.next;

    beforeNode.next = afterNode;
    afterNode.prev = beforeNode;
      // removedNode.prev.next = removedNode.next;
      // removedNode.next.prev = removedNode.prev;

    removedNode.next = null;
    removedNode.prev = null;
    this.length--;
    return removedNode;
}

🤔 Big O of Doubly Linked Lists

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

technically searching is O(N/2), but that's still O(N)

 

👊 정리

• 이중 연결 리스트는 이전 노드에 대한 포인터가 있다는 점을 제외하고는 단일 연결 리스트와 거의 동일하다.
• 노드를 찾는 데 단일 연결 리스트보다 뛰어나고, 절반의 시간 내에 완료할 수 있다.
• 그러나, 추가로 만든 포인터를 고려하면 메모리를 더 많이 차지한다.