单向链表简介

链表和数组一样,可以用于存储一系列的元素,但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有的语言称为指针或连接)组成。类似于火车头,一节车厢载着乘客(数据),通过节点连接另一节车厢。

image-20200707211620661

image-20200707211629678

image-20200707211641966

  • head 属性指向链表的第一个节点;
  • 链表中的最后一个节点指向 null;
  • 当链表中一个节点也没有的时候,head 直接指向 null;

数组存在的缺点

  • 数组的创建通常需要申请一段连续的内存空间(一整块内存),并且大小是固定的。所以当原数组不能满足容量需求时,需要扩容(一般情况下是申请一个更大的数组,比如 2 倍,然后将原数组中的元素复制过去)。
  • 在数组的开头或中间位置插入数据的成本很高,需要进行大量元素的位移。

链表的优势

  • 链表中的元素在内存中不必是连续的空间,可以充分利用计算机的内存,实现灵活的内存动态管理
  • 链表不必在创建时就确定大小,并且大小可以无限地延伸下去。
  • 链表在插入和删除数据时,时间复杂度可以达到 O(1),相对数组效率高很多。

链表的缺点:

  • 链表访问任何一个位置的元素时,都需要从头开始访问(无法跳过第一个元素访问任何一个元素)。
  • 无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
  • 虽然可以轻松地到达下一个节点,但是回到前一个节点是很难的。

链表中的常见操作

  • 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 方法,让其只输出元素的值;

首先需要弄清楚:下文中的 position 指的是两个节点之间,并且与 index 的关系如下图所示:

image-20200707211658363

position 的值一般表示 position 所指位置的下一个节点。当 position 的值与 index 的值相等时,比如 position = index = 1,那么它们都表示 Node2。

封装单向链表类

创建单向链表类

先创建单向链表类 Linklist,并添加基本属性,再实现单向链表的常用方法:

代码解析:

  • 封装 LinkedList 的类, 用于表示我们的链表结构. (和 Java 中的链表同名, 不同 Java 中的这个类是一个双向链表, 后面我们会讲解双向链表)
  • 在 LinkedList 类中有一个 Node 类, 用于封装每一个节点上的信息.(和优先级队列的封装一样)
  • 链表中我们保存两个属性, 一个是链表的长度, 一个是链表中第一个节点.

append(element)

向链表尾部追加数据可能有两种情况:

  • 链表本身为空, 新添加的数据时唯一的节点.
  • 链表不为空, 需要向其他节点后面追加节点.

代码实现:

过程详解:

  • 首先需要做的是将 element 传入方法, 并根据 element 创建一个 Node 节点.

  • 场景一: 链表本身是空的,我们只需要让 head 指向新建的 node 节点即可

  • 场景二: 链表中已经有元素了, 需要向最后的节点的 next 中添加节点.首先让 current 指向第一个节点:

image-20200707211826281

  • 通过 while 循环使 current 指向最后一个节点,最后通过 current.next = newNode,让最后一个节点指向新节点 newNode:

image-20200707211843432

测试代码:

1
2
3
4
5
6
7
8
9
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.测试append方法
list.append('aaa')
list.append('bbb')
list.append('ccc')
console.log(list)

测试结果:

image-20200707211858675

toString()

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 实现toString方法
LinkList.prototype.toString = () => {
// 1.定义变量
let current = this.head
let listString = ''

// 2.循环获取一个个的节点
while (current) {
listString += current.data + ' '
current = current.next //千万不要忘了拼接完一个节点数据之后,让current指向下一个节点
}
return listString
}

方法解读:

  • 该方法比较简单, 主要是获取每一个元素
  • 还是从 head 开头, 因为获取链表的任何元素都必须从第一个节点开头.
  • 循环遍历每一个节点, 并且取出其中的 element, 拼接成字符串.
  • 将最终字符串返回.

测试代码:

1
2
3
4
5
6
7
8
9
10
11
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试toString方法
console.log(list.toString())

测试结果:

image-20200707211945460

insert(position,element)

代码实现:

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
// 实现insert方法
LinkList.prototype.insert = (position, data) => {
//理解positon的含义:position=0表示新界点插入后要成为第1个节点,position=2表示新界点插入后要成为第3个节点
//1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
if (position < 0 || position > this.length) {
return false
}
//2.根据data创建newNode
let newNode = new Node(data)

//3.插入新节点
//情况1:插入位置position=0
if (position == 0) {
// 让新节点指向第一个节点
newNode.next = this.head
// 让head指向新节点
this.head = newNode
//情况2:插入位置position>0(该情况包含position=length)
} else {
let index = 0
let previous = null
let current = this.head
//步骤1:通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
while (index++ < position) {
//步骤2:在current指向下一个节点之前,让previous指向current当前指向的节点
previous = current
current = current.next
}
// 步骤3:通过变量current(此时current已经指向position位置的后一个节点),使newNode指向position位置的后一个节点
newNode.next = current
//步骤4:通过变量previous,使position位置的前一个节点指向newNode
previous.next = newNode
/*
启示:
1.我们无法直接操作链表中的节点,但是可以通过变量指向这些节点,以此间接地操作节点(替身使者);
比如current指向节点3,想要节点3指向节点4只需要:current.next = 4即可。
2.两个节点间是双向的,想要节点2的前一个节点为节点1,可以通过:1.next=2,来实现;
*/
}
//4.新节点插入后要length+1
this.length += 1

return true
}

过程详解:

inset 方法实现的过程:根据插入节点位置的不同可分为多种情况:

  • 情况 1:position = 0

通过: newNode.next = this.head,建立连接 1;

通过: this.head = newNode,建立连接 2;(不能先建立连接 2,否则 this.head 不再指向 Node1)

image-20200707212003041

  • 情况 2:position > 0

首先定义两个变量 previous 和 curent 分别指向需要插入位置 pos = X 的前一个节点和后一个节点;

然后,通过:newNode.next = current,改变指向 3;

最后,通过:previous.next = newNode,改变指向 4;

image-20200707212021082

  • 情况 2 的特殊情形:position = length

情况 2 也包含了 pos = length 的情况,该情况下 current 和 newNode.next 都指向 null;建立连接 3 和连接 4 的方式与情况 2 相同。

image-20200707212045666

添加到其他位置:

  • 如果是添加到其他位置, 就需要先找到这个节点位置了.
  • 我们通过 while 循环, 一点点向下找. 并且在这个过程中保存上一个节点和下一个节点.
  • 找到正确的位置后, 将新节点的 next 指向下一个节点, 将上一个节点的 next 指向新的节点.

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试insert方法
list.insert(0, '在链表最前面插入节点')
list.insert(2, '在链表中第二个节点后插入节点')
list.insert(5, '在链表最后插入节点')
alert(list)
console.log(list)

image-20200707212112493

get(position)

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//实现get方法
LinkList.prototype.get = (position) => {
//1.越界判断
// 当position = length时,取到的是null所以0 =< position < length
if (position < 0 || position >= this.length) {
return null
}
//2.获取指定的positon位置的后一个节点的data
//同样使用一个变量间接操作节点
let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
return current.data
}

过程详解:

get 方法的实现过程:以获取 position = 2 为例,如下图所示:

  • 首先使 current 指向第一个节点,此时 index=0;

image-20200707212133575

  • 通过 while 循环使 current 循环指向下一个节点,注意循环终止的条件 index++ < position,即当 index=position 时停止循环,此时循环了 1 次,current 指向第二个节点(Node2),最后通过 current.data 返回 Node2 节点的数据;

image-20200707212150175

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试get方法
console.log(list.get(0))
console.log(list.get(1))

测试结果:

image-20200707212204745

indexOf(element)

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//实现indexOf方法
LinkList.prototype.indexOf = (data) => {
//1.定义变量
let current = this.head
let index = 0

//2.开始查找:只要current不指向null就一直循环
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}

//3.遍历完链表没有找到,返回-1
return -1
}

代码解析:

  • 代码 1 的位置还是定义需要的变量.
  • 代码 2 的位置, 通过 while 循环获取节点
  • 通过节点获取元素和 element 进行对比, 如果和传入 element 相同, 表示找到, 直接返回 index 即可.
  • 如果没有找到, index++, 并且指向下一个节点.
  • 到最后都没有找到, 说明链表中没有对应的元素, 那么返回-1 即可.

过程详解:

indexOf 方法的实现过程:

  • 使用变量 current 记录当前指向的节点,使用变量 index 记录当前节点的索引值(注意 index = node 数-1)

image-20200707212224834

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试indexOf方法
console.log(list.indexOf('aaa'))
console.log(list.indexOf('ccc'))

测试结果:

image-20200707212236303

update(position,element)

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//实现update方法
LinkList.prototype.update = (position, newData) => {
//1.越界判断
//因为被修改的节点不能为null,所以position不能等于length
if (position < 0 || position >= this.length) {
return false
}
//2.查找正确的节点
let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
//3.将position位置的后一个节点的data修改成newData
current.data = newData
//返回true表示修改成功
return true
}

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试update方法
list.update(0, '修改第一个节点')
list.update(1, '修改第二个节点')
console.log(list)
console.log(list.update(3, '能修改么'))

测试结果:

image-20200707212247902

removeAt(position)

代码实现:

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
//实现removeAt方法
LinkList.prototype.removeAt = (position) => {
//1.越界判断
if (position < 0 || position >= this.length) {
//position不能为length
return null
}
//2.删除元素
//情况1:position = 0时(删除第一个节点)
let current = this.head
if (position == 0) {
//情况2:position > 0时
this.head = this.head.next
} else {
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
//循环结束后,current指向position后一个节点,previous指向current前一个节点
//再使前一个节点的next指向current的next即可
previous.next = current.next
}
//3,length-1
this.length -= 1

//返回被删除节点的data,为此current定义在最上面
return current.data
}

过程详解:

removeAt 方法的实现过程:删除节点时存在多种情况:

  • 情况 1:position = 0,即移除第一个节点(Node1)。

通过:this.head = this.head.next,改变指向 1 即可;

虽然 Node1 的 next 仍指向 Node2,但是没有引用指向 Node1,则 Node1 会被垃圾回收器自动回收,所以不用处理 Node1 指向 Node2 的引用 next。

image-20200707212300727

  • 情况 2:positon > 0,比如 pos = 2 即移除第三个节点(Node3)。

注意:position = length 时 position 后一个节点为 null 不能删除,因此 position != length;

首先,定义两个变量 previous 和 curent 分别指向需要删除位置 pos = x 的前一个节点和后一个节点;

然后,通过:previous.next = current.next,改变指向 1 即可;

随后,没有引用指向 Node3,Node3 就会被自动回收,至此成功删除 Node3 。

image-20200707212314952

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试removeAt方法
console.log(list.removeAt(0))
console.log(list.removeAt(0))
console.log(list)

测试结果:

image-20200707212327149

其他方法

其他方法包括:remove(element)、isEmpty()、size()

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*-------------其他方法的实现--------------*/
//一.实现remove方法
LinkList.prototype.remove = (data) => {
//1.获取data在列表中的位置
let position = this.indexOf(data)
//2.根据位置信息,删除结点
return this.removeAt(position)
}

//二.实现isEmpty方法
LinkList.prototype.isEmpty = () => {
return this.length == 0
}

//三.实现size方法
LinkList.prototype.size = () => {
return this.length
}

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

/*---------------其他方法测试----------------*/
//remove方法
console.log(list.remove('aaa'))
console.log(list)
//isEmpty方法
console.log(list.isEmpty())
//size方法
console.log(list.size())

测试结果:

image-20200707212339289

完整实现

使用 ES5 实现

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
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
// 封装链表类
function LinkList() {
// 封装一个内部类:节点类
function Node(data) {
this.data = data
this.next = null
}

// 属性
// 属性head指向链表的第一个节点
this.head = null
this.length = 0

// 一.实现append方法
LinkList.prototype.append = (data) => {
//1.创建新节点
let newNode = new Node(data)

//2.添加新节点
//情况1:只有一个节点时候
if (this.length == 0) {
this.head = newNode
//情况2:节点数大于1,在链表的最后添加新节点
} else {
//让变量current指向第一个节点
let current = this.head
//当current.next(下一个节点不为空)不为空时,一直循环,直到current指向最后一个节点
while (current.next) {
current = current.next
}
// 最后节点的next指向新的节点
current.next = newNode
}
//3.添加完新结点之后length+1
this.length += 1
}

// 二.实现toString方法
LinkList.prototype.toString = () => {
// 1.定义变量
let current = this.head
let listString = ''

// 2.循环获取一个个的节点
while (current) {
listString += current.data + ' '
current = current.next //千万不要忘了拼接完一个节点数据之后,让current指向下一个节点
}
return listString
}

// 三.实现insert方法
LinkList.prototype.insert = (position, data) => {
//理解positon的含义:position=0表示新界点插入后要成为第1个节点,position=2表示新界点插入后要成为第3个节点
//1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
if (position < 0 || position > this.length) {
return false
}
//2.根据data创建newNode
let newNode = new Node(data)

//3.插入新节点
//情况1:插入位置position=0
if (position == 0) {
// 让新节点指向第一个节点
newNode.next = this.head
// 让head指向新节点
this.head = newNode
//情况2:插入位置position>0(该情况包含position=length)
} else {
let index = 0
let previous = null
let current = this.head
//步骤1:通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
while (index++ < position) {
//步骤2:在current指向下一个节点之前,让previous指向current当前指向的节点
previous = current
current = current.next
}
// 步骤3:通过变量current(此时current已经指向position位置的后一个节点),使newNode指向position位置的后一个节点
newNode.next = current
//步骤4:通过变量previous,使position位置的前一个节点指向newNode
previous.next = newNode

//我们无法直接操作链表中的节点,但是可以通过变量指向这些节点,以此间接地操作节点;
}
//4.新节点插入后要length+1
this.length += 1

return true
}

//四.实现get方法
LinkList.prototype.get = (position) => {
//1.越界判断
// 当position = length时,取到的是null所以0 =< position < length
if (position < 0 || position >= this.length) {
return null
}
//2.获取指定的positon位置的后一个节点的data
//同样使用一个变量间接操作节点
let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
return current.data
}

//五.实现indexOf方法
LinkList.prototype.indexOf = (data) => {
//1.定义变量
let current = this.head
let index = 0

//2.开始查找:只要current不指向null就一直循环
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}

//3.遍历完链表没有找到,返回-1
return -1
}

//六.实现update方法
LinkList.prototype.update = (position, newData) => {
//1.越界判断
//因为被修改的节点不能为null,所以position不能等于length
if (position < 0 || position >= this.length) {
return false
}
//2.查找正确的节点
let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
//3.将position位置的后一个节点的data修改成newData
current.data = newData
//返回true表示修改成功
return true
}

//七.实现removeAt方法
LinkList.prototype.removeAt = (position) => {
//1.越界判断
if (position < 0 || position >= this.length) {
return null
}
//2.删除元素
//情况1:position = 0时(删除第一个节点)
let current = this.head
if (position == 0) {
//情况2:position > 0时
this.head = this.head.next
} else {
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
//循环结束后,current指向position后一个节点,previous指向current前一个节点
//再使前一个节点的next指向current的next即可
previous.next = current.next
}
//3,length-1
this.length -= 1

//返回被删除节点的data,为此current定义在最上面
return current.data
}

/*-------------其他方法的实现--------------*/
//八.实现remove方法
LinkList.prototype.remove = (data) => {
//1.获取data在列表中的位置
let position = this.indexOf(data)
//2.根据位置信息,删除结点
return this.removeAt(position)
}

//九.实现isEmpty方法
LinkList.prototype.isEmpty = () => {
return this.length == 0
}

//十.实现size方法
LinkList.prototype.size = () => {
return this.length
}
}

使用 ES6 实现

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
// 单向链表
export class Node {
constructor(element) {
// 保存元素
this.element = element
// 指向下一个节点
this.next = null
}
}

export class LinkedList {
constructor() {
this.head = null
this.length = 0
}

append(element) {
const newNode = new Node(element)
if (!this.head) {
this.head = newNode
} else {
let current = this.head
while (current.next) {
current = current.next
}
current.next = newNode
}
this.length++
}

insert(position, element) {
if (position < 0 || position > this.length - 1) return false
const newNode = new Node(element)
if (position === 0) {
newNode.next = this.head
this.head = newNode
} else {
let index = 0
let current = this.head
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
previous.next = newNode
newNode.next = current
}
this.length++
return true
}

get(position) {
if (position < 0 || position > this.length - 1) return null
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
return current.element
}

indexOf(element) {
let current = this.head
let index = 0
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
return -1
}

removeAt(position) {
if (position < 0 || position > this.length - 1) return null
let current = this.head
if (position === 0) {
this.head = current.next
} else {
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}

// update (position, element) {
// if (position < 0 || position >= this.length) return false
// let current = this.head
// let index = 0
// while (index++ < position) {
// current = current.next
// }
// current.element = element
// return true
// }

update(position, element) {
const result = this.removeAt(position)
this.insert(position, element)
return result
}

remove() {
const index = this.indexOf(element)
if (index === -1) return
this.removeAt(index)
}

isEmpty() {
return this.length === 0
}

size() {
return this.length
}
}