DoublyLinkedList

DoublyLinkedList

Diagram

• SinglyLinkedList와 비슷하지만 단방향이 아닌 양방향으로 참조하는 자료구조
• 양쪽 끝 노드들은 Null을 가리키고 있다.

Operation

• push(value)
  • 맨 끝에 node 추가
• pop()
  • 맨 끝 node 제거
• unshift(value)
  • 맨 앞에 node 추가
• shift()
  • 맨 앞 node 제거
• get(index)
  • index에 위치한 노드 조회
• set(index, value)
  • index에 위치한 node의 value를 변경
• insert(index, value)
  • index 위치에 node를 삽입
• remove(index)
  • index에 위치한 node 제거

Purpose

• 데이터의 추가/삽입 및 삭제가 용이
• 검색의 경우 처음 요소부터 탐색을 해야하므로 검색 속도가 느림
• 검색을 자주 하면 배열이 유리
• 추가/삭제가 많으면 연결 리스트가 유리

검색을 하기 위해선 처음 혹은 끝에서부터 검색을 해야 하기 때문에 O(n)

추가/ 삭제는 해당 index에 위치한 node 혹은 해당 node 양 옆에 위치한 node의 포인터만 변경을 해주면 된다. 하지만 결국 검색(get)을 통해 추가/삭제하므로 O(n). 다만 양 쪽 끝 index에 추가/삭제 시 O(1)

Implement

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

class DoublyLinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = newNode;
    this.length = 1;
  }

  push(value) {
    const newNode = new Node(value);
    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;
  }

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

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

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

  get(index) {
    if (index < 0 || index >= this.length) return undefined;
    let temp = this.head;
    if (index < this.length / 2) {
      for (let i = 0; i < index; i++) {
        temp = temp.next;
      }
    } else {
      temp = this.tail;
      for (let i = this.length - 1; i > index; i--) {
        temp = temp.prev;
      }
    }
    return temp;
  }

  set(index, value) {
    let temp = this.get(index);
    if (temp) {
      temp.value = value;
      return true;
    }
    return false;
  }

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

    const newNode = new Node(value);
    const before = this.get(index - 1);
    const after = before.next;

    before.next = newNode;
    newNode.prev = before;
    newNode.next = after;
    after.prev = newNode;

    this.length++;
    return true;
  }

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

    const temp = this.get(index);
    temp.prev.next = temp.next;
    temp.next.prev = temp.prev;
    temp.next = null;
    temp.prev = null;
    return temp;
  }
}

const myDoublyLinkedList = new DoublyLinkedList(1);
myDoublyLinkedList.push(2);

console.log(myDoublyLinkedList);