JavaScript数据结构链表的实现

编辑：宝哥软件园来源：互联网时间：2021-09-05

新天龙八部

评分

上一位楼主分别讨论了数据结构栈和队列的实现。当时使用的所有数据结构都是用数组实现的，但有时候数组并不是最好的数据结构。例如，在数组中添加或删除元素时，需要移动其他元素，而在javascript中使用spit()方法则不需要访问其他元素。如果你发现使用数组很慢，考虑使用链表。

链表的概念

链表是一种常见的数据结构。这是一种动态存储分配结构。链表有一个“头指针”变量，用head表示，它存储一个地址并指向一个元素。每个节点使用一个对象的引用索引，它的后继节点，指向另一个节点的引用，称为链。

数组元素由下标(位置)引用，而链表元素由它们的关系引用。因此，链表的插入效率非常高。下图演示了链表节点D的插入过程：

删除过程：

基于对象的链表

我们定义了两个类，节点类和链表类。节点就是节点数据，LinkedList保存操作链表。

首先看节点类：

函数Node(element){ this . element=element；this.next=null}元素用于保存节点上的数据，next用于保存指向下一个节点的链接。

链接列表类：

函数LinkedList(){ this . head=new Node(' head ')；this.find=findthis.insert=insertthis.remove=移除；this.show=show}find()方法，从head节点开始，沿着链表节点搜索，直到找到与item内容相等的元素，然后返回该节点，如果没有找到，则返回null。

函数find(item){ var currentNode=this . head；//从head节点开始while(currentNode.element！=item){ current node=current node . next；}返回currentNode//找到了返回节点数据，但没有找到null}Insert方法。通过前面对元素插入的演示，可以看出实现插入有四个简单的步骤：

1.创建节点

2.找到目标节点

3.修改目标节点的下一个指向链接

4.将目标节点的下一个值分配给要插入的下一个节点

函数插入(newElement，item){ var new Node=new Node(new element)；var CurrentNode=this . find(item)；new node . next=CurrentNode . next；current node . next=new node；}Remove()方法。要删除一个节点，我们需要先找到被删除节点的frontNode，所以我们定义方法frontnode():

函数front node(item){ var current node=this . head；while(currentNode.next.element！=itemcurrentNode.next！=null){ CurrentNode=CurrentNode . next；}返回currentNode}简答三步走：

1.创建节点

2.找到目标节点的前节点

3.修改前节点的下一个指向被删除节点的N后节点

函数remove(item){ var front node=this . front node(item)；//console . log(front node . element)；front node . next=front node . next . next；}Show()方法：

函数show(){ var currentNode=this . head，resultwhile(currentNode.next！=null){ result=CurrentNode . next . element；//为了不显示头节点current node=current node . next；}}测试程序：

var list=new linked list()；list.insert('a '，' head ')；list.insert('b '，' a ')；list.insert('c '，' b ')；console . log(list . show())；list . remove(' b ')；console . log(list . show())；输出：

双向链表

从链表的头节点遍历到尾节点非常简单，但是有时候我们需要从后往前遍历。此时，我们可以向Node对象添加一个属性，该属性存储到前置节点的链接。楼主用下图来说明双链表的工作原理。

首先，我们将前端属性添加到节点类中：

函数Node(element){ this . element=element；this.next=nullthis.front=null}当然，我们还需要修改相应的insert()方法和remove()方法：

函数插入(newElement，item){ var new Node=new Node(new element)；var CurrentNode=this . find(item)；new node . next=CurrentNode . next；new node . front=current node；//添加前面指向的currentnode。next=newnode}函数remove(item){ var currentNode=this . find(item)；//查找节点if (currentNode.next！=null){ CurrentNode . front . next=CurrentNode . next；//让前置节点指向要删除节点的下一个节点，current node . next . front=current node . front；//让后续节点指向要删除节点的前一个节点。currentNode.next=null//并将前面和后面的方向设置为null currentNode.front=null}}以相反的顺序显示链接列表：

有必要向双向链表添加一个方法来查找最后一个节点。findLast()方法找出链表中的最后一个节点，可以避免从前到后遍历链表。

函数findLast() {//查找链表的最后一个节点var currentNode=this.headwhile (currentNode.next！=null){ CurrentNode=CurrentNode . next；}返回currentNode}实现逆序输出：

函数showReverse(){ var currentNode=this . head，result=current node=this . find last()；while(currentNode.front！=null){结果=CurrentNode . element“”；current node=current node . front；}返回结果；}测试程序：

var list=new linked list()；list.insert('a '，' head ')；list.insert('b '，' a ')；list.insert('c '，' b ')；console.log(列表)；list . remove(' b ')；console . log(list . show())；console . log(list . showreverse())；输出：

循环链表

循环链表是链式存储结构的另一种形式。其特点是表中最后一个节点的指针字段指向头节点，整个链表形成一个环。循环链表类似单向链表，节点类型相同。唯一不同的是，在创建循环链表时，让其头节点的下一个属性指向自己，即：

head.next=head

这个行为被传输到链表中的每个节点，这样每个节点的下一个属性就指向链表的头节点。楼主用下图表示循环链表：

修改施工方法：

函数LinkedList(){ this . head=new Node(' head ')；//初始化this . head . next=this . head；//直接将头节点的下一个指向头节点，形成循环链表this.find=findthis . front node=front node；this.insert=insertthis.remove=移除；this.show=show}此时要注意链表的输出方法show()和find()。原方法在循环链表中会陷入无限循环，while循环的循环条件需要修改才能在循环到头节点时退出循环。

函数find(item){ var currentNode=this . head；//从head节点开始while(currentNode.element！=itemcurrentNode.next.element！=' head '){ current node=current node . next；}返回currentNode//找到了返回节点数据，但不是null}函数show () {var current node=this。head，result=while (currentNode.next！=null currentNode.next.element！=“head”){ result=CurrentNode . next . element“”；current node=current node . next；}返回结果；}测试程序：