JavaScript中的数据结构和算法(3):链表

我们可以看到，javascript概念中的队列和堆栈是一种特殊的线性表结构，也是一种基于数组的相对简单的顺序存储结构。因为javascript解释器直接优化了数组，所以很多编程语言都不存在数组长度固定的问题(数组填充后很难添加，包括添加和删除，数组中的所有元素都需要移位，javascript数组直接优化了，比如push、pop、shift、unshift、split方法等。)

线性表的顺序存储结构最大的缺点是改变一个元素的排列会引起整个集合的变化。原因是内存中的存储本来就是连贯的，没有间隙，删除一个就要补上。这种结构优化后，就出现了链式存储结构。换句话说，我们根本不关心数据的排列。我们只需要记录下一个数据在每个元素中的位置。因此，通过链接存储的线性表简称为链表。在链结构中，数据=(信息地址)

在链式结构中，我们也可以把地址称为“链”，一个数据单元就是一个节点，所以可以说链表就是一组节点。每个节点都有一个指向其下一个节点的数据块引用

数组元素在逻辑上由位置关系引用，而链表由每个数据元素保存的引用指针关系引用。

这种结构优势非常明显。只要“链”指向连接，插入数据根本不需要关心它的排列

这样，链表的思想就不会局限于数组，只要对象之间存在引用关系，我们就可以使用对象

链表一般包括单链表、静态链表、循环链表和双链表

单链表：是单个向下传递。每个节点只记录下一个节点的信息。就像《无间道》中的梁朝伟一样，卧底就是通过中间人与线下接触。中间人一旦断了，你就无法证明自己的身份，所以在电影的结尾有一句话：‘我是个好人，谁知道呢？"

静态链表：是用数组描述的链表。也就是说，数组中的每个表都是包含数据和指针的“部分”

循环链表：因为单个链表只会传到后面，到达尾部的时候回到头部会很麻烦，所以尾部的链与头部连接形成一个循环

双链表：针对单链表的优化，每一段都可以知道前后是谁，所以在后指针字段之外还会有一个前指针字段，提高了搜索的效率，但是在设计上带来了一定的复杂性。一般来说，空间会随着时间而改变

总的来说，其实链表是线性表中顺序存储结构的一种优化方法，但是在javascript语言中，由于数组的特殊性(引用位置的自动更新)，我们可以用object方法来做链表存储结构

单链表

我们实现了一个最简单的链表关系

函数createLinkList() { var _this={}，prev=null返回{add:函数(val){//保存当前引用prev={data: val，next : prev | | null } } } var links list=createlinklist()；links list . add(' arron 1 ')；links list . add(' arron 2 ')；links list . add(' arron 3 ')；//node段的下一个链是-arron3-arron2-arron1，通过node对象的next直接引用下一个节点对象，初步实现了通过链表的引用，在日本jQuery的异步delay和cho45的jsderferre中的then方法中使用。这个实现还有另一个关键问题。我们如何在被执行的部分之后动态地插入数据？

因此，我们必须设计一个遍历方法来搜索这个节点链中的数据，然后找出相应的数据，将新的节插入到当前的链中，并重写位置记录

//在链表中找到对应的节var find node=function create find node(curr node){ return function(key){//在循环中找到被执行的节，如果它不返回自身while (currNode.data！=key){ CurrNode=CurrNode . next；}返回currNode} }(head node)；这是一种查找当前节的方法，通过传递头的原始headNode节来搜索next，直到找到相应的节信息

这是通过咖喱方法实现的

然后在插入节时，这是链表地址的转换关系

在a-b-c-d的链表中，如果你想在c(c.next-d)后面插入一个F

A-b-c-f-d，然后c，下一个f，下一个f-d

通过插入方法添加节

//create section函数createnode (data) {this。数据=数据；this.next=null}//初始化头节//形成从head node//join var head node=new create node(' head ')到next的链；//在链表中找到对应的节var find node=function create find node(curr node){ return function(key){//在循环中找到被执行的节，如果它不返回自身while (currNode.data！=key){ CurrNode=CurrNode . next；}返回currNode} }(head node)；//在此处插入新的一节。insert=function(数据，键){//新建节var newNode=new createNode(数据)；//在链中找到对应的数据段//然后将新增加的一段挂在var current=findNode(key)中；//插入新连接并更改引用关系//1: a-B- c-d//2: a-b-n-c-d new node . next=current . next；current.next=newNode};首先，分离createNode节的构造，在初始化时创建一个头节对象，作为节开头的初始化对象

在insert中添加节的方法中，通过搜索headNode链，找到对应的节，添加新的节，最后修改链关系

如何从链表中删除节点？

由于链表的特殊性，我们a-b-c-d，如果要删除C，就必须把b.next-c修改为b.next-d，所以找到上一节修改其链表的下一个地址，这有点像dom操作中removeChild找到其父节点并调用移除其子节点

同样，在remove方法的设计中，我们需要设计一个遍历来返回父节点

//查找上一节var查找上一节=function(curr node){ return function(key){ while(！(CurrNode . next==null)(CurrNode . next . data！=key)){ curr node=curr node . next；}返回currNode} }(head node)；//插入方法this。remove=function(key){ var prev node=find previous(key)；if(！(prevnode。next==null){//修改链表关系prevnode。next=prevnode。下一个。接下来；}};测试代码：

！doctype htmlbutton id='test1 '插入多条数据/buttonbutton id='test2 '删除拉塞尔维尔数据/button div id=' list show ' br//div脚本类型=' text/JavaScript '/////////////创建链表////////////函数createLinkList() { //创建节函数创建节点(数据){ this。数据=数据；this.next=null} //初始化头部节//从头节点开始形成一条链条//通过然后衔接var head节点=新建节点(' head ')；//在链表中找到对应的节var findNode=函数createFindNode(currNode){ 0返回函数(键){ //循环找到执行的节，如果没有返回本身while (currNode.data！=key){ CurrNode=CurrNode。接下来；}返回currNode} }(头节点)；//找到前一个节var find previous=function(Currnode){ return function(key){ while(！(CurrNode。next==null(CurrNode)。下一个。数据！=key)){ curr node=curr node。接下来；}返回currNode} }(头节点)；//插入一个新节this.insert=函数（数据、键){ //创建一个新节var newNode=new createNode(数据);//在链条中找到对应的数据节//然后把新加入的挂进去var current=findNode(键);//插入新的接，更改引用关系//1: a-B- c-d//2: a-B- n-c-d新节点。下一个=当前。接下来；current . next=NewNode }；//插入方法这个。remove=function(key){ var prev node=find previous(key)；if(！(prevNode.next==null)) { //修改链表关系上一个节点。next=prev节点。下一个。接下来；} };这个。display=function(fn){ var curr节点=head节点；while(！(CurrNode。next==null)){ CurrNode=CurrNode。接下来；fn(CurrNode。数据)} }；} var city=new createLinkList()；函数create(){ var text=' '；城市。display(function(data){ text='-' data；});var div=文档。创建元素(' div ')div。innerhtml=text文件。getelementbyid('列表显示').appendChild(div)}文档。getelementbyid(' test1 ').onclick=function(){ cities。插入('康威'，'头')；城市。插入(' russelville '，' Conway ')；cities.insert('卡莱尔','拉塞尔维尔');城市。插入('阿尔玛','卡莱尔');create()；}文档。getelementbyid(' test2 ').onclick=function(){ cities。移除(' Russellville ')；create() }/script双链表

原理跟单链表是一样的，无非就是给每一个节增加一个前链表的指针

增加节

//插入一个新节this.insert=函数（数据、键){ //创建一个新节var newNode=new createNode(数据);//在链条中找到对应的数据节//然后把新加入的挂进去var current=findNode(headNode，key)；//插入新的接，更改引用关系新节点。下一个=当前。接下来；新节点。previous=当前电流。next=新节点；};删除节

这个。remove=function(key){ var current node=find node(head node，key)；if(！(CurrNode。next==null)){ CurrNode。以前的。next=CurrNode。接下来；电流节点。下一个。上一个=当前节点。以前的；curr node . next=NullCurrNode . previous=null } }；在删除操作中有一个明显的优化：不需要找到父节了，因为双链表的双向引用所以效率比单链要高

测试代码：

！doctype htmlbutton id='test1 '插入多条数据/buttonbutton id='test2 '删除拉塞尔维尔数据/button div id=' list show ' br//div脚本类型=' text/JavaScript '/////////////创建链表////////////函数createLinkList() { //创建节函数创建节点(数据){ this。数据=数据；this . next=null this . previous=null }//初始化头部节//从头节点开始形成一条链条//通过然后衔接var head节点=新建节点(' head ')；//在链表中找到对应的数据var findNode=function(currNode，key) { //循环找到执行的节，如果没有返回本身while (currNode.data！=key){ CurrNode=CurrNode。接下来；}返回currNode} //插入一个新节this.insert=函数（数据、键){ //创建一个新节var newNode=new createNode(数据);//在链条中找到对应的数据节//然后把新加入的挂进去var current=findNode(headNode，key)；//插入新的接，更改引用关系新节点。下一个=当前。接下来；新节点。previous=当前电流。next=新节点；};这个。remove=function(key){ var current node=find node(head node，key)；if(！(CurrNode。next==null)){ CurrNode。以前的。next=CurrNode。接下来；电流节点。下一个。上一个=当前节点。以前的；curr node . next=NullCurrNode . previous=null } }；这个。display=function(fn){ var curr节点=head节点；while(！(CurrNode。next==null)){ CurrNode=CurrNode。接下来；fn(CurrNode。数据)} }；} var city=new createLinkList()；函数create(){ var text=' '；城市。display(function(data){ text='-' data；});var div=文档。创建元素(' div ')div。innerhtml=text文件。getelementbyid('列表显示').appendChild(div)}文档。getelementbyid(' test1 ').onclick=function(){ cities。插入('康威'，'头')；城市。插入(' russelville '，' Conway ')；cities.insert('卡莱尔','拉塞尔维尔');城市。插入('阿尔玛','卡莱尔');create()；}文档。getelementbyid(' test2 ').onclick=function(){ cities。移除(' Russellville ')；create() }/scriptgit代码下载：https://github。com/JSaaron/data _ structure。饭桶