“ 在之前分享了什么是单向链表以及如何来实现它，今天我们接着来完善它，可能有点多，希望小伙伴们耐心看，当然有不懂可以在下面留言，我看到之后会尽力回答小伙伴们的问题（技术有限，哈哈哈）。话不多说冲冲冲。”
1. 链表的查找
首先我们来实现一下链表的查找，查找是很简单的，创建一个新节点，将头节点赋值给新节点，如果找到的话就返回保存该节点的数据，否则就调用next找下一个节点直到找到，如果最后循环完都没有找到就返回null。可能文字描述有点绕，别着急下面我画一张图给你解析一下就懂了。
链表查找过程图
不知道大伙看了这幅图后心中有个所以然没有，接下来就是公布代码的时候，有没有很激动哈哈图片图片。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| /**
* 查找链表
* @param nodeVal 查找节点值
*/
find (nodeVal) {
let currentNode = this.head; // 创建一个新节点，将头节点赋值给新节点
/**
* 注意在这里要记得先判断currentNode是否存在，
* 如果它为null时就不需要再做后面的判断，否则会报错
*/
while (currentNode && currentNode.data !== nodeVal) {
currentNode = currentNode.next;
}
return currentNode;
}
|
2. 链表的删除
接下来就是比较难一些的删除操作，其实说难也不难，只要你懂得链表的指向那么就轻而易举。老规矩先看一下我画的这幅图，然后再做解释可能要好理解有些。
链表删除过程图
在这里其实想要删除节点6，那么能想到的办法只能是改变next的指向，想要删除节点6，那么首先我们就需要知道节点6的前一个节点是谁，在这里是节点1，那么我们只需要将节点1的next指向指向到节点6的next指向，然后将节点6的next指向到null即可。
于是得出结论：首先找到需要删除的节点(deleteNode)，然后找到删除节点的前一个节点(preNode)，将前一个节点的next指向指向到删除节点的next指向(preNode.next = preNode.next.next)。说了这么多，那么我们首先应该写的方法是查找需要删除节点的上一个节点的方法findPreNode，得到的代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
| /**
* 查找上一个节点
* @param itemVal 当前节点值
*/
findPreNode (itemVal) {
let currentNode = this.head;
while (currentNode.next && currentNode.next.data !== itemVal) {
currentNode = currentNode.next;
}
return currentNode;
}
|
接下来再写remove删除方法，配合上面的find和findPreNode方法一起使用，得到如下所示代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| /**
* 删除节点
* @param deleteVal 需要删除的节点值
*/
remove (deleteVal) {
let preNode = this.findPreNode(deleteVal);
let deleteNode = this.find(deleteVal); // 通过删除节点的值找到删除节点
if (preNode.next) {
// 删除方法核心点，让上一个节点指向待删除节点的后一个节点
preNode.next = preNode.next.next;
deleteNode.next = null; // 将删除节点的next指向null
}
}
|
当我删除值为6的节点之后，查看链表list的值以及删除节点6的值如下图所示：
删除值为6的节点得到结果图
3. 链表的插入
了解了第二章节的删除之后，如果真的理解了的同学对于插入肯定有了自己的想法，我还是老规矩先放上自己画的图，然后再做相关解释。
链表的插入解析图
其实就是先找到在哪个节点(currentNode)后面插入新节点(newNode)，然后将新节点的next指向currentNode.next，然后再将currentNode节点的next指向新节点即可实现插入。
需要注意的是上面的顺序不要反了，反了的话由于指向原因会导致死循环，如果你要反着写的话可以使用一个temp临时变量来存储currentNode.next。接下来就是上代码的时刻：
1
2
3
4
5
6
7
8
9
10
11
| /**
* 添加节点
* @param newVal 新添加节点值
* @param itemVal 新节点需要在指定节点后添加，itemVal表示指定节点值
*/
insert (newVal, itemVal) {
let newNode = new Node(newVal);
let currentNode = this.find(itemVal); // 找到指定节点
newNode.next = currentNode.next;
currentNode.next = newNode;
}
|
比如在6后面添加7会得到如下图所示的链表结果图：
在6后面添加7得到的链表结果图
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
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
| // 链表---链表初始化时，初始化head节点
class NodeList {
constructor (head = null) {
this.head = head;
}
/**
* 查找链表
* @param nodeVal 查找节点值
*/
find (nodeVal) {
let currentNode = this.head; // 创建一个新节点，将头节点赋值给新节点
/**
* 注意在这里要记得先判断currentNode是否存在，
* 如果它为null时就不需要再做后面的判断，否则会报错
*/
while (currentNode && currentNode.data !== nodeVal) {
currentNode = currentNode.next;
}
return currentNode;
}
/**
* 查找上一个节点
* @param itemVal 当前节点值
*/
findPreNode (itemVal) {
let currentNode = this.head;
while (currentNode.next && currentNode.next.data !== itemVal) {
currentNode = currentNode.next;
}
return currentNode;
}
/**
* 删除节点
* @param deleteVal 需要删除的节点值
*/
remove (deleteVal) {
let preNode = this.findPreNode(deleteVal);
let deleteNode = this.find(deleteVal); // 通过删除节点的值找到删除节点
if (preNode.next) {
// 删除方法核心点，让上一个节点指向待删除节点的后一个节点
preNode.next = preNode.next.next;
deleteNode.next = null; // 将删除节点的next指向null
}
}
/**
* 添加节点
* @param newVal 新添加节点值
* @param itemVal 新节点需要在指定节点后添加，itemVal表示指定节点值
*/
insert (newVal, itemVal) {
let newNode = new Node(newVal);
let currentNode = this.find(itemVal); // 找到指定节点
newNode.next = currentNode.next;
currentNode.next = newNode;
}
// 链表中存在的节点数
size () {
let count = 0;
let currentNode = this.head;
while (currentNode) {
count++;
currentNode = currentNode.next;
}
return count;
}
// 清空该链表
clear () {
this.head = null; // 只需要将head的指向改为null即可
}
// 返回链表最后一个节点
getLast () {
let lastNode = this.head;
while (lastNode && lastNode.next) {
lastNode = lastNode.next;
}
return lastNode;
}
// 返回链表第一个节点
getFirst () {
return this.head;
}
}
// 需要存储节点数据的字段（data）和一个字段（next）指向下一个节点
class Node { // 链表节点
constructor (data) {
this.data = data; // 节点数据
this.next = null; // 下一个节点指针
}
}
const node1 = new Node(1);
const node2 = new Node(6);
const node3 = new Node(8);
const list = new NodeList(node1);
node1.next = node2;
node2.next = node3;
// list.remove(6);
list.insert(7, 6);
console.log('list', list);
|
上一篇文章如何实现一个简单的单向链表，没有看过的小伙伴记得看哟，觉得不错的同学记得三连哟，谢谢！
参考链接：数据结构与算法之单向链表
