cover

数据结构与算法之链表

前言

链表是一组节点组成的集合,每个节点都使用一个对象的引用指向它的下一个节点,指向节点的引用叫做链。

实现

使用 LinkedListNode 类来表示节点,使用 LinkedList 来表示链表

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
class LinkedListNode {
element: any
next: LinkedListNode

constructor(element: any) {
this.element = element
this.next = null
}
}

class LinkedList {
// 头节点
head: LinkedListNode

constructor() {
this.head = new LinkedListNode('head')
}

// 查找
find(element: any) {
let currentNode: LinkedListNode = this.head

while (currentNode.element !== element) {
currentNode = currentNode.next
}
return currentNode
}

// 插入
insert(element: any, item: any) {
let newNode = new LinkedListNode(element)
let currentNode = this.find(item)

newNode.next = currentNode.next
currentNode.next = newNode
}

// 移除
remove(element: any) {
let prevNode = this.findPrevNode(element)

if (!(prevNode.next === null)) {
prevNode.next = prevNode.next.next
}
}

//
findPrevNode(element: any) {
let currentNode = this.head
while (
!(currentNode.next === null) &&
currentNode.next.element !== element
) {
currentNode = currentNode.next
}
return currentNode
}

// 显示
display() {
let currentNode = this.head

while (!(currentNode.next === null)) {
console.log(currentNode.next.element)
currentNode = currentNode.next
}
}
}

测试

1
2
3
4
5
6
7
8
9
10
11
const foods = new LinkedList()

foods.insert('eggs', 'head')
foods.insert('apple', 'eggs')
foods.insert('bread', 'apple')
foods.insert('chese', 'bread')
foods.insert('rice', 'chese')
foods.display()
console.log('------------')
foods.remove('bread')
foods.display()

输出

1
2
3
4
5
6
7
8
9
10
eggs
apple
bread
chese
rice
------------
eggs
apple
chese
rice

双向链表

要实现双向链表首先要为 LinkedListNode 类增加一个 prev 属性

1
2
3
4
5
6
7
8
9
10
11
class LinkedListNode {
element: any
prev: LinkedListNode
next: LinkedListNode

constructor(element: any) {
this.element = element
this.prev = null
this.next = null
}
}

然后修改 LinkedList 类的 insert, remove 方法

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
class LinkedList {
// 头节点
head: LinkedListNode = new LinkedListNode('head')

// 查找
find(element: any) {
let currentNode = this.head

while (currentNode.element !== element) {
currentNode = currentNode.next
}
return currentNode
}

// 找到最后的节点
findLast() {
let currentNode = this.head

while (currentNode.next !== null) {
currentNode = currentNode.next
}
return currentNode
}

// 插入
insert(element: any, item: any) {
let newNode = new LinkedListNode(element)
let currentNode = this.find(item)

newNode.prev = currentNode
newNode.next = currentNode.next
currentNode.next = newNode
}

// 移除
remove(element: any) {
let currentNode = this.find(element)

if (currentNode.next !== null) {
currentNode.prev.next = currentNode.next
currentNode.next.prev = currentNode.prev
currentNode.next = null
currentNode.prev = null
}
}

// 显示
display() {
let currentNode = this.head

while (!(currentNode.next === null)) {
console.log(currentNode.next.element)
currentNode = currentNode.next
}
}

// 倒叙显示
displayReverse() {
let currentNode = this.findLast()

while (currentNode.prev !== null) {
console.log(currentNode.element)
currentNode = currentNode.prev
}
}
}

测试一下

1
2
3
4
5
6
7
8
9
10
11
foods.insert('eggs', 'head')
foods.insert('apple', 'eggs')
foods.insert('bread', 'apple')
foods.insert('chese', 'bread')
foods.insert('rice', 'chese')
foods.display()
console.log('------------')
foods.remove('bread')
foods.display()
console.log('------------')
foods.displayReverse()

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
eggs
apple
bread
chese
rice
------------
eggs
apple
chese
rice
------------
rice
chese
apple
eggs

循环链表

创建循环链表需要让它的头节点的 next 属性指向本身, 然后修改 display 方法

1
2
3
4
5
6
7
8
9
10
11
this.head.next = this.head

// 显示
display() {
let currentNode = this.head

while (currentNode.next !== null && currentNode.next.element !== 'head') {
console.log(currentNode.next.element)
currentNode = currentNode.next
}
}

总结

链表是一种高效的数据结构,如果发现数组在使用时很慢,就可以考虑用链表替代它,但是如果需要对数据随机访问,数组任然是更优的选择

知识共享许可协议
← 数据结构与算法之字典 如何在 Egg.js 中使用 Sequelize 的事务 Transaction →