跳到主要内容位置

链表

链表和数组类似,是一种线性的数据结构,与数组不同的是,链表中的数据在内存中并不是顺序存储的,而是通过在链表的每个元素中,保存指向下一个元素的引用,来找到下一个元素。 这里的元素我们把它叫作节点,节点后面的节点我们把它叫作后继节点,节点前边的节点我们把它叫作前置节点。 链表的这种特性让我们无法通过索引直接访问节点,但是能够快速的删除和插入节点,因为只需要修改节点的引用。

应用

链表的应用场景有:分布式节点(例如 P2P),文件系统,或作为其它数据结构(如队列)的基础结构。

分类

常用的链表种类有:

  • 单链表,单链表是链表的最简单的形式,每个节点都指向下一个节点。
  • 双向链表:双向链表在单链表的基础上,每个节点还指向上一个节点。
  • 循环列表:在循环列表中,链表的尾部节点会指向头部节点,如果是双向循环列表,头部节点还会指向尾部节点。

常用操作

这个视频我们看一下简单的单链表的操作和实现。对于一个单链表,我们只需要保存头部节点的引用,就能找到所有节点,所有的操作都是围绕头部节点操作的。单链表的常见操作有:

  • 查找节点,给定一个值,找到对应的节点。
  • 在指定节点后面插入新节点,先找到对应位置的节点,让它指向新节点,再让新节点指向查找到的节点后面的节点。
  • 在尾部添加节点,找到尾部节点,让尾部节点的下一个节点指向新节点。
  • 在头部之前插入节点,让新节点的下一个节点指向原头部节点,再把头部节点引用设置为新的节点。
  • 删除指定节点,先找到要删除的节点的前置节点,让它指向要删除的节点的后继节点。
    • 如果删除的是头部节点,还需要把头部节点引用设置为原头部节点后面的节点
  • 删除头部节点,把头部节点的引用设置为下一个节点。
  • 删除尾部节点,找到尾部节点之前的节点,把它的指向设置为空。
  • 遍历链表:从头到尾访问链表中的每一个节点。

JavaScript 实现

基于链表数据结构的特点,我们可以使用一个类来表示一个节点,这里的 Node class 包含两个属性:

  • value 节点的数据。
  • next 对下一个节点的引用。

这里的 next 的值也是一个 Node 对象,所以这是一个递归的结构。

class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}

之后定义链表 class:

class LinkedList {
constructor(value) {
this.head = new Node(value);
}
}

因为 Node 是递归的结构,对于单链表,我们只需要知道头节点的引用就可以了,所有的节点查找、插入和删除都需要通过头节点来操作,在新建一个链表时,我们通过构造函数接收头节点的值,创建一个 Node 对象,然后保存在 head 属性中,head 就是头部节点的引用。

查找节点

接下来定义查找节点的代码,findNode() ,方法接收要查找的值作为参数,返回查找到的节点,如果没找到则返回 null:

findNode(value) {
let currentNode = this.head;
while (currentNode.value !== value) {
currentNode = currentNode.next;
}
if (!currentNode) {
return null;
}
return currentNode;
}

在这个函数里,我们用一个临时变量 currentNode 来保存当前遍历的到的节点,默认为头节点,然后在循环中与 value 值进行比对,如果值不相等,说明还没找到,那么就把 currentNode 设置为下一个节点继续比对,如果值相等,那么 while 循环就会退出,此时的 currentNode 就是找到的节点。如果最后 currentNode 返回了 null,说明访问到了尾部节点的 next,但仍然没找到对应的值。

在指定位置插入节点

下面是在指定位置插入节点的方法,insertAfter(),这个方法接收两个参数,第一个指定在哪个节点的后面插入,这里接收节点的值,第二参数是新节点的值:

  insertAfter(value, newValue) {
const newNode = new Node(newValue);
const currentNode = this.findNode(value);

newNode.next = currentNode.next;
currentNode.next = newNode;
}

在这个方法里面,我们先创建新节点的对象,然后调用 findNode() 方法找到第一个参数 value 值对应的节点,之后把新节点的 next 指向这个节点的后继节点,再把这个节点的后继节点指向新节点,这样新节点就插入到指定节点,以及指定节点的后继节点的中间了。

在尾部追加节点

再来看在链表的尾部追加节点的方法,append(),这个方法接收一个 value 作为参数,指定新节点的值:

append(value) {
const newNode = new Node(value);
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}

在方法中,根据 value 创建一个新节点,然后遍历整个链表,找到尾部节点,这里的逻辑和 findNode() 的类似,不过 while 循环中判断的是 curretNode.next 是否为空,也就是说遍历到的节点如果没有后继节点,那么它就是尾部节点了,最后把尾部节点的 next 指向新节点,这样就完成了在尾部追加节点操作了。

在头部插入节点

再定义从头部插入节点的方法,prepend(),它也接收一个值作为参数,代表新节点的值:

prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
}

在这个方法里,根据 value 创建节点对象,然后让它的 next 指向现有的头部节点,然后把当前对头节点的引用,head,指向这个新创建的节点,这一步是必须的,否则 head 指向的还是原来的头节点,导致插入失败。

删除指定节点

我们来看删除指定节点的方法,remove(),它接收一个 value 参数,即要删除的节点值:

remove(value) {
let currentNode = this.head;
let previousNode = null;

while (currentNode.value !== value) {
previousNode = currentNode;
currentNode = currentNode.next;
}

if (currentNode === this.head) {
this.head = currentNode.next;
} else {
previousNode.next = currentNode.next;
}
}

在方法里,我们需要两个临时变量,一个保存查找到的要删除的节点,一个保存要删除的节点的前置节点,因为删除一个节点需要让该节点的前置节点指向该节点的后置节点。利用 while 循环,找到要删除的节点和它的前置节点,后面有一个 if 判断,如果要删除的是头节点,那么直接让 head 指向它后面的节点就可以了,如果不是头节点,那么就让前置节点指向要删除的节点的后继节点。

删除头部节点

删除头部节点的方法比较简单,我们定义 removeHead()方法,它不接收参数,因为我们知道要删除头部节点,在里边直接让 head 指向头节点的下一个节点:

removeHead() {
this.head = this.head.next;
}

删除尾部节点

删除尾部节点的方法与删除指定节点的方法类似,我们定义 removeTail 方法,它也不接收参数:

  removeTail() {
let currentNode = this.head;
let previousNode = null;
while (currentNode.next) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = null;
}

在这个方法中,我们找到尾部节点的前置节点,直接把它的 next 设置为空就可以了。

遍历链表

遍历链表的代码和查找节点的几乎一样,在这个 traverse() 方法中,利用 while 循环直接打印出遍历到的节点的值,这样就完成了遍历:

  traverse() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}

运行示例

我们使用 LinkedList 类来编写一些单链表的操作示例,首先我们初始化一个链表,把头部节点的值设置为 1,此时链表只有一个节点,值为 1:

let list = new LinkedList(1); // 1

然后调用 append() 方法追加 2、3、4 到链表的尾部,此时链表有 4 个节点,分别为 1, 2, 3, 4:

list.append(2);
list.append(3);
list.append(4);
// 1 -> 2 -> 3 -> 4

调用 insertAfter(),传递参数 2 和 5,在节点 2 的后面插入一个节点 5,此时链表有 5 个节点,分别是 1 2 5 3 4:

list.insertAfter(2, 5);

调用 prepend(),传递参数 6,在头部节点前边插入节点 6,此时链表有 6 个节点,分别是 6 1 2 5 3 4:

list.prepend(6);

调用 remove() 方法,传入参数 3,删除值为 3 的节点,此时链表有 5 个节点,分别是 6 1 2 5 4:

list.remove(3);

调用 removeHead() 方法删除头部节点,此时链表有 4 个节点,分别是 1 2 5 4:

list.removeHead();

调用 removeTail() 删除尾部节点,此时链表有 3 个节点,分别是 1 2 5:

list.removeTail();

小结

好了,这个就是单链表数据结构的定义、操作和 JavaScript 实现,对于双向链表我们可以在 Node class 中再用一个 pre 属性保存前置节点的引用,对于循环列表,我们可以在 LinkedList 中再定义一个 tail 属性保存尾部节点,并让尾部节点的 next 属性指向 head 节点,双向循环列表则再让 head 的 pre 指向 tail 就可以了,相关的操作你可一自己实现一下。 这节课你学会了吗?如果有帮助请三连,想学更多有用的前端开发知识,请关注峰华前端工程师,感谢观看!