javascript数据结构与算法之链表_基础知识

《javascript数据结构与算法之链表_基础知识》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaScript数据结构与算法之链表链表简介链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。（有C语言基础的可能比较好理解）。使用链表结构可以克服数组需要预先知道数据大小的缺点（C语言的数组需要预先定义长度），链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。接下來就是介绍两种常见的链表：单向链表，双向链表在JavaScript中的实现。单向链表链表屮最简单的形式就是单向链表，链表屮的节点都包含两个部分，第一部分储存着口身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL:JavaS

2、cipt中单向链表的实现首先，创建一个构造函数。/***单向链农构造函数*/functionLinkedList(){/***单向链表中节点的构造函数*@param{Any}element耍传入链表的节点*/varNode=function(clement){this.element=element;〃下个节点的地址this.next二null;}//单向链表的长度varlength二0;//单向链表的头结点，初始化为NULLvarhead=null;不难看出，单向链表构造函数比栈与队列要复杂许多。单向链表需要有如下的方法：1.append(element):添加元素到链表尾部1.insert

3、(position,element):向单向链表中某个位置插入元素2.indexOf(element):寻找某个元索在单向链表中的位置3.remove(element):移除给定的元索4.removeAt(position):移除单向链表屮某个位置的元素5.getHead():获取单向链表的头部6.isAmptyO：检查单向链表是否为空，为空则返回(rue7.toString():将链表所有内容以字符串输出8.size():返回单向链表长度append方法：说明：向单向链表尾部添加元素。实现：/***向单向链表尾部添加元索*©param{Any}element要加入链表的节点*/this.ap

4、pend=function(element){varnode=newNode(element);varcurrent;if(head二二null){head=node;}else{//当前项等于链表头部元索.//while循环到最后一个，从而将该节点加入链表尾部。currenl二head;//当next为null时，判定为false。退出循坏。while(current・ncxt){current=current・next;}currenl.next=node;}lcngth++;insert方法:说明：向单向链表屮某个位置插入元素。实现：/***向单向链表小插入某个元素*@param{Num

5、ber}position要插入的位置*©param{Any}element要插入的元素*@return{Boolean}插入成功返回true,失败返回false*/this,inscrt二function(position,element){if(position>=0&&position<=length){varnode二newNode(element);varcurrent二head;varprevious;varindex=0;if(position==0){node,next二current;head=node;}else{while(index++

6、s=current;current二current,next;}previous,next=node;node,next=current;}length++;returntrue;}else{returnfalse;}};indexOf方法：说明：寻找某个元素在单向链表中的位置。实现：/***寻找某个元素在单向链表中的位芝*@param{Any}element要寻找的元素*@return{Number}返冋值＞二0则代表找到相应位置*/this.indcxOf二function(clcment){varcurrent=head;varindex=-1;whi1e(current){if(cle

7、ment二二二current.clement){returnindex;}index++;current二current.next;}return-1;};remove方法：说明：移除给定的元素。实现：/***移除给定的元索*©param{Any}clement要移除的元素*©return{Number}返回值＞二0表示移除成功*/this.remove二function(element){var