最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 双链表

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

    在链表的尾端删除元素,即使我们有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)更多链表相关的形态

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 108会员总数(位)
    • 3695资源总数(个)
    • 3本周发布(个)
    • 0 今日发布(个)
    • 182稳定运行(天)

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

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级