链表
相比数组，链表(
Linked List)是一种稍微复杂一点的数据结构，掌握起来也要比数组稍难一些。链表是通过“指针”将一组零散的内存块串联起来使用。数组的线性序是由数组的下标来决定的，而链表的的顺序是由各个对象中的指针来决定。在多数编程语言中，数组的长度是固定的，一旦被填满，要再加入数据将会变得非常困难。在数组中，添加和删除元素也比较麻烦，因为需要把数组中的其他元素向前或向后移动。
前面介绍数组的章节说过，JavaScript 的数组被实现成了对象，与 Java 相比，效率偏低。
在实际开发中，不能单靠复杂度就决定使用哪个数据结构，没有一种数据结构是完美的，否则其他的数据结构不都被淘汰了。
上面的图中，
Are 跟在 We 的后面，而不是说 Are 是这个链表的第二个元素。遍历该链表，就是顺着指针，从链表的首元素走到尾元素。链表的结构可以由很多种，它可以是单链表或双链表，也可以是已排序的或未排序的，环形的或非环形的。如果一个链表是单向的，那么链表中的每个元素没有指向前一个元素的指针。已排序的和未排序的链表较好理解。
单链表
单链表
循环链表
循环链表和单向链表的区别在于，单链表的尾元素指向的是 Null，而循环链表的尾元素指针是指向链表的头部元素。
和数组一样，链表也支持数据的查找、插入和删除。
由于链表是非连续的，想要访问第 i 个元素就没数组那么方便了，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。
数组在插入或删除元素时，为了保证数据的连续性，需要对原有的数据进行挪动。然而链表在插入或删除时，不要挪动原来的数据，因为链表的数据本身就是非连续的空间，因此在链表中插入、删除数据是非常快的。
如何设计一个链表
我们设计的链表包含两个类。
Node 类用来表示节点，LinkedList 类提供节点插入、删除和查找。- Node
1
class Node {
2
constructor(el) {
3
this.el = el;
4
this.next = null;
5
}
6
}
Copied!
- LinkedList
1
class LinkedList {
2
constructor() {
3
this.head = new Node('head');
4
}
5
6
// 用于查找
7
find() {
8
9
}
10
11
// 插入节点
12
insert() {
13
14
}
15
16
// 删除节点
17
remove() {
18
19
}
20
}
Copied!
LinkedList 类提供了所有对链表进行操作的方法。在构造函数中，我们用一个 Node 对象来保存该链表的头节点。头节点 head 的 next 属性被初始化为
null，每当调用 insert 方法时，next 就会指向新的元素。插入新节点
如果要在链表中插入新节点，需要说明在哪个节点前或后插入。先考虑单链表的情况，在后面插入，只需要知道在哪里插入和插入的元素是啥。
在已知的节点后面插入元素，需要先找到这个节点的位置，因此也需要提供一个
find 方法来遍历链表，查找数据。1
function find() {
2
// 从链表的头节点开始遍历
3
let currentNode = this.head;
4
while (currentNode && currentNode.el !== item) {
5
currentNode = currentNode.next;
6
}
7
return currentNode;
8
}
Copied!
上面的方法演示了如何在链表上查找元素，如果没找到就把当前指针往后移，找到了就返回改元素，找不到就算了直接返回
null。找到元素之后，就这个把新元素插入到链表当中去了。如下图所示，我们先创建一个新节点(X)，把新节点的
next 指针指向“后面”的节点的 next 指针对应的节点(可能有点绕，看图)，再把“后面”节点的 next 指针指向该新节点，一个完美的插入就完成了。
1
function insert(el, item) {
2
const newNode = new Node(el);
3
const currentNode = this.find(item);
4
// 将 X 的 next 指向 B 的 next
5
newNode.next = currentNode.next;
6
currentNode.next = newNode;
7
}
Copied!
删除节点
从链表中删除节点时，和插入节点类似，首先需要找到相应的节点前一个节点，找到节点之后，让他的 next 指针不再指向待删除的节点，而是指向待删除节点的下一个节点。
如图所示，我们需要删除的是 C 节点，让 B 的 next 指针指向 C 的下一个节点，也就是 D，这样就完成了一个删除的操作。现在来看下代码如何实现。
注意：我们这次找的是待删除节点的前一个节点，所以先来定义一个findPrev方法
1
function findPrev(item) {
2
let node = this.head;
3
while (node.next !== null && node.next.el !== item) {
4
node = node.next;
5
}
6
return node;
7
}
Copied!
接下来来实现
remove1
function remove(item) {
2
const prevNode = this.findPrev(item);
3
if (prevNode.next !== null) {
4
// 指向下一个元素，这行代码很关键
5
prevNode.next = prevNode.next.next;
6
}
7
}
Copied!
- 完整代码
1
// 定义单个节点
2
class Node {
3
constructor(el) {
4
this.el = el;
5
this.next = null;
6
}
7
}
8
9
class LinkedList {
10
constructor() {
11
this.head = new Node('head');
12
}
13
14
// 用于查找
15
find(item) {
16
let node = this.head;
17
while (node !== null && node.el !== item) {
18
node = node.next;
19
}
20
return node;
21
}
22
23
findPrev() {
24
let node = this.head;
25
while (node.next !== null && node.next.el !== item) {
26
node = node.next;
27
}
28
return node;
29
}
30
31
// 插入节点
32
insert(el, item) {
33
const newNode = new Node(el);
34
const currentNode = this.find(item);
35
newNode.next = currentNode.next;
36
currentNode.next = newNode;
37
}
38
39
// 删除节点
40
remove(item) {
41
const prevNode = this.findPrev(item);
42
if (prevNode.next !== null) {
43
// 指向下一个元素，这行代码很关键
44
prevNode.next = prevNode.next.next;
45
}
46
}
47
}
Copied!
双向链表
双向链表看字面意思，它有两个方向，除了 next 指针指向下一个元素之外，还多了一个 prev 的指针用来指向前面的元素。
我们发现，单链表尽管可以通过前一个元素可以找到下一个元素，但是后面的元素不知道自己前面的是谁。那么如何来解决这个问题呢？其实很简单，只需要再给 Node 添加一个
prev 的指针就可以解决问题了。储存同样的数据，双向链表要比单链表占用更多的内存空间。我们知道空间可以换时间，双向链表往往会比单链表更加灵活。
如何实现一个双链表
和单链表类似，在原有的
Node 基础上，增加一个 prev 指针。1
class Node {
2
constructor(el) {
3
this.el = el;
4
this.prev = null;
5
this.next = null;
6
}
7
}
Copied!
双向链表的查找和单链表的查找一样，这边不做重复的说明。
实现双向链表的插入和单链表非常类似，多了一个
prev 指针，我们对之前的代码稍作修改：1
function insert(el, item) {
2
const newNode = new Node(el);
3
const currentNode = this.find(item);
4
// 将 X 的 next 指向 B 的 next (C)
5
newNode.next = currentNode.next;
6
// 将 X 的 prev 指向 B
7
nextNode.prev = currentNode;
8
// 将 B 的 next 指向 X
9
currentNode.next = newNode;
10
// 将 C 的 prev 指向 X
11
currentNode.next.prev = newNode;
12
}
Copied!
双向链表的删除比单链表更加简单，不需要再定义
findPrev方法，话不多说，看图看代码。
1
function remove(item) {
2
const node = this.find(item);
3
node.prev.next = node.next;
4
node.next.prev = node.prev;
5
node.next = null;
6
node.prev = null;
7
}
Copied!
在实际面试过程中，还需要留意边界的情况。写完代码后，问自己 4 个问题：
- 如果链表为空，代码会不会报错？
- 如果只有一个元素，是否会抛异常？
- 两个元素呢？
- 在头部和尾部插入或删除，代码是否还可以正常工作？
下面的表列出零数组和链表在使用时的复杂度差异，在实际应用时，可以根据实际情况来选择。一般来说应用于两种场景：
- 插入和删除非常频繁，并且想要改善
- 不知道有多少元素在，每当有新的元素就链到表的最后面
时间复杂度
数组
链表
插入、删除
随机访问
本章节分为 3 个部分：
- Part 1
- 回文链表
- 环形链表
- 删除链表中的节点
- Part 2
- 反转链表
- 删除链表的倒数第N个节点
- 合并两个有序链表
- 两数相加
- Part 3
- 排序链表
- 相交链表
- 奇偶链表
阅读完本章节，你将有以下收获：
- 了解各种链表的结构
- 可以在链表中插入、删除、移动元素
- 能够解决一些经典的链表问题
复制链接
内容