前端进阶之从零到一实现单向 & 双向链表

前言

前端工程师对于算法和数据结构这块的知识的掌握程度，是进阶高级工程师的非常重要的标志之一，为了总结一下数据结构和算法方面的知识，笔者今天继续把链表这一块的知识补上，也作为自己知识体系的一个梳理，笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章，如果感兴趣或者想进阶高级的朋友们可以参考学习一下： JavaScript 中的二叉树以及二叉搜索树的实现及应用.

你将收获

链表的概念和应用
原生javascript实现一条单向链表
原生javascript实现一条个双单向链表
链表和数组的对比及优缺点

正文

1. 链表的概念和应用

链表是一种线性表数据结构，由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

以上概念用图表示为以下结构：链表是非连续的，所以说从底层存储结构上看，它不需要一整块连续的存储空间，而是通过“指针”将一组零散的数据单元串联起来成为一个整体。链表也有几种不同的类型：单向链表，双向链表，循环链表。上图就是一种单向链表。由其定义不难发现双向链表无非就是每个节点加上了前后节点的指针引用，如下图所示：那什么是循环链表呢？循环链表本质上是一种特殊的单向链表，唯一的区别就在于它的尾结点指向了链表的头结点，这样首尾相连，形成了一个环，所以叫做循环链表。如下图所示：当然我们还可以扩展出双向循环链表，这里就不一一举例了。总之链表结构在计算机底层语言中应用的比较多，当我们在用高级语言做编程时可能不会察觉，比如我们用javascript敲js的时候，其实我们在深入了解链表之后我们就会发现链表有很多应用场景，比如LRU 缓存淘汰，最近消息推送等。

举个更接地气的，当我们在用PS画图时软件提供了一个动作面板，可以记录用户之前的操作记录，并批量执行动作，或者当我们在使用编辑器时的回退撤销功能等，用链表结构来存储状态信息还是比较方便的。

最近比较火的react hooks API，其结构也是一个链表型的数据结构，所以学习链表还是非常有帮助的。读到这里可能还是有点懵，接下来我们先用js实现一个链表，这样有助于理解链表的本质，后面笔者会总结一下链表和数组的对比以及优劣势，方便大家对链表有一个更加直观的认识。

2.原生javascript实现一条单向链表

在上面一节介绍的链表结构中大家可能对链表有了初步的认识，因为javascript中没有链表的数据结构，为了模拟链表结构，我们可以通过js面向对象的方式实现一个链表结构及其API，具体设计如下：有了以上需求点之后，这个链表才是基本可用的链表，那么我们一步步来实现它把。

2.1 定义链表结构

为了实现链表以及链表的操作，首先我们需要先定义链表的基本结构，第一步就是定义节点的数据结构。我们知道一个节点会有自己的值以及指向下一个节点的引用，所以可以这样定义节点：

1let Node = function(el) {
2      this.el = el;
3      this.next = null;
4 }

接下来我们定义一下链表的基本骨架：

1// 单向链表, 每一个元素都有一个存储元素自身的节点和一个指向下一个元素引用的节点组成
2function linkedList() {
3  let Node = function(el) {
4      this.el = el;
5      this.next = null;
6  }
7  let length = 0
8  let head = null  // 用来存储第一个元素的引用
9
10  // 尾部添加元素
11  this.append = (el) => {};  
12  //插入元素
13  this.insert = (pos, el) => {};  
14  // 移除指定位置的元素
15  this.removeAt = (pos) => {};  
16  // 移除指定节点
17  this.remove = (el) => {};    
18  // 查询节点所在位置
19  this.indexOf = (el) => {};  
20  // 判断链表是否为空
21  this.isEmpty = () => {};  
22  // 返回链表长度
23  this.size = () => {};  
24  // 将链表转化为数组返回
25  this.toArray = () => {}; 
26}

由以上代码我们可以知道链表的初始长度为0，头部元素为null，接下来我们实现添加节点的功能。

2.2 实现添加节点

追加节点的时候首先需要知道头部节点是否存在，如果不存在直接赋值，存在的话则从头部开始遍历，直到找到下一个节点为空的节点，再赋值，并将链表长度+1，代码如下：

1// 尾部添加元素
2this.append = (el) => {
3    let node = new Node(el),
4        current;
5    if(!head) {
6      head = node
7    }else {
8      current = head;
9      while(current.next) {
10        current = current.next;
11      }
12      current.next = node;
13    }
14    length++
15};

2.3 实现插入节点

实现插入节点逻辑首先我们要考虑边界条件，如果插入的位置在头部或者比尾部位置还大，我们就没必要从头遍历一遍处理了，这样可以提高性能，所以我们可以这样处理：

1//插入元素
2this.insert = (pos, el) => {
3    if(pos >=0 && pos <= length) {
4      let node = new Node(el),
5          previousNode = null,
6          current = head,
7          curIdx = 0;
8      if(pos === 0) {
9        node.next = current;
10        head = node;
11      }else {
12        while(curIdx++ < pos) {
13          previousNode = current;
14          current = current.next;
15        }
16        node.next = current;
17        previousNode.next = node;
18        length++;
19        return true
20      }
21    }else {
22      return false
23    }
24};

2.4 根据节点的值查询节点位置

根据节点的值查询节点位置实现起来比较简单，我们只要从头开始遍历，然后找到对应的值之后记录一下索引即可：

1// 查询节点所在位置
2this.indexOf = (el) => {
3    let idx = -1,
4        curIdx = -1,
5        current = head;
6    while(current) {
7      idx++
8      if(current.el === el) {
9        curIdx = idx
10        break;
11      }
12      current = current.next;
13    }
14    return curIdx
15};

这里我们之所以要用idx和curIdx两个变量来处理，是因为如果用户传入的值不在链表里，那么idx的值就会有问题，所以用curIdx来保证准确性。

2.5 移除指定位置的节点

移除指定位置的节点也需要判断一下边界条件，可插入节点类似，但要注意移除之后一定要将链表长度-1，代码如下：

1 // 移除指定位置的元素
2this.removeAt = (pos) => {
3    // 检测边界条件
4    if(pos >=0 && pos < length) {
5      let previousNode = null,
6               current = head,
7               curIdx = 0;
8      if(pos === 0) {
9        // 如果pos为第一个元素
10        head = current.next
11      }else {
12        while(curIdx++ < pos) {
13          previousNode = current;
14          current = current.next;
15        }
16        previousNode.next = current.next;
17      }
18      length --;
19      return current.el
20    }else {
21      return null
22    }
23};

2.6 移除指定节点

移除指定节点实现非常简单，我们只需要利用之前实现好的查找节点先找到节点的位置，然后在用实现过的removeAt即可，代码如下：

1  // 移除指定节点
2this.remove = (el) => {
3  let idx = this.indexOf(el);
4  this.removeAt(idx);
5};

2.7 获取节点长度

这里比较简单，直接上代码：

1// 返回链表长度
2this.size = () => {
3  return length
4};

2.8 判断链表是否为空

判断链表是否为空我们只需要判断长度是否为零即可：

1// 返回链表长度
2this.size = () => {
3  return length
4};

2.9 打印节点

打印节点实现方式有很多，大家可以按照自己喜欢的格式打印，这里笔者直接将其打印为数组格式输出，代码如下：

1// 将链表转化为数组返回
2this.toArray = () => {
3    let current = head,
4        results = [];
5    while(current) {
6      results.push(current.el);
7      current = current.next;
8    }
9    return results
10};

这样，我们的单向链表就实现了，那么我们可以这么使用：

1let link = new linkedList()
2// 添加节点
3link.append(1)
4link.append(2)
5// 查找节点
6link.indexOf(2)
7// ...

3.原生javascript实现一条个双单向链表

有了单向链表的实现基础，实现双向链表也很简单了，我们无非要关注的是双向链表的节点创建，这里笔者实现一个例子供大家参考：

1let Node = function(el) {
2      this.el = el;
3      this.previous = null;
4      this.next = null;
5 }
6let length = 0
7let head = null  // 用来存储头部元素的引用
8let tail = null  // 用来存储尾部元素的引用

由代码可知我们在节点中会有上一个节点的引用以及下一个节点的引用，同时这里笔者添加了头部节点和尾部节点方便大家操作。大家可以根据自己的需求实现双向链表的功能，这里笔者提供一份自己实现的代码，可以参考交流一下：

1// 双向链表, 每一个元素都有一个存储元素自身的节点和指向上一个元素引用以及下一个元素引用的节点组成
2function doubleLinkedList() {
3  let Node = function(el) {
4      this.el = el;
5      this.previous = null;
6      this.next = null;
7  }
8  let length = 0
9  let head = null  // 用来存储头部元素的引用
10  let tail = null  // 用来存储尾部元素的引用
11
12  // 尾部添加元素
13  this.append = (el) => {
14    let node = new Node(el)
15    if(!head) {
16      head = node
17    }else {
18      tail.next = node;
19      node.previous = tail;
20    }
21    tail = node;
22    length++
23  };  
24  // 插入元素
25  this.insert = (pos, el) => {
26    if(pos >=0 && pos < length) {
27      let node = new Node(el);
28      if(pos === length - 1) {
29        // 在尾部插入
30        node.previous = tail.previous;
31        node.next = tail;
32        tail.previous = node;
33        length++;
34        return true
35      }
36      let current = head,
37          i = 0;
38      while(i < pos) {
39        current = current.next;
40        i++
41      }
42      node.next = current;
43      node.previous = current.previous;
44      current.previous.next = node;
45      current.previous = node;
46      length ++;
47      return true    
48    }else {
49      throw new RangeError(`插入范围有误`)
50    }
51  };  
52  // 移除指定位置的元素
53  this.removeAt = (pos) => {
54    // 检测边界条件
55    if(pos < 0 || pos >= length) {
56      throw new RangeError(`删除范围有误`)
57    }else {
58      if(length) {
59        if(pos === length - 1) {
60          // 如果删除节点位置为尾节点,直接删除,节省查找时间
61          let previous = tail.previous;
62          previous.next = null;
63          length --;
64          return tail.el
65        }else {
66          let current = head,
67              previous = null,
68              next = null,
69              i = 0;
70          while(i < pos) {
71            current = current.next
72            i++
73          }
74          previous = current.previous;
75          next = current.next;
76          previous.next = next;
77          length --;
78          return current.el
79        }
80      }else {
81        return null
82      }
83    }
84  };  
85  // 移除指定节点
86  this.remove = (el) => {
87    let idx = this.indexOf(el);
88    this.removeAt(idx);
89  };
90  // 查询指定位置的链表元素
91  this.get = (index) => {
92    if(index < 0 || index >= length) {
93      return undefined
94    }else {
95      if(length) {
96        if(index === length - 1) {
97          return tail.el
98        }
99        let current = head,
100            i = 0;
101        while(i < index) {
102          current = current.next
103          i++
104        }
105        return current.el
106      }else {
107        return undefined
108      }
109    }
110  }
111  // 查询节点所在位置
112  this.indexOf = (el) => {
113    let idx = -1,
114        current = head,
115        curIdx = -1;
116    while(current) {
117      idx++
118      if(current.el === el) {
119        curIdx = idx;
120        break;
121      }
122      current = current.next;
123    }
124    return curIdx
125  };  
126  // 判断链表是否为空
127  this.isEmpty = () => {
128    return length === 0
129  };  
130  // 返回链表长度
131  this.size = () => {
132    return length
133  };  
134  // 将链表转化为数组返回
135  this.toArray = () => {
136    let current = head,
137        results = [];
138    while(current) {
139      results.push(current.el);
140      current = current.next;
141    }
142    return results
143  }; 
144}

4.链表和数组的对比及优缺点

实现完链表之后我们会对链表有更深入的认知，接下来我们进一步分析链表的优缺点。笔者将从3个维度来带大家分析链表的性能情况：

插入删除性能
查询性能
内存占用

我们先看看插入和删除的过程：由上图可以发现，链表的插入、删除数据效率非常高，只需要考虑相邻结点的指针变化，因为不需要移动其他节点，时间复杂度是 O(1)。

再来看看查询过程：我们对链表进行每一次查询时，都需要从链表的头部开始找起，一步步遍历到目标节点，这个过程效率是非常低的，时间复杂度是 O(n)。这方面我们使用数组的话效率会更高一点。

我们再看看内存占用。链表的内存消耗比较大，因为每个结点除了要存储数据本身，还要储存前后结点的地址。但是好处是可以动态分配内存。

另一方面，对于数组来说，也存在一些缺点，比如数组必须占用整块、连续的内存空间，如果声明的数组数据量过大，可能会导致“内存不足”。其次就是数组一旦需要扩容，会重新申请连续的内存空间，并且需要把上一次的数组数据全部copy到新的内存空间中。

综上所述，当我们的数据存在频繁的插入删除操作时，我们可以采用链表结构来存储我们的数据，如果涉及到频繁查找的操作，我们可以采用数组来处理。实际工作中很多底层框架的封装都是采用组合模式进行设计，一般纯粹采用某种数据结构的比较少，所以具体还是要根据所处环境进行适当的方案设计。

最后

如果想学习更多H5游戏, webpack，node，gulp，css3，javascript，nodeJS，canvas数据可视化等前端知识和实战，欢迎在公号《趣谈前端》加入我们的技术群一起学习讨论，共同探索前端的边界。