JavaScript中怎么实现链表？

JavaScript中怎么实现链表？

学习数据结构的的链表和树时，会遇到节点（node）这个词，节点是处理数据结构的链表和树的基础。节点是一种数据元素，包括两个部分：一个是实际需要用到的数据；另一个存储下一个节点位置。

链表是一系列节点串联形成的数据结构，链表存储有序的元素集合，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的部分和一个指向下一个元素的链接部分组成。因此链表增删非首尾元素时不需要移动元素，只需要更改链接部分的值即可。

在此仅看单链表，单链表每个节点的结构如下：

单链表，在这种类型的数据结构中，任何两个数据元素之间只有一个链接，参见下图：

链表的操作包括了创建、删除、插入、输出等。

创建就是空间的分配，将头、尾指针及链表结点个数等初始化。删除和插入根据被操作元素的位置可以细分为头删除（插入），尾删除（插入），中间删除（插入）。

插入操作

头插入实际上是增加一个新节点，然后把新增加的结点指针指向原来头指针指向的元素，再把头指针指向新增的节点。

尾插入也是增加一个新节点，该节点指针置为null，然后把原尾结点指针指向新增加的节点，最后把尾指针指向新增加的节点即可。

中间插入稍复杂，首先增加一个节点，然后新增节点的指针指向插入位置的后一个节点，把插入位置的前一个节点指针指向新插入节点即可。

删除操作

删除头元素时，先将头指针指向下一个节点，然后把原头结点的指针置空即可。

删除尾元素时，首先找到链表倒数第2个元素，然后把尾指针指向这个元素，接着把原倒数第2个元素的指针置空。

删除中间元素相对复杂一些，首先将要删除的节点的前一个节点指针指向要删除的节点的下一个节点，然后把要删除节点的指针置空。

上面提到是单链表最基本的操作，除此之外还有其它操作不多说了。下面给出代码示例。

在 JavaScript中，我们怎么实现链表呢？

现在以单链表的建立和遍历为例介绍。项目结构如下

SingleLinkedList.js文件内容如下：

//定义单向链表的节点类
class Node{constructor(data){this.data = data    //节点的数据部分this.next = null    //节点的链接部分(指针部分)   }
}
//定义单向链表类
class SingleLinked{  constructor(){this.size = 0  //单链表的长度，用来记录链表中的节点个数，为一个空链表this.head = new Node('head')  //是链表的头指针：记录链表的起始地址this.currentNode = ''  //用来记录当前节点}//获取链表的长度getLength(){return this.size}//判断链表是否为空isEmpty(){return this.size === 0   //如果this.size为0则说明链表为空，即返回true}//遍历链表:不重复的访问链表中的每一个节点displayList(){var list = ''var currentNode = this.head  //指向链表的头指针while(currentNode){  //若当前节点不为空，则执行循环list+=currentNode.data    //连接节点的数据域currentNode = currentNode.next  //让当前指针指向当前节点的下一个节点if(currentNode){   //如果currentNode不为空则加上连接符list += '->'  //链表节点的连接符}}console.log(list)}//获取链表的最后一个节点findLast(){var currNode = this.headwhile(currNode.next){   //若当前节点的next域为空，则他是链表的最后一个节点，跳出循环currNode = currNode.next  //若当前节点的next域不为空则让指针指向当前节点的下一个节点}return currNode}//采用尾插法给链表插入元素appendNode(element){var currNode = this.findLast()  //找到链表的最后一个节点var newNode = new Node(element)  //创建一个新的节点currNode.next = newNodenewNode.next = nullthis.size++   //链表的长度加1}//删除链表中的一个节点delete(element){//this.displayList()var currentNode = this.headtry{while((currentNode.next!=null)&&(currentNode.next.element!=element)){  //判断，如果节点靠后则节点的next的next为空，不为空时进行删除if(currentNode.next.data === element){currentNode.next = currentNode.next.next    this.size--}else{currentNode = currentNode.next}}}catch(e){   //测试函数，判断函数的运行错误console.log(e)}}
}

测试代码内容如下，我这里保存文件名为 单链表测试.html，将此文件和SingleLinkedList.js放到同一目录中：

<script src="./SingleLinkedList.js"></script><script>  //不能写在有js代码的JavaScript中var slist = new SingleLinked()console.log(slist.isEmpty())  //打印链表是否为空，若为空则输出trueslist.appendNode(1001)   //创建链表节点slist.appendNode(1002)   //创建链表节点//创建链表更多节点var arr = [1020,1234,1006,788,5512]for(var i=0;i<arr.length;i++){slist.appendNode(arr[i])}//遍历输出链表slist.displayList()//删除链表中的1006元素slist.delete(1006)slist.displayList()
</script>

用浏览器打开 单链表测试.html，按下F12键单开控制台，查看结果：

更多情况可见https://segmentfault.com/a/1190000017970029