链表

相比数组,链表(Linked List)是一种稍微复杂一点的数据结构,掌握起来也要比数组稍难一些。链表是通过“指针”将一组零散的内存块串联起来使用。数组的线性序是由数组的下标来决定的,而链表的的顺序是由各个对象中的指针来决定。

在多数编程语言中,数组的长度是固定的,一旦被填满,要再加入数据将会变得非常困难。在数组中,添加和删除元素也比较麻烦,因为需要把数组中的其他元素向前或向后移动。

前面介绍数组的章节说过,JavaScript 的数组被实现成了对象,与 Java 相比,效率偏低。

在实际开发中,不能单靠复杂度就决定使用哪个数据结构,没有一种数据结构是完美的,否则其他的数据结构不都被淘汰了。

上面的图中,Are 跟在 We 的后面,而不是说 Are 是这个链表的第二个元素。遍历该链表,就是顺着指针,从链表的首元素走到尾元素。

链表的结构可以由很多种,它可以是单链表或双链表,也可以是已排序的或未排序的,环形的或非环形的。如果一个链表是单向的,那么链表中的每个元素没有指向前一个元素的指针。已排序的和未排序的链表较好理解。

单链表

单链表
循环链表

循环链表和单向链表的区别在于,单链表的尾元素指向的是 Null,而循环链表的尾元素指针是指向链表的头部元素。

和数组一样,链表也支持数据的查找、插入和删除。

由于链表是非连续的,想要访问第 i 个元素就没数组那么方便了,需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点。

数组在插入或删除元素时,为了保证数据的连续性,需要对原有的数据进行挪动。然而链表在插入或删除时,不要挪动原来的数据,因为链表的数据本身就是非连续的空间,因此在链表中插入、删除数据是非常快的。

如何设计一个链表

我们设计的链表包含两个类。Node 类用来表示节点,LinkedList 类提供节点插入、删除和查找。

  • Node

class Node {
constructor(el) {
this.el = el;
this.next = null;
}
}
  • LinkedList

class LinkedList {
constructor() {
this.head = new Node('head');
}
// 用于查找
find() {
}
// 插入节点
insert() {
}
// 删除节点
remove() {
}
}

LinkedList 类提供了所有对链表进行操作的方法。在构造函数中,我们用一个 Node 对象来保存该链表的头节点。

头节点 head 的 next 属性被初始化为 null,每当调用 insert 方法时,next 就会指向新的元素。

插入新节点

如果要在链表中插入新节点,需要说明在哪个节点前或后插入。先考虑单链表的情况,在后面插入,只需要知道在哪里插入和插入的元素是啥。

在已知的节点后面插入元素,需要先找到这个节点的位置,因此也需要提供一个 find 方法来遍历链表,查找数据。

function find() {
// 从链表的头节点开始遍历
let currentNode = this.head;
while (currentNode && currentNode.el !== item) {
currentNode = currentNode.next;
}
return currentNode;
}

上面的方法演示了如何在链表上查找元素,如果没找到就把当前指针往后移,找到了就返回改元素,找不到就算了直接返回 null

找到元素之后,就这个把新元素插入到链表当中去了。如下图所示,我们先创建一个新节点(X),把新节点的 next 指针指向“后面”的节点的 next 指针对应的节点(可能有点绕,看图),再把“后面”节点的 next 指针指向该新节点,一个完美的插入就完成了。

function insert(el, item) {
const newNode = new Node(el);
const currentNode = this.find(item);
// 将 X 的 next 指向 B 的 next
newNode.next = currentNode.next;
currentNode.next = newNode;
}

删除节点

从链表中删除节点时,和插入节点类似,首先需要找到相应的节点前一个节点,找到节点之后,让他的 next 指针不再指向待删除的节点,而是指向待删除节点的下一个节点。

如图所示,我们需要删除的是 C 节点,让 B 的 next 指针指向 C 的下一个节点,也就是 D,这样就完成了一个删除的操作。现在来看下代码如何实现。

注意:我们这次找的是待删除节点的前一个节点,所以先来定义一个 findPrev 方法

function findPrev(item) {
let node = this.head;
while (node.next !== null && node.next.el !== item) {
node = node.next;
}
return node;
}

接下来来实现 remove

function remove(item) {
const prevNode = this.findPrev(item);
if (prevNode.next !== null) {
// 指向下一个元素,这行代码很关键
prevNode.next = prevNode.next.next;
}
}
  • 完整代码

// 定义单个节点
class Node {
constructor(el) {
this.el = el;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = new Node('head');
}
// 用于查找
find(item) {
let node = this.head;
while (node !== null && node.el !== item) {
node = node.next;
}
return node;
}
findPrev() {
let node = this.head;
while (node.next !== null && node.next.el !== item) {
node = node.next;
}
return node;
}
// 插入节点
insert(el, item) {
const newNode = new Node(el);
const currentNode = this.find(item);
newNode.next = currentNode.next;
currentNode.next = newNode;
}
// 删除节点
remove(item) {
const prevNode = this.findPrev(item);
if (prevNode.next !== null) {
// 指向下一个元素,这行代码很关键
prevNode.next = prevNode.next.next;
}
}
}

双向链表

双向链表看字面意思,它有两个方向,除了 next 指针指向下一个元素之外,还多了一个 prev 的指针用来指向前面的元素。

我们发现,单链表尽管可以通过前一个元素可以找到下一个元素,但是后面的元素不知道自己前面的是谁。那么如何来解决这个问题呢?其实很简单,只需要再给 Node 添加一个 prev 的指针就可以解决问题了。

储存同样的数据,双向链表要比单链表占用更多的内存空间。我们知道空间可以换时间,双向链表往往会比单链表更加灵活。

如何实现一个双链表

和单链表类似,在原有的 Node 基础上,增加一个 prev 指针。

class Node {
constructor(el) {
this.el = el;
this.prev = null;
this.next = null;
}
}

双向链表的查找和单链表的查找一样,这边不做重复的说明。

实现双向链表的插入和单链表非常类似,多了一个 prev 指针,我们对之前的代码稍作修改:

function insert(el, item) {
const newNode = new Node(el);
const currentNode = this.find(item);
// 将 X 的 next 指向 B 的 next (C)
newNode.next = currentNode.next;
// 将 X 的 prev 指向 B
nextNode.prev = currentNode;
// 将 B 的 next 指向 X
currentNode.next = newNode;
// 将 C 的 prev 指向 X
currentNode.next.prev = newNode;
}

双向链表的删除比单链表更加简单,不需要再定义 findPrev方法,话不多说,看图看代码。

function remove(item) {
const node = this.find(item);
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}

在实际面试过程中,还需要留意边界的情况。写完代码后,问自己 4 个问题:

  • 如果链表为空,代码会不会报错?

  • 如果只有一个元素,是否会抛异常?

  • 两个元素呢?

  • 在头部和尾部插入或删除,代码是否还可以正常工作?

下面的表列出零数组和链表在使用时的复杂度差异,在实际应用时,可以根据实际情况来选择。一般来说应用于两种场景:

  • 插入和删除非常频繁,并且想要改善

  • 不知道有多少元素在,每当有新的元素就链到表的最后面

时间复杂度

数组

链表

插入、删除

O(n)O(n)

O(1)O(1)

随机访问

O(1)O(1)

O(n)O(n)

本章节分为 3 个部分:

  • Part 1

    • 回文链表

    • 环形链表

    • 删除链表中的节点

  • Part 2

    • 反转链表

    • 删除链表的倒数第N个节点

    • 合并两个有序链表

    • 两数相加

  • Part 3

    • 排序链表

    • 相交链表

    • 奇偶链表

阅读完本章节,你将有以下收获:

  • 了解各种链表的结构

  • 可以在链表中插入、删除、移动元素

  • 能够解决一些经典的链表问题