链表 - Java API 中 LinkedList 类中的"header"

Question

在阅读LinkedList文档时，我对"header"的使用有点困惑。通常，标头是linkedList中的第一个节点。但在这里，"header"看起来像是列表中的一个伪节点，它指向列表的第一个和最后一个节点，从而使LinkedList成为一个循环节点。这是真的吗？

private transient Entry<E> header = new Entry<E>(null, null, null);
public LinkedList() {
    header.next = header.previous = header;
}
public E getFirst() {
    if (size==0)
        throw new NoSuchElementException();
    return header.next.element;
}
public E getLast()  {
    if (size==0)
        throw new NoSuchElementException();
    return header.previous.element;
}
public E removeFirst() {
    return remove(header.next);
}

Answer 1

但在这里，"头"看起来像是列表中的一个伪节点，它指向列表的第一个和最后一个节点

这就是真正的

从而使LinkedList成为一个循环列表。

这并不完全正确：从结构上讲，列表确实是循环的，因为头部会"循环"它。这只是一个实现细节，这是一个常见的技巧，可以避免声明两个东西(header和tailPiece(而不是一个。同一条目单独用于两端这一事实不足以使列表循环：您无法"从外部"循环最后一个节点，因为count阻止您这样做。

Answer 2

你说得对。header存储对列表的头部和尾部的引用。这有助于降低涉及删除/添加/查看列表两端的操作成本。

由于两端都有引用，像getFirst、getLast、removeFirst、removeLast、addFirst、addLast等操作不需要列表遍历。

Answer 3

循环列表是一种避免在顶层结构中同时存储头指针和尾指针的廉价方法。我不知道Java的LinkedList实现，但这肯定是一个技巧，例如std::list的GCC实现。

Answer 4

LinkedList的实现使用了所谓的ssentinel节点。他们选择用一个哨兵同时代表头部和尾部；其他实现将使用两个独立的哨兵。

在任何一种情况下，哨兵的使用都允许实现代码的其余部分不处理null情况。例如，考虑添加一个节点。没有哨兵：

Node newNode = ...;
if (header == null) {
  header = newNode;
  tail = newNode;
} else {
  newNode.previous = tail;
  tail.next = newNode;
  tail = newNode;
}

与哨兵：

Node newNode = ...;
newNode.previous = sentinel.previous;
newNode.next = sentinel;
sentinel.previous = newNode;

这是维基百科上关于哨兵节点的文章。