[자료구조] 양방향 연결리스트

1. 양방향 연결리스트

[자료구조] 단방향 연결리스트

단방향 연결리스트의 노드들에 next 뿐만 아니라 앞의 노드도 표시해주는 prev도 포함한다.

양방향이기 때문에 더 많은 메모리가 사용된다.

하지만 그만큼 제거, 삽입 할때 이전과 다음 노드를 알고 있으니 단방향 연결리스트보다 빠르게 처리 할 수 있다.

2. 양방향 연결리스트 클래스

(1) 클래스 및 노드

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;
  }
}

(2) push

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

(3) pop

pop() {
    if (!this.head) return undefined;
    let removed = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      let tailNode = removed.prev;
      tailNode.next = null;
      this.tail = tailNode;
      removed.prev = null;
    }
    this.length--;
    return removed;
  }

(4) shift

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;
  }

(5) unshift

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

(6) get

get(index) {
    if (index < 0 || index >= this.length) return null;
    let 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;
  }

(7) set

set(index, val) {
    if (index < 0 || index >= this.length) return false;
    let foundNode = get(index);
    foundNode.val = val;
    return true;
  }

(8) insert

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);
    let newNode = new Node(val);
    let nextNode = get(index);
    let prevNode = nextNode.prev;
    (prevNode.next = newNode), (newNode.prev = prevNode);
    (newNode.next = nextNode), (nextNode.prev = newNode);
    this.length++;
    return true;
  }

(9) 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 removed = this.get(index);
    let prevNode = removed.prev;
    let nextNode = removed.next;
    (prevNode.next = nextNode), (nextNode.prev = prevNode);
    (removed.next = null), (removed.prev = null);
    this.length--;
    return removed;
  }

3. 양방향 연결리스트 빅O

insertion(삽입)	removal(제거)	searching(탐색)	access(접근)
O(1)	O(1)	O(n)	O(n)

4. 단방향 연결리스트와 비교

단방향 연결리스트는 prev가 없기 때문에 get메소드를 구현할때 처음부터 탐색을 시작해야 한다.

하지만 양방향 연결리스트는 tail에서 prev를 통해 탐색도 할수 있으므로 인덱스에 따라 처음이나 끝부터 탐색을 할수 있다.

시간적으로는 양방향 연결리스트가 유리할 수 있지만 더 많은 메모리를 차지한다는 단점이 있다.