链表是一组节点组成的集合，每个节点都使用一个对象的引用指向它的下一个节点，指向节点的引用叫做链
前言
链表是一组节点组成的集合，每个节点都使用一个对象的引用指向它的下一个节点，指向节点的引用叫做链。
实现
使用 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
}
}
|
总结
链表是一种高效的数据结构，如果发现数组在使用时很慢，就可以考虑用链表替代它，但是如果需要对数据随机访问，数组任然是更优的选择