1. ホーム
  2. java

[解決済み] リンクリストのダミーノード

2022-02-08 20:23:03

質問

Q:どのようなときに使うのですか?(宿題の質問)

  1. リスト内の1番目と最後のノード

  2. リストの最初と最後のノードとして使用されることもあります。

  3. リストの最初と最後のノードとして使用されたことはありません。

ウィキペディアによると

センチネルノードとは、リンクされたノードで使用される特別に指定されたノードです。 リストやツリーのトラバーサルパスのターミネータとして使用されます。センチネルノードは データ構造が管理するいかなるデータも保持せず、参照もしない。

Bだと思うんだけど、よくわからない。

どのように解決するのですか?

ダミーノードとセンチネルノードには大きな違いがあります。

ダミーノードは、リストの最初と最後のノードとして使用されることがあります。

リンクリストを開始するときに、ダミーのノードを作るのが一般的な方法ですが、興味深いことに、それは同時に最終ノードでもあるのです。

もちろん、LLの最初と最後のノードがダミーレコードであるとは限りません。

なお、LLの最後のノードを示すセンチネルとして、データを持たないダミーノードとNULLポインタを使用することができる。

ダミー・ノードがないLLは可能なのだろうかと思うかもしれない。
回答 はい、そうです。最初のデータ・エントリーが挿入されるまでLLの初期化を保持し、その時点ではLLとしてNULLポインタを持ち、挿入後は先頭ノードへのポインタを保持し、常にNULLポインタを末尾ノードの "Next" ノードとして使用すればよいのです。

参照先 これ のページをご覧ください。