連結リスト ノードの配列を使った連結リスト

ウィキペディア

連結リスト

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/07 16:50 UTC 版)

ノードの配列を使った連結リスト

参照型をサポートしていない言語でも、ポインタの代わりに配列にインデックスを使うことでリンクを実現できる。構造体の配列を用意し、リンク用フィールドには配列のインデックスを表す整数を保持することで次（あるいは前）のノードを指すものとする。配列にある全ノードを使う必要はない。構造体がサポートされていない場合、並列配列を代替として使うことができる。

例として、次の構造体を示す。ポインタの代わりに配列にインデックスを使っている。

 record Entry {
    integer next; // 次のエントリの配列インデックス
    integer prev; // 前のエントリ（双方向の場合）
    string name;
    real balance;
 }

この構造体の配列を生成し、リストの先頭のインデックスを保持する整数変数を用意すれば、連結リストを構築できる。

integer listHead;
Entry Records[1000];

要素間のリンクはリスト上の次（または前）の要素の配列インデックスを Next あるいは Prev フィールドに格納することでなされる。例えば、次のようになる。

インデックス	Next	Prev	Name	Balance
0	1	4	Jones, John	123.45
1	-1	0	Smith, Joseph	234.56
2 (listHead)	4	-1	Adams, Adam	0.00
3			Ignore, Ignatius	999.99
4	0	2	Another, Anita	876.54
5
6
7

この例で、ListHead は 2 になっており、そこがリストの先頭ノードである。3番と5から7番のエントリはリスト上に含まれていない。これらのセルはリストに新たに追加することが可能である。ListFree という整数変数を用意してフリーリストを構成しておくと扱いやすくなる。全てのエントリが使われている場合、配列の大きさを拡張するか、一部要素を削除して空きを作らないと、新たな要素をリストに追加できなくなる。

次のコードは、リストを辿って、name と balance を表示するものである。

i := listHead;
while i >= 0 { // リスト上をループする
     print i, Records[i].name, Records[i].balance // エントリの印字
     i = Records[i].next;
}

この手法の利点は次の通りである。

• リンクとしてアドレスを使っていないので、リロケータブル（メモリ上でコピー可能）である。また、直接シリアライズしてディスクやネットワークに転送可能である。
• 小さいリストの場合、配列インデックスの方がポインタよりも小さくて済むことが多い。
• ノードがメモリ上に連続して存在するため、参照の局所性が向上する可能性がある。
• 素朴な動的メモリ確保でノード用にメモリを割り当てると無駄が生じる可能性があるが、この方式ではノード毎のオーバーヘッドはほとんどない。
• 事前に配列として確保されている範囲では、動的メモリ確保よりもノードの生成が高速化される。

ただし、この方式にはノード群のためのメモリ領域管理を独自に行わなければならないという欠点がある。このため、次のような問題が生じる。

• 実装が複雑になる。
• 全ノードを使い切ったとき、配列の拡張が困難か不可能な場合がある。汎用のメモリプールからノード用にメモリを確保するほうが容易である。
• 動的配列に要素を追加しようとすると、予期しないタイミングで定数時間ではなく線形時間（O(n)）がかかってしまう（平均すれば定数時間と言える）。
• 予想したよりもノード数の使用量が少ないと、メモリを無駄に確保することになる。

以上のような理由から、この手法は動的メモリ確保をサポートしていない言語で主に利用される。問題の多くは、配列生成時にリストの最大サイズが分かっている場合には問題ではなくなる。