Doubly linked list

앞서 알아본 linked list는 singly linked list 이고 이번에 알아볼 linked list는 Doubly linked list이다.

singly linked list 와 다르게 1개의 pointer가 더 있고 이 pointer는 이전 값을 가르킨다.
그래서 insert와 같은 동작을 뒤에서부터 시작할 수 있다.

시간 복잡도

prepend, append => O(1)
lookup, insert, delete => O(n)

시간복잡도는 singly linked list와 같다. 하지만 그보다 빠르다.

BUT

pointer가 1개 더 있는만큼 메모리를 더 많이 차지해서 메모리가 더 필요하다.

Doubly linked list code

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null,
      prev: null
    };
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = {
      value: value,
      next: null,
      prev: null
    }
    newNode.prev = this.tail
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  prepend(value) {
    const newNode = {
      value: value,
      next: null,
      prev: null
    }
    newNode.next = this.head;
    this.head.prev = newNode
    this.head = newNode;
    this.length++;
    return this;
  }
  insert(index, value){
    //Check for proper parameters;
    if(index >= this.length) {
      return this.append(value);
    }
    
    const newNode = {
      value: value,
      next: null,
      prev: null
    }
    const leader = this.traverseToIndex(index-1);
    const follower = leader.next;
    leader.next = newNode;
    newNode.prev = leader;
    newNode.next = follower;
    follower.prev = newNode;
    this.length++;
    console.log(this)
    return this.printList();
  }
  traverseToIndex(index) {
    //Check parameters
    let counter = 0;
    let currentNode = this.head;
    while(counter !== index){
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
}

Single vs Double linked list

Single

Pros

Double보다 만들기 쉽다. 메모리가 적게 든다. 메모리가 적게 들기에 delete, insert의 동작이 더 빠르다.

cons

reverse 나 뒤에서 앞으로 traverse 하는 동작이 안되기에 pointer를 잃으면 메모리를 영영 잃게 된다.

적은 메모리를 사용하거나 delete , insert 를 빨리하고 싶을 때,
특히 List 앞에 insert 하고 싶을 때 쓰면 좋다.

Double

Pros

양방향으로 list를 탐색 가능하다. delete를 하고 싶을 때 굳이 앞에서부터 찾지 않아도 된다.

cons

메모리가 더 필요하고 single 보다 복잡하다. delete, insert 에 필요한 추가 동작들이 있다.

메모리에 크게 구애받지 않는 환경에서 사용하기 좋다.
앞으로든 뒤로든 value를 찾고 싶을 때 쓰면 좋다.

참고
Udemy " Master the Coding Interview: Data Structures + Algorithms " - Zero To Mastery