Java API中的LinkedList类中的“头文件”

在阅读LinkedList文档时，我对“头文件”的用法有点困惑。通常，头是链接列表中的第一个节点。但是在这里它看起来像'头'是列表中的虚拟节点，它指向列表的第一个和最后一个节点，从而使LinkedList成为循环列表。真的吗？Java API中的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); 
}

来源

2013-02-26 user697911

是的。 Java API的LinkedList实现。 – user697911 2013-02-26 00:58:17

我不知道。我从Java 1.4看到这一点。乔希布洛赫编码它。 – 2013-02-26 01:04:51

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

来源

2013-02-26 00:55:16

但在这里它看起来像“头”在列表中的虚拟节点，并将其指向列表

的第一个和最后一个节点这是非常真实

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

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

来源

2013-02-26 00:55:55 dasblinkenlight

但是，如果我只是按照'下一个/上一个'链接，我是否能够遍历列表？我是否必须使用count来循环？ – user697911 2013-02-26 01:00:26

@ user697911正确，如果你只是按照上一个/下一个链接，你会循环。但是，如果您忽略计数，则会通过不带数据的虚拟'header'元素。例如，如果您决定通过一个圆圈中的三元素列表{{A，B，C}'，您会看到'A，B，C，null，A，B，C，null，A， ......“等等。 – dasblinkenlight 2013-02-26 01:03:06

那么，这应该是一般实现双向链表的最佳方式？ – user697911 2013-02-26 01:07:15

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

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

来源

2013-02-26 00:57:09

标题不存储任何对象。对？ – user697911 2013-02-26 01:01:27

不，它被实例化为新条目（null，null，null）;'。当LinkedList构造函数被调用时，只有'next'和'previous'引用被赋值。 – 2013-02-26 01:05:17

LinkedList的执行是使用所谓的s 哨兵节点。他们选择使用一个哨兵头和尾巴;其他暗示将使用两个单独的哨兵。

在任何一种情况下，使用标记都会允许其余的实现代码不处理空情况。例如，考虑添加一个节点。无需Sentinel：

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;

这里的Wikipedia article on Sentinel Nodes。

来源

2013-02-26 01:07:44

Java API中的LinkedList类中的“头文件”

回答

相关问题