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

双链表

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

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

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

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

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

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

循环链表

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

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

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

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

数组链表

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

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(4.6)更多链表相关的形态

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多