关于双向链表和单向链表

Question

根据我自己写的单项链表和双向链表，我感觉其实无论哪种链表对于中间位置的元素的处理都是一个O(n)级别的操作，所以一般使用链表是对头和尾处理，那么其实单链表的头尾操作并没有比双链表差啊，甚至操作起来更简单，那为什么jdk里的链表要用双链表呢？可能是因为我见识太短浅，看不到更大的用处吧，不知道老师可否给我介绍一下双链表的作用呢？

Answer 1

liuyubobobo 2020-04-01 15:28:09

你说的“无论哪种链表对于中间位置的元素的处理都是一个O(n)级别的操作”是正确的：）

双向链表的意义在于，如果想快速删除尾结点的话，双向链表可以做到，但是单链表做不到。

因此，对于有一些数据结构，比如双端队列，适合使用双链表构建。

继续加油！：）

• 提问者 Ethan_Qjm #1

  非常感谢！

• qq_期待_fjAHQT #2

  老师，双向列表不就是Node里面多了一个pre指针吗 
  为什么可以快速删除尾节点？

• liuyubobobo 回复 qq_期待_fjAHQT #3

  因为可以快速的找到尾结点的上一个节点，让上一个节点的 next 为空。