Doubly Linked List#
Doubly Linked List는 노드들이 양방향으로 연결된 선형 데이터 구조로, 각 노드가 데이터와 이전 노드, 다음 노드를 가리키는 포인터를 포함하고 있다.
Doubly Linked List는 각 노드가 데이터와 두 개의 링크 필드를 가지고 있는 있으며, 이 두 개의 링크는 이전 노드(previous node)와 다음 노드(next node)를 가리킨다.
이러한 구조로 인해 리스트의 양방향 순회가 가능해진다.
과 끝(테일)을 모두 가리키는 포인터를 유지한다.
- 순환 구조: 마지막 노드의 다음 노드는 첫 번째 노드를, 첫 번째 노드의 이전 노드는 마지막 노드를 가리킬 수 있다.
- 양방향 탐색: 리스트를 앞뒤로 탐색할 수 있어 효율적인 검색이 가능하다.
- 삽입과 삭제의 효율성: 노드의 삽입과 삭제가 O(1) 시간 복잡도로 수행된다.
- 리스트 끝에서의 연산: 테일 포인터를 통해 리스트의 마지막 요소에 즉시 접근할 수 있다.
- 메모리 사용량 증가: 각 노드가 두 개의 포인터를 저장해야 하므로 메모리 사용량이 증가한다.
- 구현의 복잡성: 단일 연결 리스트에 비해 구현이 더 복잡하다.
- 삽입과 삭제 시 포인터 조작: 노드 삽입과 삭제 시 여러 포인터를 조작해야 한다.
- 웹 브라우저의 앞으로/뒤로 탐색 기능
- 음악 플레이어의 재생 목록
- 운영 체제의 작업 스케줄링
- 캐시 구현
- 복잡한 데이터 구조(예: 그래프)의 기본 구성 요소
동작 원리#
- 삽입: 새 노드를 생성하고 이전 노드와 다음 노드의 포인터를 적절히 조정한다.
- 삭제: 삭제할 노드의 이전 노드와 다음 노드를 서로 연결하고 해당 노드를 메모리에서 해제한다.
- 탐색: 헤드나 테일에서 시작하여 원하는 노드를 찾을 때까지 포인터를 따라 이동한다.
구성 요소#
- 노드: 데이터와 이전/다음 노드를 가리키는 두 개의 포인터로 구성된다.
- 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다.
- 테일 포인터: 리스트의 마지막 노드를 가리킨다.
구현 방식#
JavaScript를 사용한 Doubly Linked List 구현 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| 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;
}
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
prepend(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
delete(data) {
let current = this.head;
while (current) {
if (current.data === data) {
if (current === this.head && current === this.tail) {
this.head = null;
this.tail = null;
} else if (current === this.head) {
this.head = this.head.next;
this.head.prev = null;
} else if (current === this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.size--;
return true;
}
current = current.next;
}
return false;
}
print() {
let current = this.head;
let result = [];
while (current) {
result.push(current.data);
current = current.next;
}
console.log(result.join(' <-> '));
}
}
// 사용 예시
const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print(); // 출력: 0 <-> 1 <-> 2 <-> 3
list.delete(2);
list.print(); // 출력: 0 <-> 1 <-> 3
|
참고 및 출처#