이중 연결 리스트는 각 항목이 이전 항목을 가리키는 포인터와 다음 항목을 가리키는 포인터를 갖는 데이터 구조이다. 이를 통해 리스트의 양쪽 끝에서도 항목을 삽입, 삭제, 검색하는 과정을 효율적으로 수행할 수 있다.

이중 연결 리스트의 구조

이중 연결 리스트의 각 노드(Node)는 데이터와 이전 노드를 가리키는 포인터(prev) 그리고 다음 노드를 가리키는 포인터(next)로 구성된다.

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

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

이중 연결 리스트의 기본 작업

1. 삽입:
   • 삽입 시에는 이전 노드의 next 포인터와 다음 노드의 prev 포인터를 업데이트한다.
2. 삭제:
   • 삭제 시에는 삭제할 노드의 이전 노드와 다음 노드를 직접 연결하여 사이 간격을 없앤다.
3. 검색:
   • 검색 시에는 처음부터 혹은 끝부터 이동하며 해당 데이터를 찾거나, 인덱스를 통해 효율적으로 검색할 수 있다.

정리

이중 연결 리스트는 삽입, 삭제, 검색 등의 작업을 효율적으로 수행할 수 있는 데이터 구조이다. 많은 언어에서 내장된 자료구조로 제공되며, 많은 알고리즘과 문제 해결에 활용될 수 있다.

참고 문헌:

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT press.