이중 연결 리스트(Doubly Linked List)는 각 노드가 데이터(data), 이전 노드 참조(prev), 다음 노드 참조(next) 세 가지 요소로 구성되는 선형 자료구조입니다. 단일 연결 리스트와 달리 양방향 탐색이 가능하기 때문에 앞뒤 어느 방향으로든 순회할 수 있으며, 특정 위치에서의 삽입과 삭제가 더 유연하다는 장점이 있습니다.
DoublyLinkedList 클래스 전체 구현
아래는 head(머리), tail(꼬리), length(길이) 세 가지 속성을 관리하는 자바스크립트 이중 연결 리스트 클래스의 완전한 구현 예제입니다.
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
insert(data, position = this.length) {
let node = new this.Node(data);
// 리스트가 비어 있는 경우
if (this.head === null) {
this.head = node;
this.tail = node;
this.length++;
return this.head;
}
// 맨 앞(head)에 삽입하는 경우
if (position == 0) {
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
return this.head;
}
let iter = 1;
let currNode = this.head;
while (currNode.next != null && iter < position) {
currNode = currNode.next; iter++;
}
// 새 노드가 리스트의 다음 노드를 가리키도록 설정
node.next = currNode.next;
// 다음 노드의 prev가 새 노드를 가리키도록 설정
if (currNode.next != null) {
currNode.next.prev = node;
}
// 새 노드가 이전 노드를 가리키도록 설정
node.prev = currNode;
// 이전 노드의 next가 새 노드를 가리키도록 설정
currNode.next = node;
// 삽입된 위치가 꼬리(tail)라면 tail을 갱신
if (this.tail.next != null) {
this.tail = this.tail.next;
}
this.length++;
return node;
}
remove(data, position = 0) {
if (this.length === 0) {
console.log("List is already empty");
return;
}
this.length--;
let currNode = this.head;
if (position <= 0) {
this.head = this.head.next;
this.head.prev = null;
} else if (position >= this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
let iter = 0;
while (iter < position) {
currNode = currNode.next;
iter++;
}
currNode.next = currNode.next.next;
currNode.next.prev = currNode;
}
return currNode;
}
display() {
let currNode = this.head;
while (currNode != null) {
console.log(currNode.data + " <-> ");
currNode = currNode.next;
}
}
}
DoublyLinkedList.prototype.Node = class {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
};주요 메서드 동작 원리
1. insert() — 노드 삽입
insert() 메서드는 데이터와 삽입 위치(position)를 인자로 받습니다. 기본값은 리스트의 맨 끝이며, 다음과 같은 경우를 나누어 처리합니다.
- 빈 리스트인 경우: 새 노드가 head이자 tail이 됩니다.
- 맨 앞 삽입(position = 0): 기존 head의 prev가 새 노드를 가리키도록 한 뒤 head를 교체합니다.
- 중간 또는 끝 삽입: position까지 순회한 뒤, 앞뒤 노드의 참조(prev/next)를 모두 재설정하여 연결을 유지합니다. 삽입 위치가 기존 tail 뒤라면 tail 포인터도 갱신됩니다.
2. remove() — 노드 삭제
remove() 메서드는 지정한 위치의 노드를 제거하고 길이를 1 감소시킵니다. 빈 리스트에서 호출되면 경고 메시지를 출력합니다.
- 첫 번째 노드 삭제: head를 다음 노드로 이동하고 새 head의 prev를 null로 만듭니다.
- 마지막 노드 삭제: tail을 이전 노드로 이동하고 새 tail의 next를 null로 만듭니다.
- 중간 노드 삭제: 해당 위치까지 순회한 후, 이전 노드와 다음 노드를 직접 연결하여 대상 노드를 리스트에서 분리합니다.
3. display() — 리스트 출력
display() 메서드는 head부터 시작해 next 참조를 따라가며 각 노드의 데이터를 콘솔에 순서대로 출력합니다. 리스트 전체를 확인할 때 유용하게 사용할 수 있습니다.
4. Node 내부 클래스
각 노드는 DoublyLinkedList.prototype.Node로 정의된 클래스를 통해 생성되며, 저장할 data와 함께 next, prev 참조를 null로 초기화합니다. 프로토타입에 정의함으로써 리스트 클래스 내부에서 this.Node 형태로 깔끔하게 접근할 수 있습니다.
정리
이처럼 이중 연결 리스트는 prev와 next 두 개의 포인터를 유지하는 대신, 양방향 순회와 효율적인 삽입·삭제가 가능합니다. 위 구현은 head와 tail을 함께 관리하므로 맨 앞과 맨 뒤에서의 작업을 O(1) 시간 복잡도로 처리할 수 있다는 점이 핵심 장점입니다.