double-linked-circular-list

说明

双向循环链表

源码

用法

doubleLinkedCircularList.test.ts
1
import { DoubleLinkedCircularList } from "../../utility/algorithm/double-linked-circular-list";
2
import { ListNode } from "../../utility/algorithm/double-linked-circular-list/list-node";
3
4
// ? Double Linked Circular List
5
describe('DLCL', () => {
6
test('dlcl1.handleGetHead should return the `head` of linked-list', () => {
7
const dlcl1 = new DoubleLinkedCircularList<number>({
8
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
9
});
10
11
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
12
const head = dlcl1.handleGetHead();
13
const tail = dlcl1.handleGetTail();
14
15
// ? 正向遍历
16
let current: ListNode<number> | null = head;
17
let count: number = 0;
18
while (current && current !== tail) {
19
expect(current.value).toBe(expected[count]);
20
21
count++;
22
current = current.next;
23
}
24
if (current) {
25
expect(current.value).toBe(expected[count]);
26
// ? 重置
27
current = tail;
28
count = expected.length - 1;
29
}
30
31
// ? 反向遍历
32
while (current && current !== head) {
33
expect(current.value).toBe(expected[count]);
34
35
count--;
36
current = current.prev;
37
}
38
if (current) {
39
expect(current.value).toBe(expected[count]);
40
}
41
});
42
43
test('dlcl1.handleGetTail should return the `tail` of linked-list', () => {
44
const dlcl1 = new DoubleLinkedCircularList<number>({
45
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
46
});
47
48
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
49
const tail = dlcl1.handleGetTail();
50
const head = dlcl1.handleGetHead();
51
52
let current: ListNode<number> | null = tail;
53
let count: number = expected.length - 1;
54
// ? 反向遍历
55
while (current && current !== head) {
56
expect(current.value).toBe(expected[count]);
57
58
count--;
59
current = current.prev;
60
}
61
if (current) {
62
expect(current.value).toBe(expected[count]);
63
64
// ? 重置
65
count = 0;
66
current = head;
67
}
68
69
// ? 正向遍历
70
while (current && current !== tail) {
71
expect(current.value).toBe(expected[count]);
72
73
count++;
74
current = current.next;
75
}
76
if (current) {
77
expect(current.value).toBe(expected[count]);
78
}
79
});
80
81
test('dlcl1.handleGetLength should return the length of linked-list', () => {
82
const dlcl1 = new DoubleLinkedCircularList<number>({
83
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
84
});
85
86
const expected_1 = 9;
87
const expected_2 = 8;
88
const expected_3 = 10;
89
90
const result_1: number = dlcl1.handleGetLength();
91
expect(result_1).toBe(expected_1);
92
93
const result_2: number = dlcl1.handleRemove(41).handleGetLength();
94
expect(result_2).toBe(expected_2);
95
96
const result_3: number = dlcl1.handleAppend(41).handleAppend(100).handleGetLength();
97
expect(result_3).toBe(expected_3);
98
});
99
100
test('dlcl1.handleAppend should add new node to the tail of the linked-list', () => {
101
const dlcl1 = new DoubleLinkedCircularList<number>({
102
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
103
});
104
105
const expected_length_1 = 9;
106
const expected_value_1 = 41;
107
const expected_length_2 = 10;
108
const expected_value_2 = 100;
109
const expected_length_3 = 11;
110
const expected_value_3 = 200;
111
112
const result_length_1: number = dlcl1.handleGetLength();
113
const result_value_1: number = (dlcl1.handleGetTail() as ListNode<number>).value;
114
expect(result_length_1).toBe(expected_length_1);
115
expect(result_value_1).toBe(expected_value_1);
116
117
const result_length_2: number = dlcl1.handleAppend(100).handleGetLength();
118
const result_value_2: number = (dlcl1.handleGetTail() as ListNode<number>).value;
119
expect(result_length_2).toBe(expected_length_2);
120
expect(result_value_2).toBe(expected_value_2);
121
122
const result_length_3: number = dlcl1.handleAppend(200).handleGetLength();
123
const result_value_3: number = (dlcl1.handleGetTail() as ListNode<number>).value;
124
expect(result_length_3).toBe(expected_length_3);
125
expect(result_value_3).toBe(expected_value_3);
126
});
127
128
test('dlcl1.handlePrepend should add new node to the head of the linked-list', () => {
129
const dlcl1 = new DoubleLinkedCircularList<number>({
130
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
131
});
132
133
const expected_length_1 = 9;
134
const expected_value_1 = 2;
135
const expected_length_2 = 10;
136
const expected_value_2 = 100;
137
const expected_length_3 = 11;
138
const expected_value_3 = 200;
139
140
const result_length_1: number = dlcl1.handleGetLength();
141
const result_value_1: number = (dlcl1.handleGetHead() as ListNode<number>).value;
142
expect(result_length_1).toBe(expected_length_1);
143
expect(result_value_1).toBe(expected_value_1);
144
145
const result_length_2: number = dlcl1.handlePrepend(100).handleGetLength();
146
const result_value_2: number = (dlcl1.handleGetHead() as ListNode<number>).value;
147
expect(result_length_2).toBe(expected_length_2);
148
expect(result_value_2).toBe(expected_value_2);
149
150
const result_length_3: number = dlcl1.handlePrepend(200).handleGetLength();
151
const result_value_3: number = (dlcl1.handleGetHead() as ListNode<number>).value;
152
expect(result_length_3).toBe(expected_length_3);
153
expect(result_value_3).toBe(expected_value_3);
154
});
155
156
test('dlcl1.handleInsertBefore should add new list-node to the front of the target node', () => {
157
const dlcl1 = new DoubleLinkedCircularList<number>({
158
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
159
});
160
161
const expected_length_1 = 10;
162
const expected_value_1 = 100;
163
const expected_length_2 = 11;
164
const expected_value_2 = 200;
165
166
// ? 头节点
167
const result_length_1: number = dlcl1.handleInsertBefore(2, 100).handleGetLength();
168
const result_value_1: number = (dlcl1.handleGetHead() as ListNode<number>).value;
169
expect(result_length_1).toBe(expected_length_1);
170
expect(result_value_1).toBe(expected_value_1);
171
172
// ? 其它部位
173
const result_length_2: number = dlcl1.handleInsertBefore(2, 200).handleGetLength();
174
const result_value_2: number = ((dlcl1.handleGetHead() as ListNode<number>).next as ListNode<number>).value;
175
expect(result_length_2).toBe(expected_length_2);
176
expect(result_value_2).toBe(expected_value_2);
177
});
178
179
test("dlcl1.handleInsertAfter should add new list-node to the back of the target node", () => {
180
const dlcl1 = new DoubleLinkedCircularList<number>({
181
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
182
});
183
184
const expected_length_1 = 10;
185
const expected_value_1 = 100;
186
const expected_length_2 = 11;
187
const expected_value_2 = 200;
188
189
// ? 尾部节点
190
const result_length_1: number = dlcl1.handleInsertAfter(41, 100).handleGetLength();
191
const result_value_1: number = (dlcl1.handleGetTail() as ListNode<number>).value;
192
expect(result_length_1).toBe(expected_length_1);
193
expect(result_value_1).toBe(expected_value_1);
194
195
// ? 其它部位
196
const result_length_2: number = dlcl1.handleInsertAfter(41, 200).handleGetLength();
197
const result_value_2: number = ((dlcl1.handleGetTail() as ListNode<number>).prev as ListNode<number>).value;
198
expect(result_length_2).toBe(expected_length_2);
199
expect(result_value_2).toBe(expected_value_2);
200
});
201
202
test('dlcl1.handleRemove should remove special node from the linked-list', () => {
203
const dlcl1 = new DoubleLinkedCircularList<number>({
204
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
205
});
206
const received_value = 7;
207
const expected_length = 8;
208
const expected_value = false;
209
210
const result_length: number = dlcl1.handleRemove(7).handleGetLength();
211
expect(result_length).toBe(expected_length);
212
213
let sign: boolean = false;
214
dlcl1.handleTraversalWithForward((node) => {
215
if (node.value === received_value) {
216
sign = true;
217
}
218
});
219
expect(sign).toBe(expected_value);
220
});
221
222
test('dlcl1.handleTraversalWithForward should traversal the linked-list forwardly', () => {
223
const dlcl1 = new DoubleLinkedCircularList<number>({
224
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
225
});
226
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
227
let sign = false;
228
let count = 0;
229
230
dlcl1.handleTraversalWithForward((node) => {
231
node.value !== expected[count] && (sign = true);
232
count++;
233
});
234
235
expect(sign).toBeFalsy();
236
});
237
238
test('dlcl1.handleTraversalWithBackward should traversal the linked-list backwardly', () => {
239
const dlcl1 = new DoubleLinkedCircularList<number>({
240
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
241
});
242
const expected = [41, 14, 23, 19, 7, 3, 8, 5, 2];
243
244
let sign = false;
245
let count = 0;
246
247
dlcl1.handleTraversalWithBackward((node) => {
248
node.value !== expected[count] && (sign = true);
249
count++;
250
});
251
252
expect(sign).toBeFalsy();
253
});
254
});
Copied!

API

Name
Type
Description
handleGetHead
() => ListNode | null
获取头节点
handleGetTail
() => ListNode | null
获取尾节点
handleAppend
(value: V) => DoubleLinkedCircularList<V>
尾部追加节点
handlePrepend
(value: V) => DoubleLinkedCircularList<V>
首部追加节点
handleInsertBefore
(target: V, value: V) => DoubleLinkedCircularList<V>
将目标节点插入至源节点前
handleInsertAfter
(target: V, value: V) => DoubleLinkedCircularList<V>
将目标节点插入至源节点后
handleTraversalWithForward
(callback: (node: ListNode<V>) => void) => void
正向遍历双向循环链表
handleTraversalWithBackward
(callback: (node: ListNode<V>) => void) => void
反向遍历双向循环链表
handleGetLength
() => number
获取链表长度
handleRemove
(value: V) => DoubleLinkedCircularList
移除链表指定节点
最近更新 1yr ago
复制链接