이중 연결 리스트(Doubly linked list)

• 이중 연결 리스트는 앞에서 살펴본 단일 연결 리스트에서 이전의 노드를 가리키는 포인터를 하나 더하는 것 뿐이다. 그러니까 각각의 노드에 포인터 가 두 개씩 있게 된다.
• 이중 연결 리스트는 이처럼 반대 방향 포인터도 갖게 되어 성능상 유연함을 갖게 됐지만, 더 많은 메모리가 필요하게 됐다.

기본 구조

• 이중 연결 리스트의 constructor는 단일 연결 리스트의 것과 같다.

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

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

Push 메서드

  push(val) {
    // 인수로 전달된 값으로 새 노드를 만든다.
    const newNode = new Node(val);
    // 길이가 0이면, 새 노드를 head와 tail로 정한다.
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
      // 길이가 0이 아니라면, tail의 next 포인터가 새 노드를 가리키게 하고,
      // 새 노드의 prev 포인터는 tail을 가리키게 하고,
      // 마지막으로 tail은 이제 새 노드가 되도록 지정한다.   
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

Pop 메서드

  pop() {
    // 만약 head가 없으면(=길이가 0이면) undefined를 반환한다.
    if (!this.head) return undefined;
    // poppedNode 변수가 tail을 가리키게 한다.
    const poppedNode = this.tail;
    // 길이가 1이면, head와 tail 모두 null이 된다.(pop됐으니)
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
      // 길이가 2이상이면, poppedNode의 prev(마지막에서 두 번째) 노드가 tail이 되도록 하고, 
      // tail의 next 포인터는 null로 재할당하고,
      // poppedNode의 prev 포인터도 null로 재할당하여 연결을 끊는다. 
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      poppedNode.prev = null;
    }
    this.length--;
    return poppedNode;
  }

Shift 메서드

  shift() {
    // 길이가 0이면, undefined를 반환한다.
    if (this.length === 0) return undefined;
    // oldHead 변수가 head를 가리키게 한다.
    const oldHead = this.head;
    // 길이가 1이면, shift될 경우 길이가 0이 되므로 head와 tail에 모두 null을 할당한다. 
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
      // 길이가 2이상 이면, oldHead의 next(앞에서 두 번째) 노드가 head가 되도록 하고,
      // head의 prev 포인터는 null로 재할당하고,
      // oldHead의 next 포인터도 null로 재할당하여 연결을 끊는다. 
    } else {
      this.head = oldHead.next;
      this.head.prev = null;
      oldHead.next = null;
    }
    this.length--;
    return oldHead;
  }

Unshift 메서드

  unshift(val) {
    // 인수로 받은 val로 새 노드를 만든다.
    const newNode = new Node(val);
    // 길이가 0이면, head와 tail에 모두 새 노드를 할당한다.
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
      // 길이가 1 이상 이면, head의 prev 포인터가 새로 추가된 노드를 가리키게 하고,
      // 새 노드의 nex 포인터는 head를 가리키게 하고,
      // 이제 새 노드가 head가 되도록 만든다.
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

Get 메서드

• 연결 리스트에서 위치를 통해 노드를 반환받는다.
  • 효율적으로 루프롤 돌기 위해, 찾는 index가 해당 리스트의 중앙을 기준으로 어디에 있는지 확인하고, 그 결과에 따라 앞에서부터 루프를 시작할지, 뒤에서부터 루프를 시작할지 결정한다.

  get(index) {
    // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index >= this.length) return null;
    let count; // 루프를 돌면서 인덱스를 카운팅한다.
    let current; // current 변수를 나중에 return한다.
    // 입력된 인덱스가 리스트의 앞 부분에 있으면 
    if (index <= this.length / 2) {
      count = 0;
      current = this.head;
      // head부터 시작해서 정방향으로 루프를 돈다.
      while (count !== index) {
        current = current.next;
        count++;
      }
      // 입력된 인덱스가 리스트의 뒤 부분에 있으면,
    } else {
      count = this.length - 1;
      current = this.tail;
      // tail부터 시작해서 역방향으로 루프를 돈다.
      while (count !== index) {
        current = current.prev;
        count--;
      }
    }
    return current;
  }

Set 메서드

• 연결 리스트에서 특정 위치의 노드의 값를 변경한다.
  • 위에서 만든 get 메서드를 사용한다.
  • 단일 연결 리스트에서 해당 메서드 로직과 동일하다.

  set(index, val) {
    // get 메서드를 사용하여 foundNode가 해당 인덱스의 노드를 가리키도록 한다.
    const foundNode = this.get(index);
    // 입력된 값을 foundNode의 val에 재할당하고 true를 반환한다.
    if (foundNode != null) {
      foundNode.val = val;
      return true;
    }
    // 입력된 index에 노드가 없으면 false 반환
    return false;
  }

Insert 메서드

• 연결 리스트의 특정 위치에 노드를 삽입한다.

  insert(index, val) {
    // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index > this.length) return false;
    // 입력된 인덱스가 길이와 같다면, push 메서드 사용하고 형 변환을 통해 true를 반환한다.
    if (index === this.length) return !!this.push(val);
    // 입력된 인덱스가 0이라면, unshift 메서드 사용하고 형 변환을 통해 true를 반환한다.
    if (index === 0) return !!this.unshift(val);

    const newNode = new Node(val);
    // 새로 삽입될 노드의 이전에 위치할 노드는 get 메서드를 사용해서 index-1 노드를 가져온다.
    const beforeNode = this.get(index - 1);
    // 새로 삽입될 노드의 다음에 위치할 노드는 beforeNode의 next를 통해 가져온다. 
    const afterNode = beforeNode.next;
		
    // beforeNode의 next 포인터가 새 노드를 가리키게 하고, 
    // 새 노드의 prev 포인터는 beforeNode를 가리키게 한다.
    (beforeNode.next = newNode), (newNode.prev = beforeNode);
    // 새 노드의 next 포인터가 afterNode를 가리키게 하고,
    // afterNode의 prev 포인터는 새 노드를 가리키게 한다.
    (newNode.next = afterNode), (afterNode.prev = newNode);
    this.length++;
    return true;
  }

Remove 메서드

• 연결 리스트에서 특정 위치에 있는 노드를 삭제한다.

remove(index) {
  // 입력된 인덱스가 유효한지 체크한다.
    if (index < 0 || index > this.length) return undefined;
  // 입력된 인덱스가 0이면 shift 메서드를 사용한다.
    if (index === 0) return this.shift();
  // 입력된 인덱스가 끝 인덱스와 같다면 pop 메서드를 사용한다.
    if (index === this.length - 1) return this.pop();

    const removedNode = this.get(index);
  // 삭제할 노드의 이전 노드의 next 포인터가 삭제할 노드의 next 노드를 가리키게 한다.
    removedNode.prev.next = removedNode.next;
  // 삭제할 노드의 다음 노드의 prev 포인터가 삭제할 노드의 prev 노드를 가리키게 한다.
    removedNode.next.prev = removedNode.prev;

  // 삭제할 노드의 next 포인터와 prev 포인터를 모두 null로 재할당하여, 연결을 끊는다.
    removedNode.next = null;
    removedNode.prev = null;
    this.length--;
    return removedNode;
  }
}

• 위 코드에서 헷갈리는 부분은 아마 이 부분일 텐데, 변수로 할당해서 단순화할 수 있다.

    removedNode.prev.next = removedNode.next;
// 위 코드는 아래의 두 줄 코드와 같다. 		
		const beforeNode = removedNode.prev;
    beforeNode.next = afterNode;

--------------------------------------------------------------------

    removedNode.next.prev = removedNode.prev;
// 위 코드도 아래의 두 줄 코드와 같다.
    const afterNode = removedNode.next;
    afterNode.prev = beforeNode;

Reverse 메서드

• 이중 연결 리스트의 reverse 메서드는 head와 tail을 바꾸고, 모든 노드의 next 포인터와 prev 포인터 방향을 뒤집음로써, 리스트 자체를 뒤집는다.

reverse() {
  // 반복문에서 사용할 node를 저장한다.
    let node = this.head;
  // head와 tail을 바꾼다.
    this.head = this.tail;
    this.tail = node;

  // next 포인터 방향 뒤집기
    let next; // 임시 저장 변수
    let prev = null; // 첫 번째로 뒤집히는 node(tail이 되므로)의 next는 null이다.
    for (let i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }

  // prev 포인터 방향 뒤집기
    next = null;  // 첫 번째로 뒤집히는 node(head가 되므로)의 prev는 null이다.
    node = this.head; // 반복문에서 사용할 tail node를 저장한다
  //(위에서 head와 tail이 뒤집혔으므로 this.head는 사실상 원래 tail이었다.)
    for (let i = 0; i < this.length; i++) {
      prev = node.prev;
      node.prev = next;
      next = node;
      node = prev;
    }
  }

• reverse 메서드 실행 결과 확인
  • 이 메서드는 강의에서 알려주지 않아서, 그냥 혼자 만들어 본 것이므로 정확하지 않을 수도 있는 점을 참고해주세요.

const list = new DoublyLinkedList();
list.push(5).push(10).push(15).push(20);
console.log(list);
/* 
DoublyLinkedList {
  head: <ref *1> Node {
    val: 5,
    next: Node { val: 10, next: [Node], prev: [Circular *1] },
    prev: null
  },
  tail: <ref *2> Node {
    val: 20,
    next: null,
    prev: Node { val: 15, next: [Circular *2], prev: [Node] }
  },
  length: 4
}
 */

list.reverse();
console.log(list);

/* 
DoublyLinkedList {
  head: <ref *1> Node {
    val: 20,
    next: Node { val: 15, next: [Node], prev: [Circular *1] },
    prev: null
  },
  tail: <ref *2> Node {
    val: 5,
    next: null,
    prev: Node { val: 10, next: [Circular *2], prev: [Node] }
  },
  length: 4
} 
*/

이중 연결 리스트의 성능

시간복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
  • 정확하게는 탐색의 시간복잡도는 O(N/2)이나, Big O에 의하면 여전히 O(N)이다.
• 접근 : O(N)

결론

• 이중 연결 리스트는 이전 노드를 향하는 포인터가 추가됐다는 점만 빼면 단일 연겨 리스트와 거의 비슷하다.
• 노드를 찾을 때는 이중 연결 리스트가 단일 연결리스트보다 시간을 절반으로 줄일 수 있으므로 더 낫다. 이 외의 이중 연결 리스트의 시간복잡도는 단일 연결 리스트의 성능과 같다.
• 하지만, 이중 연결 리스트는 추가 포인터 때문에 더 많은 메모리가 필요하다는 점이 단점이다.