循環リスト

ウィキペディア小見出し辞書

循環リスト

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)

「連結リスト」の記事における「循環リスト」の解説

循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド（やプロセス）が他のノードを全て参照したい場合などに便利である。 リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。 3つの整数値を格納した循環リスト

循環リスト

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)

「連結リスト」の記事における「循環リスト」の解説

循環リストには、片方向のものと双方向のものがある。循環リストでは環状にノードが連結されているので、"null" は使わない。キューのような前後関係のあるリストでは、リストの最後尾ノードへの参照を保持する必要がある。循環リストでは最後尾ノードの次のノードは先頭ノードである。要素の最後尾への追加や先頭からの削除は定数時間で可能である。 循環リストの利点は、任意のノードから開始してリスト全体をたどることができる点である。このため、"firstNode" や "lastNode" も保持する必要がないことが多いが、空のリストを表すには何らかの特別な表現が必要である。ここでは "lastNode" に "null" を格納することで空のリストを表す。これにより空でないリストでの追加・削除は大幅に単純化されるが、空のリストを特殊ケースとして扱う必要がある。