源码地址
链表（linked list）
链表是一种在物理上非连续、非顺序的数据结构，由若干节点组成。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单向链表
单向链表的每个节点包含两个部分，data 跟 next，data用于存放数据，next 指向 下一个节点
1
2
3
4
5
6
7
8
9
10
|
var node_1 = { data: 1, next: null }
var node_2 = { data: 2, next: null }
var node_3 = { data: 3, next: null }
var node_4 = { data: 4, next: null }
node_1.next = node_2
node_2.next = node_3
node_3.next = node_4
|
初始化
1
2
3
4
5
6
7
8
9
10
11
12
| class LinkList {
constructor(...arg){
this.head = null
this.rear = null
}
node(data){
return {
data,
next: null
}
}
}
|
基本操作
插入
头部插入
链表的头节点前面插入
- 新节点的next指向原头节点
- 把头节点指针指向新节点
1
2
3
| 1->2->3
插入0
0->1->2->3
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| prepend(data){
let node = this.node(data)
if(!this.head){
this.head = node
this.rear = node
return node.data
}
let temp = this.head
node.next = temp
this.head = node
return node.data
}
|
尾部插入
从节点尾部插入新节点
- 通过尾指针找到尾节点，尾节点的next指向新节点
- 把尾指针指向新节点
1
2
3
| 1->2->3
插入4
1->2->3->4
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| append(data){
let node = this.node(data)
if(!this.rear){
this.head = node
this.rear = node
return node.data
}
let temp = this.rear
temp.next = node
this.rear = node
return node.data
}
|
中间插入
从指定的某个值后插入
- 找到目标节点，将目标节点的 next 取出
- 将新节点的 next 指向目标节点的 next
- 目标节点的 next 指向新节点
1
2
3
4
5
6
7
| 1->3
在 1 后插入 2
取出 1
3
1->2
2->3
1->2->3
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
add(el, data){
let curr = this.contains(el)
if(!curr) throw null
let node = this.node(data)
let temp = curr.next
curr.next = node
node.next = temp
return node.data
}
|
删除
头部删除
从头节点开始删除节点
- 通过头指针取出头节点，取出头节点的 next
- 头指针指向 头节点的 next
- 释放原来的头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
removeHead(){
let temp = this.head
if(!temp) return null
if(!temp.next) this.rear = null
this.head = temp.next
temp.next = null
return temp.data
}
|
删除尾节点
从尾部删除节点
- 取出尾指针指向的尾节点，通过头节点遍历找出尾节点的前置节点
- 将尾指针指向尾节点的前置节点，next 指向 null
- 释放原来的尾节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| removeRear(){
let curr = this.head
while (curr){
if(curr.next == this.rear) break
curr = curr.next
}
let rear = this.rear
curr.next = null
this.rear = curr
return rear.data
}
|
删除指定节点
删除指定的节点，断开前置节点的 next 指向，令前置节点的 next 指向删除节点的 next
- 找到目标节点的前置节点 curr，取出待删除节点 node = curr.next
- 前置节点 curr 的 next 指向 待删除节点 node node.next
- 释放待删除节点
1
2
3
4
| 1->2->3->4
2, 3
2->4
1->2->4
|
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
| remove(el){
if(!this.head) return null
if(this.head.data === el){
let temp = this.head
this.head = this.head.next
temp.next = null
return temp.data
}
let curr = this.head
while (curr && curr.next){
if(curr.next.data == el) break
curr = curr.next
}
if(!curr.next) return null
if(curr.next == this.rear){
this.rear = curr
}
let node = curr.next
curr.next = node.next
return node.data
}
|
查找
- 定位到头节点
- 根据头节点的next往下遍历比对
- 找到就返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
contains(el){
if(!this.head) return null
let curr = this.head
while (curr){
if(curr.data === el) break
curr = curr.next
}
return curr
}
|
遍历
正向遍历
- 找到头节点
- 查找每一个值，当curr为 null 跳出循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
traverse(callback=(item)=>item){
let res = []
if(!this.head) return res
let curr = this.head
while (curr){
res.push(callback(curr.data))
curr = curr.next
}
return res
}
|
反向遍历
- 找到头节点，找到尾节点
- 每次从头节点查找到前置节点
1
2
3
4
5
| 1->2->3
3
2
等于 head
1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
reverseTraversal(callback=(item)=>item){
let res = []
if(!this.head) return res
let curr = this.rear
while(curr != this.head){
let prev = this.head
while(prev.next != curr){
prev = prev.next
}
res.push(callback(curr.data))
curr = prev
}
res.push(callback(curr.data))
return res
}
|
反转
- 取出头尾节点，定义 next = null prev = null curr = head
- 从 curr 开始循环，取出 curr.next，next = curr.next
- curr.next 指向 prev
- prev = curr
- curr = next
- 回到第二步
1
2
3
4
| 1->2->3
1 2->3
2->1 3
3->2->1
|
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
|
reverse() {
if(!this.head) return null
let curr = this.head
let next = null
let prev = null
while(curr){
next = curr.next
curr.next = prev
prev = curr
curr = next
}
this.rear = this.head
this.head = prev
return this
}
|
取出中间节点
取出中间节点一般通过快慢指针来实现
- search 指针 search.next.next
- mid 指针 mid.next
- search 相当于 走两步，mid 走一步，当 search 走完的时候，mid 则刚好在中间
1
2
3
4
| 1->2->3->4->5
1 3
2 4
3 5
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
findMid(){
if(!this.head) return null
let search = this.head
let mid = this.head
while(search.next){
if(search.next.next != null){
search = search.next.next
mid = mid.next
}else{
search = search.next
}
}
return mid
}
|
时间复杂度
| Access |
Search |
Insertion |
Deletion |
| O(n) |
O(n) |
O(1) |
O(1) |
空间复杂度
O(n)
