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これは単なる実装の詳細であり、1 つではなく 2 つのもの (と)を宣言することを避けるための一般的なトリックです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と呼ばれるものを使用しています。彼らは、頭と尾の両方に 1 つの歩哨を使用することを選択しました。他の実装では、2 つの別個のセンチネルが使用されます。

いずれの場合も、センチネルを使用すると、実装コードの残りの部分で 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 に答える