JavaScript数据结构之单链表和循环链表实例分享

发布日期： 2018-01-05 阅读量： 作者： 网络

本文主要介绍了javascript数据结构之单链表、循环链表，详细的介绍了javascript如何实现单链表、循环链表，有兴趣的可以了解一下，希望能帮助到大家。

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

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

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

下面是JS部分

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

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

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

单链表：

function LinkedList(){ 
 /*节点定义*/ 
 var Node = function(element){ 
  this.element = element; //存放节点内容 
  this.next = null; //指针 
 } 
 
 var length = 0, //存放链表长度 
  head = null; //头指针 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; //操作所用指针 
 
  if (!head){ 
   head = node; 
  }else { 
   current = head; 
 
   while(current.next){ 
    current = current.next; 
   } 
 
   current.next = node; 
  } 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if (position &gt;= 0 &amp;&amp; position  -1 &amp;&amp; position <p>循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。<br></p><p class="jb51code"><br></p><pre class="brush:js;">function CircularLinkedList(){ 
 var Node = function(element){ 
  this.element = element; 
  this.next = null; 
 } 
 
 var length = 0, 
  head = null; 
 
 this.append = function(element){ 
  var node = new Node(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++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if(position &gt; -1 &amp;&amp; position  -1 &amp;&amp; position <p>使用方法：<br></p><p style="text-align: center"><img alt="" src="//imgfile2.oss-cn-hangzhou.aliyuncs.com/147/315bfeda84b1ffa0e62356e5fc8522d5-0.png"></p><p>在类外部扩充方法：<br></p><p   style="max-width:90%"><img alt="" src="//imgfile2.oss-cn-hangzhou.aliyuncs.com/147/315bfeda84b1ffa0e62356e5fc8522d5-1.png"></p><p>相关推荐：</p><p><a href="http://www.php.cn/js-tutorial-380760.html" target="_self">JavaScript数据结构中双向链表的使用定义的示例</a></p><p><a href="http://www.php.cn/js-tutorial-380758.html" target="_self">JavaScript数据结构中优先队列与循环队列</a></p><p><a href="http://www.php.cn/js-tutorial-360362.html" target="_self">JavaScript数据结构之二叉查找树的定义与表示方法详解</a></p>

# JavaScript # 数据结构 # js

上一篇: wordpress必须安装php吗

下一篇: 官方例子：k8s轻松跑起一个wordpress

JavaScript数据结构之单链表和循环链表实例分享

随便看看