連結リスト
循環リスト(circularly-linked list)では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。つまり、循環リストは先頭や最後尾といったものが存在しないリストと考えることもできる。循環リストはデータ格納用バッファの管理によく使われ、1つのノードを使っているスレッド(やプロセス)が他のノードを全て参照したい場合などに便利である。
リスト全体を指すポインタは、アクセスポインタと呼ばれることがある。
参照型をサポートしていない言語でも、ポインタの代わりに配列にインデックスを使うことでリンクを実現できる。構造体の配列を用意し、リンク用フィールドには配列のインデックスを表す整数を保持することで次(あるいは前)のノードを指すものとする。配列にある全ノードを使う必要はない。構造体がサポートされていない場合、並列配列を代替として使うことができる。
例として、次の構造体を示す。ポインタの代わりに配列にインデックスを使っている。
この構造体の配列を生成し、リストの先頭のインデックスを保持する整数変数を用意すれば、連結リストを構築できる。
要素間のリンクはリスト上の次(または前)の要素の配列インデックスを Next あるいは Prev フィールドに格納することでなされる。例えば、次のようになる。
この例で、ListHead は 2 になっており、そこがリストの先頭ノードである。3番と5から7番のエントリはリスト上に含まれていない。これらのセルはリストに新たに追加することが可能である。ListFree という整数変数を用意してフリーリストを構成しておくと扱いやすくなる。全てのエントリが使われている場合、配列の大きさを拡張するか、一部要素を削除して空きを作らないと、新たな要素をリストに追加できなくなる。
次のコードは、リストを辿って、name と balance を表示するものである。
この手法の利点は次の通りである。
片方向循環リスト(singly-circularly-linked list)では、各ノードは線形の片方向リストと同じように1つのリンクを持つが、最後尾のノードは先頭のノードをリンクしている。片方向リストと同様、新たなノードを挿入する場合、既に参照を持っているノードの次の位置にのみ挿入できる。このため、片方向循環リストでは、最後尾のノードを指している参照を保持しておくことが多く、それによって、先頭位置に高速に挿入可能とするだけでなく、先頭ノードから最後尾のノードまでを順に辿ることも可能にしている。