JavaScript数据结构之链表的实现方法介绍(图文)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript数据结构之链表的实现方法介绍(图文),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5294字,纯文字阅读大概需要8分钟。
内容图文
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。本文主要介绍JavaScript数据结构中链表的实现,具有很好的参考价值。下面跟着小编一起来看下吧前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢,就可以考虑使用链表。
链表的概念
链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量,以head表示,它存放一个地址,指向一个元素。每个结点都使用一个对象的引用指标它的后继,指向另一个结点的引用叫做链。
数组元素依靠下标(位置)来进行引用,而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高,下图演示了链表结点d的插入过程:
删除过程:
基于对象的链表
我们定义2个类,Node类与LinkedList类,Node为结点数据,LinkedList保存操作链表的方法。
首先看Node类:
element用来保存结点上的数据,next用来保存指向一下结点的的链接。
LinkedList类:
find()方法,从头结点开始,沿着链表结点一直查找,直到找到与item内容相等的element则返回该结点,没找到则返回空。
Insert方法。通过前面元素插入的演示可以看出,实现插入简单四步:
1、创建结点
2、找到目标结点
3、修改目标结点的next指向链接
4、将目标结点的next值赋值给要插入的结点的next
Remove()方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法frontNode():
简答三步:
1、创建结点
2、找到目标结点的前结点
3、修改前结点的next指向被删除结点的n后一个结点
Show()方法:
测试程序:
输出:
双向链表
从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。
首先我们先给Node类增加front属性:
当然,对应的insert()方法和remove()方法我们也需要做相应的修改:
反序显示链表:
需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。
实现反序输出:
测试程序:
输出:
循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:
head.next = head
这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表:
修改构造方法:
这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。
测试程序:
测试结果:
以上就是JavaScript数据结构之链表的实现方法介绍(图文)的详细内容,更多请关注Gxl网其它相关文章!
内容总结
以上是互联网集市为您收集整理的JavaScript数据结构之链表的实现方法介绍(图文)全部内容,希望文章能够帮你解决JavaScript数据结构之链表的实现方法介绍(图文)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。