[자료구조] 이중 연결 리스트(Doubly Linked List) 개념, 메소드, 시간복잡도

이중 연결 리스트

• 단일 연결 리스트와 다르게 prev, next를 pointer로 모두 연결
• 삽입/삭제에서 상수 시간 복잡도 O(N)을 가지나, 포인터를 하나 더 추가하므로 메모리를 더 잡아먹는 단점이 있음

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
뒤에서 Node를 추가하는 메소드
길이가 0일 경우 그냥 newNode를 head와 tail로 지정,
그 외의 경우 tail의 next를 newNode로 지정하고 newNode의 prev를 현재의 tail로 지정한 후 tail을 newNode로 지정 */
  push(val) {
    var newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  /* POP
뒤에서 Node를 제거하는 메소드
길이가 0일 경우 그냥 head와 tail을 null로 지정,
그 외의 경우 현재 tail을 제거할 노드의 prev로 지정, 현재 tail의 next를 null로 지정, 제거할 node의 prev를 null로 지정해서 모든 연결관계를 끊음 */

  pop() {
    if (!this.head) return undefined;
    var 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;
  }

/* SHIFT
앞에서 노드를 제거하는 메소드
현재 head를 제거할 노드로 지정하고, 새로운 head로 현재 노드의 next를 삽입
그 뒤 두 노드의 prev, next를 연결관계를 모두 끊음 */

  shift() {
    if (this.lenth === 0) return undefined;
    var 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;
  }

/* UNSHIFT
앞에서 노드를 삽입하는 메소드
현재 head의 prev를 newNode로 연결, newNode의 next를 현재 헤드로 연결한 후
새로운 head로 newNode 지정 */

  unshift(val) {
    var newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

/* GET
Index에 있는 node를 search하는 메소드
분할점령법으로 haed와 가까운 index, tail과 가까운 index인지에 따라 접근법이 달라짐*/

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

/* SET
지정한 Index에 새로운 value를 넣는 메소드
get 메소드를 이용해 node 위치를 찾고, 그 node value로 새로운 value를 넣고 boolean 반환 */

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

  /* INSERT
위치를 나타내는 인덱스와 값을 입력, 노드를 하나 만들어서 해당 위치에 추가
가장 큰 차이점은 처음부터 시작하는 게 아닌, 인덱스에 따라서 최적화를 함
boolean 반환 */

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

    var newNode = newNode(val);
    var beforeNode = this.get(index - 1);
    var afterNode = beforeNode.next;

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

  /*   REMOVE
  인덱스, 값을 입력하면 그것을 삭제해줌
  get을 이용해서 특정 위치가 head에 가까운지, tail에 가까운지 확인
  index가 0이면 shift 이용, index가 list.length-1와 같으면 pop 이용
  두 경우가 아니라면 get method 이용, 해당 노드의 prev와 next를 null로 세팅
  리스트 길이를 -1하고 해당 노드를 출력 */

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

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

    (beforeNode.next = removedNode.next), (afterNode.prev = removedNode.prev);
    (removedNode.next = null), (removedNode.prev = null);

    this.length--;
    return removedNode;
  }
}

단일 연결 리스트와의 비교

• Insertion : O(1) - 단일연결리스트와 동일
• Removal : O(1) - 단일연결리스트와 다름(O(N)). 단일 연결 리스트의 경우 맨 끝에서 노드를 제거하는 경우 전체 리스트를 돌면서 뒤에서 두번째 요소에 접근해서 그것을 새로운 테일로 만들어야 했음. 그러나 Double의 경우 .prev 하면 되기 때문에 빠름.
• Seraching : O(N) - 정확히 말하면 분할점령법을 사용해서 O(N/2)이지만, 크게 보면 O(N)
• Access : O(N)

이중 연결리스트 Recap

• 이전 노드를 가리키는 prev pointer가 있다는 점을 제외하면 단일연결리스트와 동일
• 실제로 방문 페이지를 확인할 때 많이 쓰임
• 뭔가를 찾을 때 단일연결리스트보다 절반의 시간이 걸림 (분할점령법 사용하기 때문)
• 하지만 pointer를 하나 더 추가하기 때문에 메모리를 더 소모함