• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(4.6)更多链表相关的形态

极客笔记 Geekerstar 11个月前 (05-13) 373次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

双链表

对于队列来说我们要在链表的两端进行操作的时候就遇到了这样一个问题。

在链表的尾端删除元素,即使我们有tail这个变量指向链表的结尾,但依然是O(n)复杂度的。

对于这个问题其实有一个解决方案,这个解决方案就是双链表。

所谓双链表就是对我们链表中每一个节点其实包含了两个指针,或者叫两个引用,既指向这个节点后一个元素next,又指向这个节点的前一个元素prev。

对于双链表来说,noed就变成了这种情况,包含三个域分别是元素e和两个指向node的节点next和prev。

对于双链表一旦我们知道了tail这个位置之后,删除tail节点就变得非常简单,是个O(1)复杂度的操作,代价就是由于每个节点有两个指针,维护它就更加复杂一些。

循环链表

对于循环链表也可以用双链表的这种思路实现,不过我们设立一个虚拟头结点之后,整个链表最终是形成一个环。

这里最重要的就是尾节点不指向空而是指向虚拟头节点,我们可以很方便的用这个节点下一个节点是不是虚拟头结点来判断是不是尾节点。

循环的好处是进一步把许多操作进行统一,比如说向链表结尾添加一个元素,我们就不再需要tail一直指着结尾了,我们只需要在头结点前面添加一个元素,就等于在整个链表结尾添加一个元素。

循环链表是非常有用的,java里面的LinkedList类底层实现就是循环链表。

数组链表

链表也可以用数组来实现,因为链表的next只是指向下一个node而已,如果我们数组中每一个位置存储的不仅仅有这个元素,再多存储一个指向下一个元素的索引,在明确知道链表有多少个的情况下,使用数组链表是比较方便的。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(4.6)更多链表相关的形态
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00