本文通过实例描述了JS中算法和数据结构的链表。分享给大家参考，如下：

链表(Linked-list)

之前，我们讨论了如何使用堆栈和队列来存储数据。其实都是列表，底部存储的数据的数据结构都是数组。

但是数组并不总是最好的数据结构，因为在很多编程语言中，数组的长度是固定的，如果数组中充满了数据，就很难添加新元素。而且，对于数组的删除和添加操作，通常需要将数组中的其他元素向前或向后翻译，这些操作也非常繁琐。

但是JS中的数组并不存在上述问题，主要是因为它们是作为对象实现的，但是与其他语言(如C或Java)相比，它的效率要低很多。

这时，我们可以考虑用链表来代替它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况下。如果你碰巧使用C或Java等高级语言，你会发现链表的性能比数组好得多。

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

链表的定义

首先，要实现链表，首先要了解链表的一些基本的东西，因为它非常重要！

链表是一组节点，每个节点使用一个对象的引用来指向它的下一个节点。对另一个节点的引用称为链。下面我画一个简单的链接结构图，方便大家理解。

链表结构图

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

因为确定链表的起点比较麻烦，所以链表的很多实现都会在链表的前面增加一个特殊的节点，叫做head节点，代表链表的头部。在转换中，链接列表变成以下外观：

带有标题节点的链表

将节点插入链表非常有效。需要修改其前面的节点(前置节点)，使其指向新添加的节点，而新节点指向原前置节点所指向的节点。接下来，我将使用图片展示如何在data2节点之后插入data4节点。

插入节点

同样，从链表中删除一个节点也很简单。只需将待删节点的前驱节点指向待删节点，并将待删节点指向空，即可成功删除该节点。让我们展示如何从带有图片的链表中删除data4节点。

删除节点

链表的设计

，我们设计了LinkedList包含两个类，一个是Node类表示节点，另一个是linkedlist类提供一些插入节点、删除节点等操作。

节点类

Node类包含几个属性：element用于保存节点上的数据，next用于保存到下一个节点的链接。具体实现如下：

//节点功能节点(元素){this。元素=元素；//当前节点的元素是this，next=null；//下一个节点链接}链接列表类

LinkedList类提供了操作链表的方法，包括插入和删除节点、查找给定值等。值得注意的是，它只有一个属性，就是用一个Node对象保存链表的头节点。

它的构造函数实现如下：

//链表类functionlist () {this。head=new node(' head ')；//head node this . find=find；//查找节点this.insert=insert//插入节点this.remove=remove//删除节点this . find prev=find prev；//查找上一个节点this.display=display//显示链表}头节点的下一个属性初始化为null，插入新元素时，next将指向新元素。

接下来，我们来看看具体方法的实现。

插入：将节点插入到链接列表中

首先，我们分析插入方法。如果我们想插入一个节点，我们必须指定在哪个节点之前或之后插入。我们先来看看如何在已知节点后插入节点。

要在已知节点后插入新节点，我们必须首先找到该节点。为此，我们需要一个查找方法来遍历链表并找到给定的数据。如果找到，方法返回保存数据的节点。然后，让我们先实现find方法。

查找：查找给定的节点

//查找给定的节点函数find (item) {var currnode=this。头部；while (currNode.element！=item){ CurrNode=CurrNode . next；}返回currNode}find方法还显示了如何在链表上移动。首先创建一个新节点，将链表的头节点分配给新创建的节点，然后在链表上循环。如果当前节点的元素属性与我们要查找的信息不匹配，则将当前节点移动到下一个节点。如果搜索成功，方法返回包含数据的节点。否则，返回null。

一旦找到节点，我们就可以将新节点插入到链表中，将新节点的下一个属性设置为下一个节点的下一个属性对应的值，然后将下一个节点的下一个属性设置为指向新节点。具体实现如下：

//insert node函数insert (newelement，item){ var new node=new node(new element)；var CurrNode=this . find(item)；new node . next=currennode . next；curr node . next=new node；}现在我们可以测试我们的链表了。等等，让我们定义一个显示方法来显示链表的元素，否则，我们怎么知道它是否正确？

显示：显示链接列表

//显示链表元素function display(){ var curr node=this . head；while(！(CurrNode . next==null)){ console . log(CurrNode . next . element)；curr node=curr node . next；}}实现原理同上。将头节点分配给一个新变量，然后循环链表，直到当前节点的下一个属性为空。我们只是在循环过程中打印出每个节点的数据。

var水果=new LList()；水果。插入('苹果'，'头')；水果。插入('香蕉'，'苹果')；水果。插入('梨'，'香蕉')；console.log(水果. display())；//苹果//香蕉//pearrove:从链表中删除一个节点

当从链表中删除一个节点时，我们首先需要找到要删除的节点的上一个节点。找到它后，我们修改它的下一个属性，使它不指向要删除的节点，而是指向要删除的节点的下一个节点。然后，我们需要定义一个findPrevious方法来遍历链表，并检查每个节点的下一个节点是否存储了要删除的数据。如果找到，则返回该节点，以便可以修改其下一个属性。findPrevious的实现如下：//用删除节点函数find prev(item){ var cur node=this . head找到上一个节点；while(！(CurrNode . next==null)(CurrNode . next . element！=item)){ curr node=curr node . next；}返回currNode}这样就解决了remove方法的实现问题

//delete node函数remove (item) {var prev node=this。findprev(项目)；if(！(prev node . next==null)){ prev node . next=prev node . next . next；}}让我们编写一个测试程序来测试remove方法：

//然后上面的代码，我们再添加一个水果。插入('葡萄'，'梨')；console.log(水果. display())；//苹果//香蕉//梨//葡萄//我们吃香蕉。移除('香蕉')；console.log(水果. display())；//苹果//梨//葡萄！成功了，现在可以实现一个基本的单向链表了。

双向链表

虽然从链表的头节点遍历链表很简单，但是反过来，从后往前遍历就不容易了。我们可以给Node类添加一个previous属性，指向前置节点的链接，从而形成一个双向链表，如下图所示：

双向链表

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

双向链表的实现

要实现双向链表，首先需要给结节类增加一个以前的属性：

//节点类函数节点(元素){ this。元素=元素；//当前节点的元素this.next=null/下一个节点链接this.previous=null/上一个节点链接}双向链表的插入方法与单链表相似，但需要设置新节点的以前的属性，使其指向该节点的前驱，定义如下：

//插入节点函数插入(newElement，item){ var new Node=new Node(新元素)；var CurrNode=this。find(item)；新节点。next=currennode。接下来；新节点。上一个=当前节点；电流节点。next=新节点；}双向链表的删除移动方法比单链表效率高，不需要查找前驱节点，只要找出待删除节点，然后将该节点的前驱然后属性指向待删除节点的后继，设置该节点后继以前的属性，指向待删除节点的前驱即可。定义如下：

//删除节点函数remove(item){ var current node=this。find(item)；if(！(CurrNode。next==null)){ CurrNode。以前的。next=CurrNode。接下来；电流节点。下一个。上一个=当前节点。以前的；curr node . next=NullCurrNode . previous=null } }还有一些反向显示链表反证，查找链表最后一个元素查找最后一项等方法，相信你已经有了思路，这里我给出一个基本双向链表的完成代码，供大家参考。

//节点函数节点(元素){ this。元素=元素；//当前节点的元素this.next=null/下一个节点链接this.previous=null/上一个节点链接}//链表类函数LList(){ this。head=新节点(“head”)；this.find=findthis。查找最后一个；this.insert=insertthis.remove=移除；this.display=显示；这个。反证词=反证词；}//查找元素函数find(item){ var current node=this。头部；while (currNode.element！=item){ CurrNode=CurrNode。接下来；}返回currNode}//查找链表中的最后一个元素函数find last(){ var current node=this。头部；while(！(CurrNode。next==null)){ CurrNode=CurrNode。接下来；}返回currNode}//插入节点函数插入(newElement，item){ var new Node=new Node(新元素)；var CurrNode=this。find(item)；新节点。next=currennode。接下来；新节点。上一个=当前节点；电流节点。next=新节点；}//显示链表元素函数display(){ var current node=this。头部；while(！(CurrNode。next==null)){控制台。调试(CurrNode。下一个。元素)；当前节点=当前节点。接下来；}}//反向显示链表元素函数exprovese(){ var current node=this。find last()；while(！(CurrNode。previous==null)){控制台。日志(CurrNode。元素)；当前节点=当前节点。以前的；}}//删除节点函数remove(item){ var current node=this。find(item)；if(！(CurrNode。next==null)){ CurrNode。以前的。next=CurrNode。接下来；电流节点。下一个。上一个=当前节点。以前的；curr node . next=NullCurrNode . previous=null } } var水果=new LList()；水果。插入('苹果','头');水果。插入('香蕉','苹果');水果。插入('梨','香蕉');水果。插入('葡萄','梨');console.log(水果。display())；//苹果//香蕉//梨//葡萄console.log(水果。反证());//葡萄//梨//香蕉//苹果

循环链表

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

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

循环链表

相信你已经明白原理了，所以这里的循环链表上没有贴代码，相信你可以独立完成！

至此，我们对链表有了深刻的认识。如果我们想让自己的链表更健全，也可以用自己的思维，给链表增加一些方法，比如向前移动几个节点，向后移动几个节点，显示当前节点等。让我们一起加油吧！

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun来测试上述代码的运行效果。

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》和0103010

希望本文对JavaScript编程有所帮助。