-
Notifications
You must be signed in to change notification settings - Fork 1
/
link.ts
155 lines (129 loc) · 3.53 KB
/
link.ts
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/**
* 链表
* 此处实现带哨兵的双向链表
*
* 哨兵是一个特殊的 Node,用来简化链表的操作(特别是删除操作)。
* 加入哨兵后,哨兵扮演了 head 和 tail 的角色(Link 不再需要 head 和 tail 指针),整个 Link 构成了循环链表,
* 第一个 Node 的 prev 指向哨兵,最后一个 Node 的 next 也指向哨兵;
* 哨兵的 next 指向第一个 Node,哨兵的 pre 指向最后一个 Node;
* 初始化时,哨兵的 pre 和 next 指向自己。
*/
/**
* 节点定义
*/
interface Node {
data: unknown;
prev: Node;
next: Node;
}
/**
* 双向链表
*/
class Link {
// 链表中元素数量
protected _size: number
// 哨兵节点
protected sentinel: Node
public constructor() {
this._size = 0
// 初始化哨兵,其 prev 和 next 都指向自身
const sentinel = { data: null, prev: null, next: null } as Node
// prev 和 next 指向自身
sentinel.prev = sentinel.next = sentinel
this.sentinel = sentinel
}
public isEmpty(): boolean {
return this._size == 0
}
public size(): number {
return this._size
}
/**
* 向链表(头)插入数据 data
*
* @param data - 待插入元素
* @returns 生成的新节点 Node
*/
public insert(data: unknown): Node {
this._size++
// 将 data 包装成 Node
const node = {
data,
prev: this.sentinel,
next: this.sentinel.next,
}
this.sentinel.next.prev = node
this.sentinel.next = node
return node
}
/**
* 查找 data
* @param data
* @returns 如果找到,则返回对应的 Node,否则返回 null
*/
public search(data: unknown): Node | null {
// 从 sentinel.next 往后找
let curr = this.sentinel.next
while (curr !== this.sentinel) {
if (curr.data === data) {
return curr
}
curr = curr.next
}
return null
}
/**
* 根据自定义函数查找 data
* @param data
* @returns 如果找到,则返回对应的 Node,否则返回 null
*/
public searchByFunc(compareFunc: (data: unknown) => boolean): Node | null {
let curr = this.sentinel.next
while (curr !== this.sentinel) {
if (compareFunc(curr.data)) {
return curr
}
curr = curr.next
}
return null
}
/**
* 删除节点
* 删除前:nodePrev -> node -> nodeNext
* 删除后:nodePrev -> nodeNext,且 node 不再引用 nodePrev 和 nodeNext
*/
public delete(node: Node) {
// 判断 node 是否已经被删除了
if (node.prev === null || node.next === null) {
return
}
node.prev.next = node.next
node.next.prev = node.prev
// 清理前后指针
node.prev = node.next = null
this._size--
}
/**
* 取出表头节点并从链表中删除
*/
public shift(): Node | null {
if (!this._size) {
return null
}
const node = this.sentinel.next
this.delete(node)
return node
}
/**
* 取出表尾元素,并从链表中删除
*/
public pop(): Node | null {
if (!this._size) {
return null
}
const node = this.sentinel.prev
this.delete(node)
return node
}
}
export { Link }