链表和数组:
链表和数组一样,可以用于存储一系列的元素,但是链表和数组的实现机制完全不同。
数组:
存储多个元素,数组(或列表)可能是最常用的数据结构。
几乎每一种编程语言都有默认实现数组结构,提供了一个便利的
[]
语法来访问数组元素。
数组缺点:
- 数组的创建需要申请一段连续的内存空间(一整块内存),并且大小是固定的,当前数组不能满足容量需求时,需要扩容。 (一般情况下是申请一个更大的数组,比如 2 倍,然后将原数组中的元素复制过去)
- 在数组开头或中间位置插入 / 删除数据的成本很高,需要进行大量元素的位移。
链表(LinkedList):
存储多个元素,另外一个选择就是使用链表。
不同于数组,链表中的元素在内存中不必是连续的空间。
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。
链表优点:
- 内存空间不必是连续的,可以充分利用计算机的内存,实现灵活的内存动态管理。
- 链表不必在创建时就确定大小,并且大小可以无限延伸下去。
- 链表在插入和删除数据时,时间复杂度可以达到 O(1),相对数组效率高很多。
链表缺点:
- 访问任何一个位置的元素时,需要从头开始访问。(无法跳过第一个元素访问任何一个元素)
- 无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
- 虽然可以轻松地到达下一个节点,但是回到前一个节点是很难的。
如何选择
频繁在中间或前面插入数据时选择链表
需要使用下标去修改获取数据时选择数组
# 1、单向链表
单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。
链表的火车结构
链表的数据结构
head 属性指向链表的第一个节点。 链表中的最后一个节点指向
null
。 当链表中一个节点也没有的时候,head 直接指向null
。给火车加上数据后的结构
# 2、链表中的常见操作
常见操作可以按增删改查分类,剩下的几个都是获取链表信息的方法
append(element)
向链表尾部添加一个新的项。insert(position, element)
向链表的特定位置插入一个新的项。get(position)
获取对应位置的元素。indexOf(element)
返回元素在链表中的索引。如果链表中没有该元素就返回-1。update(position, element)
修改某个位置的元素。removeAt(position)
从链表的特定位置移除一项。remove(element)
从链表中移除一项。isEmpty()
如果链表中不包含任何元素,返回 trun,如果链表长度大于 0 则返回 false。size()
返回链表包含的元素个数,与数组的 length 属性类似。toString()
由于链表项使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString 方法,让其只输出元素的值。
# 3、单向链表的封装
先创建单向链表类 LinkedList,添加基本属性,再逐步实现单向链表的常用方法。
// 封装链表节点类
class Node{
constructor(data) {
this.data = data
this.next = null
}
}
class LinkedList{
constructor() {
// 链表头节点,初始为 null
this.head = null
// 初始链表长度为 0
this.length = 0
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# append()
向链表尾部添加一个新的项。
过程图解:
首先让
currentNode
指向第一个节点。通过
while
循环使currentNode
指向最后一个节点,最后通过currentNode.next = newNode
,让最后一个节点指向新节点newNode
。
// append(data) 往链表尾部追加数据
append(data) {
// 1、创建新节点
const newNode = new Node(data)
// 2、追加新节点
if (this.length === 0) {
// 链表长度为 0 时,直接修改头指针head即可
this.head = newNode
} else {
// 链表长度大于 0 时,在尾节点后面添加新节点
// 先取得链表第一个节点,之后循环遍历至尾节点
let currVE EAent = this.head
// 当current.next!=null时表示不是尾节点
while (current.next) {
current = current.next
}
// 尾节点的 next 指向新节点
current.next = newNode
}
// 3、追加完新节点后,链表长度 + 1
this.length++
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
代码测试:
const linkedList = new LinkedList();
// 测试 append 方法
linkedList.append('AA');
linkedList.append('BB');
linkedList.append('CC');
console.log(linkedList);
2
3
4
5
6
# toString()
// toString() 链表数据以字符串形式返回
toString() {
let current = this.head
let resultString = 'a'
// 遍历所有的节点,拼接为字符串,直到尾节点(值为null)
while (current) {
resultString += current.data + ' '//空格
current = current.next
}
return resultString
}
2
3
4
5
6
7
8
9
10
11
12
13
测试代码:
// 测试 toString 方法
console.log(linkedList.toString()); //--> AA BB CC
2
# insert()
向链表的特定位置插入一个新的项。
// insert(position, data) 在指定位置(position)插入节点
insert(position, data) {
// position 新插入节点的位置
// position = 0 表示新插入后是第一个节点
// position = 1 表示新插入后是第二个节点,以此类推
// 1、对 position 进行越界判断,不能小于 0 或大于链表长度
if (position < 0 || position > this.length) return false;
// 2、创建新节点
const newNode = new Node(data);
// 3、插入节点
if (position === 0) {
// position = 0 即新插入节点为第一个节点的情况
// 顺序很重要,先让新节点指向原来的第一个节点,之后修改头指针指向新节点
// 让新节点的 next 指向 原来的第一个节点,即 head
// newNode.next=原来第一个结点
newNode.next = this.head;
// head 赋值为 newNode
//head指向新jiedian
this.head = newNode;
} else {
// 0 < position <= length 的情况
// 初始化一些状态变量
let index = 0; // 遍历索引初始化为 0
let current = this.head; // current指向head
let previous = null; // 遍历的的上一节点初始化为 null
// 在 0 ~ position 之间遍历,不断地更新 current 和 previous
// 直到找到要插入的位置
while (index++ < position) {
previous = current;
current = current.next;//指向下一个结点
}
// 在当前节点和当前节点的上一节点之间插入新节点,即改变它们的指向
newNode.next = current;
previous.next = newNode;
}
// 4、追加完新节点后,链表长度 + 1
this.length++;
// 5、返回新添加的节点,方便其他操作
return newNode;
}
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
测试结果:
// 测试 insert 方法
linkedList.insert(0, "123");
linkedList.insert(2, "456");
console.log(linkedList.toString()); //--> 123 AA 456 BB CC
2
3
4
# getData()
获取指定位置(position)的 data。
// getData(position) 获取指定位置的 data
getData(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null;
// 2、获取指定 position 的节点
let index = 0;
//position=2 从0开始算
let current = this.head;//head不为空的话current=第一个结点
//index= 0 current=
//index= 1 current= position=2
//index=2 index不小于position
while (index++ < position) {
current = current.next;
}
// 3、返回相应节点的 data
return current.data;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
测试代码:
// 测试 getData 方法
console.log(linkedList.toString()); //--> 123 AA 456 BB CC
console.log(linkedList.getData(0)); //--> 123
console.log(linkedList.getData(1)); //--> AA
2
3
4
# indexOf()
indexOf(data) 返回指定 data 的 index,如果没有,返回 -1。
// indexOf(data) 返回指定 data 的 index,如果没有,返回 -1。
indexOf(data) {
// 1、定义遍历变量
let index = 0
let current = this.head
// 2、遍历比较链表中数据
while (current) {
if (current.data === data) {
// 找到相应数据,返回索引
return index
}
current = current.next
index++
}
// 未找到相应数据,返回-1
return -1
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
代码测试:
// 测试 indexOf 方法
console.log(linkedList.toString()); //--> 123 AA 456 BB CC
console.log(linkedList.indexOf("AA")); //--> 1
console.log(linkedList.indexOf("ABC")); //--> -1
2
3
4
# update()
update(position, data) 修改指定位置节点的 data。
// update(position, data) 修改指定位置节点的 data
update(position, data) {
// 涉及到 position 都要进行越界判断
// 1、position越界判断
if (position < 0 || position >= this.length) return false
// 2、循环遍历,找到指定 position 的节点
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
// 3、修改相应节点的 data
current.data = data
// 4、返回指定 position 的节点,方便其他操作
return current
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
代码测试:
// 测试 update 方法
linkedList.update(0, "12345");
console.log(linkedList.toString()); //--> 12345 AA 456 BB CC
linkedList.update(1, "54321");
console.log(linkedList.toString()); //--> 12345 54321 456 BB CC
2
3
4
5
# removeAt()
removeAt(position) 删除指定位置的节点。
// removeAt(position) 删除指定位置的节点,并返回删除的那个节点
removeAt(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null
// 2、删除指定 position 节点
let current = this.head
if (position === 0) {
// position = 0 的情况
this.head = this.head.next
} else {
// position > 0 的情况
// 在 0 ~ position 之间遍历,不断地更新 current 和 previous
// 直到找到要删除的位置
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
// 让上一节点的 next 指向当前的节点的 next,相当于删除了当前节点。
previous.next = current.next
}
// 3、更新链表长度 -1
this.length--
// 4、返回被删除的节点,方便其他操作
return current
}
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
代码测试
// 测试 removeAt 方法
linkedList.removeAt(3);
console.log(linkedList.toString()); //--> 12345 54321 456 CC
2
3
# remove()
remove(data) 删除指定 data 所在的节点。
代码实现:
// remove(data) 删除指定 data 的节点,并返回删除的那个节点
remove(data) {
return this.removeAt(this.indexOf(data))
}
2
3
4
代码测试:
// 测试 remove 方法
linkedList.remove("CC");
console.log(linkedList.toString()); //--> 12345 54321 456
2
3
# isEmpty()
isEmpty() 判断链表是否为空。
代码实现:
// isEmpty() 判断链表是否为空
isEmpty() {
return this.length === 0
}
2
3
4
代码测试:
// 测试 isEmpty 方法
console.log(linkedList.isEmpty()); //--> false
2
# size()
size() 获取链表的长度。
代码实现:
// size() 获取链表的长度
size() {
return this.length
}
2
3
4
代码测试:
// 测试 size 方法
console.log(linkedList.size()); //--> 3
2
# 完整实现
// 封装链表节点类
export class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 单向链表结构的封装
export class LinkedList {
constructor() {
// 链表头节点,初始为 null
this.head = null;
// 初始链表长度为 0
this.length = 0;
}
// ------------ 链表的常见操作 ------------ //
// append(data) 往链表尾部追加数据
append(data) {
// 1、创建新节点
const newNode = new Node(data);
// 2、追加新节点
if (this.length === 0) {
// 链表长度为 0 时,直接修改头指针head即可
this.head = newNode;
} else {
// 链表长度大于 0 时,在尾节点后面添加新节点
// 先取得链表第一个节点,之后循环遍历至尾节点
let current = this.head;
// 当current.next!=null时表示不是尾节点
while (current.next) {
current = current.next;
}
// 尾节点的 next 指向新节点
current.next = newNode;
}
// 3、追加完新节点后,链表长度 + 1
this.length++;
}
// insert(position, data) 在指定位置(position)插入节点
insert(position, data) {
// position 新插入节点的位置
// position = 0 表示新插入后是第一个节点
// position = 1 表示新插入后是第二个节点,以此类推
// 1、对 position 进行越界判断,不能小于 0 或大于链表长度
if (position < 0 || position > this.length) return false;
// 2、创建新节点
const newNode = new Node(data);
// 3、插入节点
if (position === 0) {
// position = 0 即新插入节点为第一个节点的情况
// 顺序很重要,先让新节点指向原来的第一个节点,之后修改头指针指向新节点
// 让新节点的 next 指向 原来的第一个节点,即 head
newNode.next = this.head;
// head 赋值为 newNode
this.head = newNode;
} else {
// 0 < position <= length 的情况
// 初始化一些状态变量
let index = 0; // 遍历索引初始化为 0
let current = this.head; // 遍历的当前节点初始化为 head
let previous = null; // 遍历的的上一节点初始化为 null
// 在 0 ~ position 之间遍历,不断地更新 current 和 previous
// 直到找到要插入的位置
while (index++ < position) {
previous = current;
current = current.next;
}
// 在当前节点和当前节点的上一节点之间插入新节点,即改变它们的指向
newNode.next = current;
previous.next = newNode;
}
// 4、追加完新节点后,链表长度 + 1
this.length++;
// 5、返回新添加的节点,方便其他操作
return newNode;
}
// getData(position) 获取指定位置的 data
getData(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null;
// 2、获取指定 position 的节点
let index = 0;
let current = this.head;
while (index++ < position) {
current = current.next;
}
// 3、返回相应节点的 data
return current.data;
}
// indexOf(data) 返回指定 data 的 index,如果没有,返回 -1。
indexOf(data) {
// 1、定义遍历变量
let index = 0;
let current = this.head;
// 2、遍历比较链表中数据
while (current) {
if (current.data === data) {
// 找到相应数据,返回索引
return index;
}
current = current.next;
index++;
}
// 未找到相应数据,返回-1
return -1;
}
// update(position, data) 修改指定位置节点的 data
update(position, data) {
// 涉及到 position 都要进行越界判断
// 1、position越界判断
if (position < 0 || position >= this.length) return false;
// 2、循环遍历,找到指定 position 的节点
let index = 0;
let current = this.head;
while (index++ < position) {
current = current.next;
}
// 3、修改相应节点的 data
current.data = data;
// 4、返回指定 position 的节点,方便其他操作
return current;
}
// removeAt(position) 删除指定位置的节点,并返回删除的那个节点
removeAt(position) {
// 1、position越界判断
if (position < 0 || position >= this.length) return null;
// 2、删除指定 position 节点
let current = this.head;
if (position === 0) {
// position = 0 的情况
this.head = this.head.next;
} else {
// position > 0 的情况
// 在 0 ~ position 之间遍历,不断地更新 current 和 previous
// 直到找到要删除的位置
let index = 0;
let previous = null;
while (index++ < position) {
previous = current;
current = current.next;
}
// 让上一节点的 next 指向当前的节点的 next,相当于删除了当前节点。
previous.next = current.next;
}
// 3、更新链表长度 -1
this.length--;
// 4、返回被删除的节点,方便其他操作
return current;
}
// remove(data) 删除指定 data 的节点,并返回删除的那个节点
remove(data) {
return this.removeAt(this.indexOf(data));
}
// isEmpty() 判断链表是否为空
isEmpty() {
return this.length === 0;
}
// size() 获取链表的长度
size() {
return this.length;
}
// toString() 链表数据以字符串形式返回
toString() {
let current = this.head;
let resultString = "";
// 遍历所有的节点,拼接为字符串,直到尾节点(值为null)
while (current) {
resultString += current.data + " ";
current = current.next;
}
return resultString;
}
}
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205