js创建一条通用链表

曾经终败给现在 2022-05-20 20:14 142阅读 0赞

什么是「链表[科普][Link 1]」？

> 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

什么是「顺序存储结构[科普][Link 2]」？

> 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

多数高级语言的「数组」使用「顺序存储结构」，不过早期的 javascript 引擎用了「链式存储结构」。Chrome 的 V8 的数组使用了「顺序存储结构」与「链式存储结构」混合模式；大多数情况下，V8 下的数组是「顺序存储结构」，所以我们就假装 V8 的数组使用的是「顺序存储结构」吧！（-\_-! 心虚）

javascript 开发需要「链表」吗？自问自答  
大多数情况下 javascript 开发关心的是「数据的逻辑结构」而非「数据的存储结构」，似乎「链表」跟 javascript 开发没什么关系。But…「链表」在一些情况下能有效提升代码的性能，特别是在H5游戏的过程中。

假设有一个业务需要高频率地向一张「线性表[科普][Link 3]」插入或删除节点。通常笔者会用数组表示「线性表」，因为 javascript 的数组有一系列成熟好用的 APIs （如：unshift / push / shift / pop / splice 等）可以完成插入与删除节点的操作。但是数组（顺序存储结构）的 `unshift` & `shift` & `splice` 的算法时间复杂度是 O(n) ，这情况可能「链表」是更好的选择。

## 图解链表 ##

先看一下最简单的单向链表：

![单链表结构图][20171014-single-link.png]

往链表里插入一个节点：  
![插入节点][20171014-single-link-insert.gif]

剔除链表里的节点：  
![剔除节点][20171014-remove-node.gif]

往链表里插入一条链表：  
![插入链表][20171014-insert-chain.gif]

剪除链表的一段切片：  
![剪除切片][20171014-remove-chain.gif]

通过上面的图示，可以很清晰地了解到单链表的优势：插入节点或链表片段的算法时间复杂度为O(2)；删除节点或链表片段的算法时间复杂度为O(1)

## 实现双向链表 ##

「单向链表」效率虽然高，不过局限性比较大。所以笔者想实现的是「双向链表」。双向链表插入节点或链表的算法时间复杂度为 O(4)，删除节点或链表片段的算法时间复杂度为O(2)。  
双向链表的结构如下：

*  节点指针 ——「前驱」与「后继」
 *  链表指针 —— 「头指针」、「尾指针」和「游标指针」

![双向链表][20171014-double-chain.png]

用一个匿名对象作为链表上的节点，如下伪代码：

声明变量 `HEAD`, `TAIL`, `POINTER` & `length` 分别指代「头指针」，「尾指针」，「游标指针」和 「链表长度」，那么构建一个双向链表如下伪代码：

<table style="border:none;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;border-spacing:0px;"> 
 <tbody style="font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(102,102,102);line-height:1.6;text-align:right;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      1 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      2 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      3 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      4 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      5 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      6 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      7 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      8 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      9 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      10 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      11 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      12 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      13 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      14 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      15 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      16 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      17 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      18 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      19 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      20 
    </div></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(77,77,76);line-height:1.6;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> HEAD, TAIL, POINTER, length = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 创建一条长度为5的双向链表</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      [ 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">2</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">3</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>].forEach( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);">(<span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">data, index, arr</span>) =&gt;</span> { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> node = generateNode(data); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 第一个节点</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(index === 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      HEAD = node; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">else</span> { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 指定前驱后继指针</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      [node.prev, POINTER.next] = [POINTER, node]; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 最后一个节点</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      index === arr.length - 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span> &amp;&amp; (TAIL = node) 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 指向当前节点</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      POINTER = node; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      ++length; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      }); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 游标指针回退到头部</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      POINTER = HEAD; 
    </div></td> 
  </tr> 
 </tbody> 
</table>

链表结构本身是个很简单的结构，20行左右代码可以完成双向链表数据结构的构建。

## 定制 APIs ##

上一节虽然实现了「双向链表」的数据结构，但链表还处在很原始的状态，操作起来比较麻烦，为了方便操作链表得为链表量身定做一套 APIs。数组有一系列成熟且好用的 APIs，笔者想借鉴数组的 APIs 为链表定制以下的 APIs:

<table style="border:0px;font-family:'PingFang SC', 'Lantinghei SC', 'Microsoft Yahei', 'Hiragino Sans GB', 'Microsoft Sans Serif', 'WenQuanYi Micro Hei', sans;font-size:16px;vertical-align:baseline;border-spacing:0px;table-layout:fixed;color:rgb(51,51,51);background-color:rgb(255,255,255);"> 
 <thead style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Name</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Detail</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Name</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Detail</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Name</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Detail</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Name</th> 
   <th style="font-family:inherit;font-size:16px;vertical-align:baseline;text-align:center;color:rgb(51,51,51);background:rgb(241,241,241);">Detail</th> 
  </tr> 
 </thead> 
 <tbody style="font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">shift</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">unshift</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">pop</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">push</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;background-color:rgb(248,248,248);"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">slice</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">splice</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">concat</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">reverse</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">sort</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">indexOf</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">length<span style="border:0px;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;line-height:0;">[属性]</span></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">参见数组</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;background-color:rgb(248,248,248);"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">at</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">指针定位</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">prev</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">指针前移</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">next</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">指针后退</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">curr</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">当前指针</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">first</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">头节点</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">last</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">尾节点</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">remove</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">删除节点</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">clone</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">克隆链表</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;background-color:rgb(248,248,248);"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">insertAfter</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">插入节点</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">insertBefore</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">插入节点</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">insertChainAfter</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">插入链表</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">insertChainBefore</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">插入链表</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">HEAD<span style="border:0px;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;line-height:0;">[属性]</span></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">头指针</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">TAIL<span style="border:0px;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;line-height:0;">[属性]</span></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">尾指针</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">setHead</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">重置头指针</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">setTail</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">重置尾指针</td> 
  </tr> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;background-color:rgb(248,248,248);"> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">POINTER<span style="border:0px;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;line-height:0;">[属性]</span></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">游标指针（当前位置）</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">setPointer</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">设置当前指针</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
   <td style="font-style:inherit;font-family:inherit;font-size:16px;vertical-align:baseline;color:rgb(51,51,51);text-align:center;">-</td> 
  </tr> 
 </tbody> 
</table>

上表与数组同名的 APIs，表示用法与功能与数组一样。

为了突显「链表性」笔者添加了四个 `insert*`。`insert*` 的作用是向主链表指定位置插入节点或链表。APIs 不小心被笔者写多了，这里就不展开介绍它们的实现过程了。有兴趣的同学可以移步：[https://github.com/leeenx/es6-utils/blob/master/modules/Chain\_v2.js][https_github.com_leeenx_es6-utils_blob_master_modules_Chain_v2.js]

## 循环链表 ##

笔者以往都是用数组来模拟循环链表，如下：

<table style="border:none;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;border-spacing:0px;"> 
 <tbody style="font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(102,102,102);line-height:1.6;text-align:right;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      1 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      2 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      3 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      4 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      5 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      6 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      7 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      8 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      9 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      10 
    </div></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(77,77,76);line-height:1.6;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">Array</span>.prototype.next = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">function</span>(<span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);"></span>) </span>{ 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">var</span> cur = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">this</span>[ 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>]; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">this</span>.push( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">this</span>.shift()); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> cur; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">var</span> arr = [ 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">2</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">3</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">5</span>]; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">var</span> count = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">while</span>(count++ 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(200,40,41);">&lt;<span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">20)</span> { </span></span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">console.log</span>( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">arr.next</span>()); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

有了 `Chain` 类后，可以直接这样写：

[Link 1]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473?fr=aladdin
[Link 2]: https://baike.baidu.com/item/%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84/1347176?fr=aladdin
[Link 3]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%A1%A8/3228081?fr=aladdin
[20171014-single-link.png]: https://misc.aotu.io/leeenx/chain/20171014-single-link.png
[20171014-single-link-insert.gif]: https://misc.aotu.io/leeenx/chain/20171014-single-link-insert.gif
[20171014-remove-node.gif]: https://misc.aotu.io/leeenx/chain/20171014-remove-node.gif
[20171014-insert-chain.gif]: https://misc.aotu.io/leeenx/chain/20171014-insert-chain.gif
[20171014-remove-chain.gif]: https://misc.aotu.io/leeenx/chain/20171014-remove-chain.gif
[20171014-double-chain.png]: https://misc.aotu.io/leeenx/chain/20171014-double-chain.png
[https_github.com_leeenx_es6-utils_blob_master_modules_Chain_v2.js]: https://github.com/leeenx/es6-utils/blob/master/modules/Chain_v2.js