(TIL Day03-02)자료구조-연결 리스트(2) 양방향 연결 리스트

Doubly Linked List

• 양방향으로 이어지는 연결 리스트.
• Singly Linked List보다 메모리 크기가 조금 더 크다.(이전 노드를 가리키는 메모리가 있어야 하기 때문이다!)

  

데이터 추가

31을 6과 2 사이에 추가해보자.

1. 우선 새롭게 만든 31의 다음 노드를 6의 다음 노드인 2로 연결한다.
2. 2의 이전 노드는 31을 가리키도록 한다.
3. 6의 다음 노드를 31로 연결한다.
4. 31의 이전 노드를 6으로 연결한다.

단방향 연결 리스트보다 복잡하게 느껴지겠지만, 이해한다면 쉽게 다룰 수 있다!

 

데이터 삭제

6을 지웠을 경우다.

1. 31의 이전 노드를 6의 이전 노드인 1을 가리키도록 한다.
2. 1의 다음 노드를 31로 바꾼다.
3. 6을 삭제한다.

 

코드

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

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

  find(value) {
    let currentNode = this.head;

    while (currentNode !== null && currentNode.value != value) {
      currentNode = currentNode.next;
    }

    if (currentNode === null) {
      console.log(`FindError...Can't find the value : ${value}`);
    }

    return currentNode;
  }

  append(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
      newNode.prev = this.tail;
    }
    this.size++;
  }

  insert(node, value) {
    if (node === null) {
      return;
    }

    const newNode = new Node(value);

    node.next.prev = newNode;
    newNode.prev = node;
    newNode.next = node.next;
    node.next = newNode;
    this.size++;
  }

  remove(value) {
    let prevNode = this.head;

    while (prevNode.next !== null && prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
      this.size--;
    } else {
      console.log(`RmoveError...Can't find the value : ${value}`);
    }
  }

  display() {
    let currentNode = this.head;
    let displayString = "[";

    while (currentNode !== null) {
      displayString += `${currentNode.value}, `;
      currentNode = currentNode.next;
    }

    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }

  getSize() {
    console.log(this.size);
  }
}

const dll = new DoublyLinkedList();
dll.append(1);
dll.append(6);
dll.append(2);
dll.append(8);
dll.display();
dll.insert(dll.find(6), 31);
dll.display();
dll.remove(6);
dll.display();

실행 결과