JavaScript数据结构之链表的实现

前面楼主分别讨论了数据结构栈与队列的实现，当时所用的数据结构都是用的数组来进行实现，但是数组有的时候并不是最佳的数据结构，比如在数组中新增删除元素的时候需要将其他元素进行移动，而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢，就可以考虑使用链表。

链表的概念

链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量，以head表示，它存放一个地址，指向一个元素。每个结点都使用一个对象的引用指标它的后继，指向另一个结点的引用叫做链。

数组元素依靠下标（位置）来进行引用，而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高，下图演示了链表结点d的插入过程：　

删除过程：

基于对象的链表

我们定义2个类，Node类与LinkedList类，Node为结点数据，LinkedList保存操作链表的方法。

首先看Node类：　　

element用来保存结点上的数据，next用来保存指向一下结点的的链接。　　

LinkedList类:

find()方法，从头结点开始，沿着链表结点一直查找，直到找到与item内容相等的element则返回该结点，没找到则返回空。

Insert方法。通过前面元素插入的演示可以看出，实现插入简单四步：

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

Remove()方法。删除某一节点需要先找到被删除结点的前结点，为此我们定义方法frontNode()：

简答三步：

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

Show()方法：

不显示head结点 currentNode = currentNode.next; } }

测试程序：

输出：

双向链表

从链表的头节点遍历到尾节点很简单，但有的时候，我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

首先我们先给Node类增加front属性：　　

当然，对应的insert()方法和remove()方法我们也需要做相应的修改：　

增加front指向前驱结点 currentNode.next = newNode; } function remove(item){ var currentNode = this.find(item);//找到需要删除的节点 if (currentNode.next != null) { currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点 currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点 currentNode.next = null;//并设置前驱与后继的指向为空 currentNode.front = null; } }

反序显示链表：

需要给双向链表增加一个方法，用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点，可以免除从前往后遍历链。

实现反序输出：

测试程序：

输出：