0

在阅读 LinkedList 文档时，我对“标题”的使用感到有些困惑。通常，标头是linkedList 中的第一个节点。但在这里看起来“标题”是列表中的一个虚拟节点，它指向列表的第一个和最后一个节点，从而使 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);
}
4

4 回答 4

3

但在这里看起来“标题”是列表中的一个虚拟节点，它指向列表的第一个和最后一个节点

这是真的

从而使 LinkedList 成为循环列表。

这并不完全正确：从结构上讲，列表确实是循环的，因为标题“循环”了它。这只是一个实现细节，一个常见的技巧，可以让您避免声明两件事 (header和tailPiece) 而不是一个。同一条目本身用于两端的事实不足以使列表循环：您无法“从外部”围绕最后一个节点循环，因为这会count阻止您这样做。

于 2013-02-26T00:55:55.863 回答
1

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

随着对两端的引用的可用性，诸如getFirst, getLast, removeFirst, removeLast,addFirst等的addLast操作不需要列表遍历。

于 2013-02-26T00:57:09.190 回答
0

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

于 2013-02-26T00:55:16.783 回答
0

的实现LinkedList是使用所谓的 s sentinel节点。他们选择了对头部和尾部使用一个哨兵；其他实现将使用两个独立的哨兵。

在任何一种情况下，使用哨兵都允许其余的实现代码不处理 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;

这是关于 Sentinel Nodes 的维基百科文章。

于 2013-02-26T01:07:44.773 回答