이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가리키는 자료구조입니다. 양방향 탐색이 가능해 삽입과 삭제가 유연하다는 장점이 있습니다. 이번 글에서는 자바스크립트로 이중 연결 리스트를 직접 구현해 보겠습니다.
먼저 생성자에서 head(첫 번째 노드)와 tail(마지막 노드)을 null로 초기화하는 간단한 클래스를 정의하는 것부터 시작합니다. 그리고 DoublyLinkedList 클래스의 프로토타입에 연결 리스트의 각 노드를 나타내는 별도의 Node 구조체도 함께 정의합니다.
예제: 기본 클래스와 노드 구조 정의
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
LinkedList.prototype.Node = class {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
};위 코드에서 LinkedList 클래스는 리스트의 시작점(head), 끝점(tail), 그리고 현재 길이(length)를 관리합니다. 프로토타입에 정의된 Node 클래스는 저장할 데이터(data)와 앞뒤 노드를 가리키는 포인터(next, prev)를 가집니다.
리스트 출력(display) 함수 만들기
리스트가 어떻게 구성되어 있는지 눈으로 확인할 수 있도록 display 함수도 함께 만들어 보겠습니다. 이 함수는 다음과 같은 순서로 동작합니다.
- 리스트의 head부터 순회를 시작합니다.
- currElem = currElem.next를 통해 노드를 하나씩 이동하며 리스트를 순회하고, currElem이 null이 되면(즉, 리스트의 끝에 도달하면) 반복을 종료합니다.
- 매 반복마다 현재 노드의 데이터를 출력합니다.
다음은 그 동작 과정을 나타낸 그림입니다.
그럼 위에서 설명한 로직이 실제로 어떻게 구현되는지 코드로 살펴보겠습니다.
예제: display 함수 구현
display() {
let currNode = this.head;
while (currNode != null) {
console.log(currNode.data + " -> ");
currNode = currNode.next;
}
}display 함수는 head에서 출발해 next 포인터를 따라 마지막 노드까지 이동하면서 각 노드의 데이터를 콘솔에 출력합니다. currNode가 null이 되는 순간, 즉 더 이상 다음 노드가 없으면 while 루프가 자동으로 종료됩니다. 이처럼 head와 next 포인터만 활용하면 이중 연결 리스트를 손쉽게 처음부터 끝까지 순회할 수 있습니다.