JS数据结构与算法 — 链表

链表(Linked-list)

在很多编程语言中，数组的长度都是固定的，如果数组已被数据填满，再要加入新的元素是非常困难的。而且，对于数组的删除和添加操作，通常需要将数组中的其他元素向前或者向后平移，这些操作也是十分繁琐的。

然而，JS中数组却不存在上述问题，主要是因为他们被实现了成了对象，但是与其他语言相比（比如C或Java），那么它的效率会低很多。 这时候，我们可以考虑使用链表(Linked-list) 来替代它，除了对数据的随机访问，链表几乎可以在任何可以使用一维数组的情况中。如果你正巧在使用C或者Java等高级语言，你会发现链表的表现要优于数组很多。

链表其实有许多的种类：单向链表、双向链表、单向循环链表和双向循环链表，接下来，我们基于对象来实现一个单向链表，因为它的使用最为广泛。

链表的定义

首先，要实现链表，我们先搞懂一些链表的基本东西，因为这很重要！ 链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链。下面我画了一个简单的链接结构图，方便大家理解。

链表结构图

其中，data中保存着数据，next保存着下一个链表的引用。上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。上图，值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。

由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。进行改造，链表就成了如下的样子：

有头节点的链表

向链表中插入一个节点的效率很高，需要修改它前面的节点(前驱)，使其指向新加入的节点，而将新节点指向原来前驱节点指向的节点即可。下面我将用图片演示如何在 data2 节点 后面插入 data4 节点。

插入节点

同样，从链表中删除一个节点，也很简单。只需将待删节点的前驱节点指向待删节点的，同时将待删节点指向null，那么节点就删除成功了。下面我们用图片演示如何从链表中删除 data4 节点。

删除节点

链表的设计

首先我们要创建一个链表类：

function LinkedList(){
    //各种属性和方法的声明
}

然后我们需要一种数据结构来保存链表里面的数据：

var Node=function(element){
this.element=element;
this.next=null;
}

Node类表示要添加的元素，他有两个属性， 一个是element，表示添加到链表中的具体的值； 另一个是next,表示要指向链表中下一个元素的指针。 接下来，我们需要给链表声明一些方法：

• append(element):向链表尾部添加一个新的元素；
• insert(position,element):向链表特定位置插入元素；
• remove(element):从链表移除一项；
• indexOf(element):返回链表中某元素的索引，如果没有返回-1；
• removeAt(position):从特定位置移除一项；
• isEmpty():判断链表是否为空，如果为空返回true,否则返回false;
• size():返回链表包含的元素个数；
• toString():重写继承自Object类的toString()方法，因为我们使用了Node类；

ES6版本实现，点击阅读原文

双向链表

尽管从链表的头节点遍历链表很简单，但是反过来，从后向前遍历却不容易。我们可以通过给Node类增加一个previous属性，让其指向前驱节点的链接，这样就形成了双向链表，如下图：

双向链表

此时，向链表插入一个节点就要更改节点的前驱和后继了，但是删除节点的效率提高了，不再需要寻找待删除节点的前驱节点了。

双向链表的实现要实现双向链表，首先需要给 Node 类增加一个 previous 属性： //节点类

function Node(element) {
    this.element = element;   //当前节点的元素
    this.next = null;         //下一个节点链接
    this.previous = null;     //上一个节点链接
}

循环链表

循环链表和单链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性执行它本身，即

head.next = head;这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表，如下图所示：

循环链表

原理相信你已经懂了，循环链表这里就不贴代码了，相信你自己能独立完成！ 参考： https://juejin.im/entry/59cb70995188256aa423b680 https://juejin.im/post/58287452570c3500587642b6