java - 双向链表空的情况

Question

在我的演讲中没有给出如果双向链表为空则

header.next==tail;

或者

tail.prev==header; 

但我觉得恰好有两个节点时就是这种情况。空壳不应该是 head==null.
我不知道我是否正确。我对这个主题还是陌生的。有人可以澄清一下

Answer 1

有两种常见的方式来存储双链表:

• 让 head 和 tail 指代树中的实际节点。

  head variable       tail variable
    |                   |
    V                   V
  first -> second -> third -> null
  

  在这种情况下，您是正确的 - head 将为 null。

• 让 head 和 tail 成为特殊节点(称为 "sentinel nodes" ，正如另一个答案中指出的那样)，它们实际上不包含任何数据并且通过next和prev分别指向列表中的第一个和最后一个节点。

  head variable                       tail variable
    |                                   |
    V                                   V
  head -> first -> second -> third -> tail -> null
  node                                node
  

  在这种情况下，header.next == tail 表示列表为空。

  可以使用这种方法而不是上述方法来稍微简化实现并使代码更快一些 - 无需为删除或插入第一个或最后一个节点做出特殊规定。

  <