JavaScript数据结构中单链表和循环链表的示例分析(javascript,移动开发)

进入正题，关于链表的数据结构知识，这里简单介绍下：

链表是一种物理存储单元上非线性、非连续性的数据结构（它在数据逻辑上是线性的），它的每个节点由两个域组成：数据域和指针域。数据域中存储实际数据，指针域则存储着指针信息，指向链表中的下一个元素或者上一个元素。正是由于指针的存在，链表的存储在物理单元是非连续性的。

链表的优点和缺点同样明显。和线性表相比，链表在添加和删除节点上的效率更高，因为其只需要修改指针信息即可完成操作，而不像线性表（数组）那样需要移动元素。同样的，链表的长度在理论上也是无限的（在存储器容量范围内），并可以动态变化长度，相比线性表优势很大。 相应的，由于线性表无法随机访问节点，只能通过指针顺着链表进行遍历查询来访问，故其访问数据元素的效率比较低。

下面是JS部分

这里面封装了的常用方法及描述：

方法描述append(element)向链表尾部添加结点elementinsert(position,element)向位置position处插入结点elementremoveAt(position)按照索引值position删除结点remove(element)搜索并删除给定结点elementremove()删除链表中最后一个结点indexOf(element)查找并返回给定结点element的索引值isEmpty()判断链表是否为空size()获取链表长度toString()转换为字符串输出getHead()获取头结点getTail()获取尾结点

对于各常用方法的算法描述在这里就不写了，相信大家都可以轻易读懂并理解，毕竟都是非常基础的知识了。

单链表：

functionLinkedList(){/*节点定义*/varNode=function(element){this.element=element;//存放节点内容this.next=null;//指针}varlength=0,//存放链表长度head=null;//头指针this.append=function(element){varnode=newNode(element),current;//操作所用指针if(!head){head=node;}else{current=head;while(current.next){current=current.next;}current.next=node;}length++;returntrue;};this.insert=function(position,element){if(position>=0&&position<=length){varnode=newNode(element),current=head,previous,index=0;if(position===0){node.next=current;head=node;}else{while(index++<position){previous=current;current=current.next;}node.next=current;previous.next=node;}length++;returntrue;}else{returnfalse;}};this.removeAt=function(position){if(position>-1&&position<length){varcurrent=head,previous,index=0;if(position===0){head=current.next;}else{while(index++<position){previous=current;current=current.next;}previous.next=current.next;};length--;returncurrent.element;}else{returnnull;}};this.remove=function(element){varcurrent=head,previous;if(element===current.element){head=current.next;length--;returntrue;}previous=current;current=current.next;while(current){if(element===current.element){previous.next=current.next;length--;returntrue;}else{previous=current;current=current.next;}}returnfalse;};this.remove=function(){if(length<1){returnfalse;}varcurrent=head,previous;if(length==1){head=null;length--;returncurrent.element;}while(current.next!==null){previous=current;current=current.next;}previous.next=null;length--;returncurrent.element;};this.indexOf=function(element){varcurrent=head,index=0;while(current){if(element===current.element){returnindex;}index++;current=current.next;}returnfalse;};this.isEmpty=function(){returnlength===0;};this.size=function(){returnlength;};this.toString=function(){varcurrent=head,string='';while(current){string+=current.element;current=current.next;}returnstring;};this.getHead=function(){returnhead;}}

循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。

functionCircularLinkedList(){varNode=function(element){this.element=element;this.next=null;}varlength=0,head=null;this.append=function(element){varnode=newNode(element),current;if(!head){head=node;node.next=head;}else{current=head;while(current.next!==head){current=current.next;}current.next=node;node.next=head;};length++;returntrue;};this.insert=function(position,element){if(position>-1&&position<length){varnode=newNode(element),index=0,current=head,previous;if(position===0){node.next=head;head=node;}else{while(index++<position){previous=current;current=current.next;}previous.next=node;node.next=current;};length++;returntrue;}else{returnfalse;}};this.removeAt=function(position){if(position>-1&&position<length){varcurrent=head,previous,index=0;if(position===0){head=current.next;}else{while(index++<position){previous=current;current=current.next;}previous.next=current.next;};length--;returncurrent.element;}else{returnnull;}};this.remove=function(element){varcurrent=head,previous,indexCheck=0;while(current&&indexCheck<length){if(current.element===element){if(indexCheck==0){head=current.next;length--;returntrue;}else{previous.next=current.next;length--;returntrue;}}else{previous=current;current=current.next;indexCheck++;}}returnfalse;};this.remove=function(){if(length===0){returnfalse;}varcurrent=head,previous,indexCheck=0;if(length===1){head=null;length--;returncurrent.element;}while(indexCheck++<length){previous=current;current=current.next;}previous.next=head;length--;returncurrent.element;};this.indexOf=function(element){varcurrent=head,index=0;while(current&&index<length){if(current.element===element){returnindex;}else{index++;current=current.next;}}returnfalse;};this.isEmpty=function(){returnlength===0;};this.size=function(){returnlength;};this.toString=function(){varcurrent=head,string='',indexCheck=0;while(current&&indexCheck<length){string+=current.element;current=current.next;indexCheck++;}returnstring;};}

使用方法：

在类外部扩充方法：

 </div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">