リンクリスト

単方向連結リストは、「値」フィールドと「次」フィールドを持つノードで構成されます。「次」フィールドは、ノードの並びにおける次のノードを指します。単方向連結リストに対して実行できる操作には、挿入、削除、および走査があります。

以下のC言語コードは、単方向連結リストの末尾に「値」を持つ新しいノードを追加する方法を示しています。

#include <stdlib.h>// 連結リストの各ノードは構造体です。先頭ノードはリストの最初のノードです。typedef struct Node {整数値;struct Node * next ;}ノード;Node * addNodeToTail ( Node * head , int value ) {// Node ポインタを宣言し、リストの末尾に追加される新しい Node を指すように初期化します (つまり、新しい Node のメモリ アドレスを持つようになります)。Node * temp = ( Node * ) malloc ( sizeof * temp ); /// stdlib の 'malloc'。temp -> value = value ; // 新しいノードの値フィールドにデータを追加します。temp -> next = NULL ; // 無効なリンクを nil に初期化します。if ( ! head ) {head = temp ; // リンクリストが空の場合（つまり、head ノード ポインタが null ポインタの場合）、head ノード ポインタを新しい Node を指すようにします。}それ以外{Node * p = head ; // head ノードポインタを Node ポインタ 'p' に代入します。while ( p -> next ) {p = p -> next ; // p が最後のノードになるまでリストを走査します。最後のノードは常に NULL を指します。}p -> next = temp ; // 以前の最後のノードを新しいノードを指すようにします。}return head ; // ヘッドノードポインタを返します。}

双方向リンクリストでは、各ノードは次のノードへのリンクに加えて、シーケンス内の「前の」ノードを指す2つ目のリンクフィールドを持ちます。この2つのリンクは、「前方」と「後方」、または「次」と「前」と呼ばれます。

XORリンクと呼ばれる手法を用いると、各ノードに単一のリンクフィールドを使用して二重リンクリストを実装できます。ただし、この手法はアドレスに対するビット演算機能を必要とするため、一部の高級言語では利用できない場合があります。

多くの最新のオペレーティングシステムは、アクティブなプロセス、スレッド、その他の動的オブジェクトへの参照を維持するために二重リンクリストを使用します。^{[ 4 ]}ルートキットが検出を回避するための一般的な戦略は、これらのリストから自分自身をリンク解除することです。^{[ 5 ]}

「多重リンクリスト」では、各ノードに2つ以上のリンクフィールドが含まれており、各フィールドは、異なる順序（名前順、部署順、生年月日順など）で並べられた同じデータセットを接続するために使用されます。二重リンクリストは多重リンクリストの特殊なケースと見なすことができますが、2つ以上の順序が互いに逆であるため、よりシンプルで効率的なアルゴリズムが実現できるため、通常は別のケースとして扱われます。

連結リストの最後のノードでは、リンクフィールドには多くの場合、それ以上のノードがないことを示す特殊な値であるヌル参照が含まれます。あまり一般的ではない慣習として、リンクフィールドをリストの最初のノードを指すようにすることもあります。その場合、リストは「循環的」または「循環連結」と呼ばれ、そうでない場合は「オープン」または「線形」と呼ばれます。これは、最後のノードポインタが最初のノードを指しているリストです（つまり、最後のノードの「次のノードへのリンク」ポインタは、最初のノードのメモリ アドレスを持っています）。

循環二重リンクリストの場合、最初のノードはリストの最後のノードも指しています。

実装によっては、最初のデータレコードの前または最後のデータレコードの後に​​、追加の「番兵」または「ダミー」ノードが追加される場合があります。この慣例により、すべてのリンクを安全に逆参照できること、およびすべてのリスト（データ要素を含まないリストであっても）に必ず「最初」ノードと「最後」ノードが存在することが保証されるため、一部のリスト処理アルゴリズムが簡素化され、高速化されます。

空のリストとは、データレコードを一切含まないリストのことです。これは通常、ノードがゼロ個であることと同じです。番兵ノードが使用されている場合、リストに番兵ノードのみが含まれている場合、そのリストは空であるとみなされます。

リンクフィールドは、ノードの物理的な一部である必要はありません。データレコードが配列に格納され、インデックスによって参照される場合、リンクフィールドはデータレコードと同じインデックスを持つ別の配列に格納できます。

最初のノードへの参照によってリスト全体にアクセスできるため、その参照はリストの「アドレス」、「ポインタ」、または「ハンドル」と呼ばれることがよくあります。連結リストを操作するアルゴリズムは通常、入力リストへのハンドルを取得し、結果リストへのハンドルを返します。実際、このようなアルゴリズムの文脈では、「リスト」という言葉はしばしば「リストハンドル」を意味します。ただし、場合によっては、リストの最初と最後のノードを指す2つのリンクで構成されるハンドルでリストを参照する方が便利な場合もあります。

上記に挙げた選択肢は、ほぼあらゆる方法で任意に組み合わせることができるため、番兵のない循環二重リンクリスト、番兵のある循環単方向リンクリストなどを作成できます。

動的配列は、すべての要素をメモリ上に連続して割り当て、現在の要素数を保持するデータ構造です。動的配列用に確保された領域を超えると、再割り当てと（場合によっては）コピーが行われますが、これはコストのかかる操作です。

リンクリストは、動的配列に比べていくつかの利点があります。リストの特定の位置への要素の挿入または削除は、ポインタが既にノード（削除対象のノードの前、または挿入位置の前）を指している場合、定数時間で実行できます（この参照がない場合はO(n)になります）。一方、動的配列にランダムな位置に要素を挿入する場合、平均して要素の半分、最悪の場合はすべての要素を移動する必要があります。要素を何らかの方法で「空き」としてマークすることで、配列から要素を定数時間で「削除」することはできますが、これにより断片化が発生し、反復処理のパフォーマンスが低下します。

さらに、連結リストには使用可能なメモリの総量によってのみ制限されるものの、任意の数の要素を挿入できます。一方、動的配列は最終的に基となる配列データ構造がいっぱいになり、再割り当てが必要になります。これはコストのかかる操作であり、メモリが断片化している場合は不可能な場合もあります。ただし、再割り当てのコストは挿入ごとに平均化でき、再割り当てによる挿入のコストは依然として償却O(1)になります。これは配列の末尾に要素を追加する際には役立ちますが、データの連続性を維持するためにデータが移動するため、中間位置への挿入（または中間位置からの削除）には依然として非常に高いコストがかかります。多くの要素が削除された配列は、スペースの無駄遣いを避けるためにサイズ変更が必要になる場合もあります。

一方、動的配列（および固定サイズの配列データ構造）は定数時間でランダムアクセスが可能ですが、連結リストは要素へのシーケンシャルアクセスしかできません。実際、単方向連結リストは一方向にしか簡単に走査できません。そのため、ヒープソートのようにインデックスで要素を素早く検索することが有用なアプリケーションには、連結リストは適していません。また、配列や動的配列は参照の局所性が最適であるため、データキャッシュを有効活用でき、多くのマシンでシーケンシャルアクセスが連結リストよりも高速です。

リンクリストのもう 1 つの欠点は、参照に必要な追加のストレージです。リンクのストレージのオーバーヘッドがデータのサイズの 2 倍以上になる可能性があるため、文字やブール値などの小さなデータ項目のリストには実用的ではないことがよくあります。対照的に、動的配列はデータ自体 (およびごく少量の制御データ) のスペースのみを必要とします。^{[注 1 ]}また、新しい要素ごとに個別にメモリを割り当てると遅くなり、単純なアロケータでは無駄になる可能性があり、この問題は一般的にメモリ プールを使用して解決されます。

ハイブリッドソリューションの中には、2つの表現形式の利点を組み合わせようとするものがあります。展開されたリンクリストは、各リストノードに複数の要素を格納することで、キャッシュのパフォーマンスを向上させつつ、参照のためのメモリオーバーヘッドを削減します。CDRコーディングも同様に、参照を、参照レコードの末尾を超えて拡張される実際の参照データに置き換えることで、これらの利点を両方実現します。

動的配列と連結リストの長所と短所を際立たせる良い例として、ヨセフス問題を解決するプログラムを実装してみましょう。ヨセフス問題は、円になって立つ人々のグループによって行われる選挙方法です。あらかじめ決められた人物から始めて、円をn回数えます。n番目の人物に到達したら、その人物を円から外し、円を閉じます。このプロセスは、1人だけが残るまで繰り返されます。残った人が選挙に勝ちます。これは、連結リストと動的配列の長所と短所を示しています。人々を円形連結リスト内の接続されたノードと見なすと、連結リストがノードをいかに簡単に削除できるかがわかります（異なるノードへのリンクを再配置するだけで済むため）。しかし、連結リストは次に削除する人物を見つけるのが苦手で、その人物が見つかるまでリストを検索する必要があります。一方、動的配列は、ノード（または要素）の削除が苦手です。すべての要素を個別に1つずつ上に移動させなければ、1つのノードを削除できないためです。しかし、配列内の位置を直接参照することで、円の中のn番目の人物を見つけるのは非常に簡単です。

リストランキング問題とは、連結リスト表現を効率的に配列に変換する問題である。従来のコンピュータにとっては容易な問題だが、並列アルゴリズムを用いてこの問題を解決するのは複雑であり、多くの研究の対象となってきた。

バランスのとれた木は、リンクリストと同様のメモリアクセスパターンとスペースオーバーヘッドを持ちながら、インデックス付けがはるかに効率的で、ランダムアクセスにO(n)ではなくO(log n)の時間しかかかりません。ただし、バランスを維持するための木の操作オーバーヘッドのため、挿入と削除の操作はよりコストがかかります。木が自動的にバランス状態を維持する仕組みも存在します。AVL木や赤黒木などがその例です。

二重リンクリストと循環リストは単方向リンク線形リストに比べて利点があるが、線形リストにもいくつかの利点があり、状況によってはそちらの方が好ましい場合もある。

単方向連結線形リストは、同じ型のより小さなオブジェクトへのポインタを含むため、再帰的なデータ構造です。そのため、単方向連結線形リストに対する多くの操作（2つのリストのマージや要素の逆順列挙など）は、反復コマンドを使用するソリューションよりもはるかに単純な再帰アルゴリズムで実現できます。これらの再帰的なソリューションは、双方向連結リストや循環連結リストにも適用できますが、一般的に追加の引数とより複雑な基本ケースが必要になります。

線形単方向連結リストでは、サブリストの共通の末尾部分を2つの異なるリストの末尾部分として使用できる末尾共有も可能です。具体的には、リストの先頭に新しいノードが追加された場合、以前のリストは新しいリストの末尾として引き続き使用できます。これは、永続的なデータ構造の簡単な例です。繰り返しますが、これは他のバリアントでは当てはまりません。ノードが2つの異なる循環リストや双方向連結リストに属することは決してありません。

特に、末尾の番兵ノードは、単方向リンクの非循環リスト間で共有できます。同じ末尾の番兵ノードを、そのようなすべてのリストに使用できます。たとえば、 Lispnilでは、すべての適切なリストは、またはで表される特別なノードへのリンクで終わります()。

高度な手法の利点は、多くの場合、アルゴリズムの複雑さに限られ、効率性には関係しません。特に循環リストは、通常、最初のノードと最後のノードを指す2つの変数を持つ線形リストで、追加コストなしでエミュレートできます。

二重リンクリストは、ノードごとに多くのスペースを必要とし（XORリンクを使用しない限り）、基本操作のコストも高くなります。しかし、双方向でリストに高速かつ容易に順次アクセスできるため、操作が容易な場合が多いです。二重リンクリストでは、ノードのアドレスさえあれば、一定回数の操作でノードを挿入または削除できます。単方向リンクリストで同じ操作を行うには、そのノードへのポインタのアドレスが必要です。これは、最初のノードの場合はリスト全体のハンドル、前のノードの場合は前のノードのリンクフィールドのいずれかです。一部のアルゴリズムでは、双方向のアクセスが必要です。一方、二重リンクリストは末尾共有を許可せず、永続的なデータ構造として使用することはできません。

循環連結リストは、多角形の頂点、 FIFO（先入れ先出し）順で使用および解放されるバッファプール、ラウンドロビン方式でタイムシェアリングされるべきプロセス群など、本質的に循環的な配列を表現するための自然な選択肢となり得ます。これらのアプリケーションでは、任意のノードへのポインタがリスト全体へのハンドルとして機能します。

循環リストでは、最後のノードへのポインターから、1つのリンクをたどるだけで最初のノードにも簡単にアクセスできます。そのため、リストの両端へのアクセスが必要なアプリケーション（例えば、キュ​​ーの実装など）では、循環構造を用いることで、2つのポインターではなく、1つのポインターで構造を操作できます。

循環リストは、各部分の最後のノードのアドレスを指定することで、定数時間で2つの循環リストに分割できます。この操作は、2つのノードのリンクフィールドの内容を交換することによって行われます。2つの異なるリストの任意の2つのノードに同じ操作を適用すると、2つのリストが1つに結合されます。この特性により、クワッドエッジやフェイスエッジなどのアルゴリズムやデータ構造が大幅に簡素化されます。

空の循環リスト（そのような概念が意味を成す場合）を表す最も単純な方法は、リストにノードがないことを示すヌルポインタを用いることです。この方法を用いない場合、多くのアルゴリズムはこの特殊なケースをテストし、個別に処理する必要があります。一方、空の線形リストを表すのにヌルを用いる方がより自然であり、特殊なケースも少なくて済みます。

アプリケーションによっては、単方向連結リストが有用な場合があります。単方向連結リストは、循環型と線形型、あるいは初期セグメントが線形である循環型など、様々な形状をとることができます。このようなリストを検索したり操作したりするアルゴリズムでは、意図せず無限ループに陥らないように注意する必要があります。よく知られている方法の一つは、リストを半分の速度または2倍の速度で走査する2つ目のポインタを用意し、両方のポインタが同じノードに到達した場合に循環が見つかったと判断するというものです。

番兵ノードは、すべての要素に対して次または前のノードが存在すること、および空のリストにも少なくとも1つのノードが存在することを保証することで、特定のリスト操作を簡素化できます。また、リストの末尾に適切なデータフィールドを持つ番兵ノードを使用することで、リストの末尾判定の一部を省略することもできます。たとえば、リストをスキャンして特定の値xを持つノードを探す場合、番兵のデータフィールドをxに設定することで、ループ内でリストの末尾判定を行う必要がなくなります。別の例として、2つのソート済みリストをマージする場合、番兵のデータフィールドが +∞ に設定されていれば、次の出力ノードの選択において空のリストに対する特別な処理は不要になります。

しかし、番兵ノードは余分なスペースを消費し（特に多くの短いリストを使用するアプリケーションの場合）、他の操作（新しい空のリストの作成など）を複雑にする可能性があります。

しかし、循環リストを単に線形リストのシミュレートするために使用する場合は、各リストの最後のデータノードと最初のデータノードの間に単一の番兵ノードを追加することで、この複雑さの一部を回避できます。この規則では、空のリストは番兵ノードのみで構成され、次のノードへのリンクを介して自身を指します。リストハンドルは、リストが空でない場合は番兵ノードの前の最後のデータノードへのポインタ、リストが空の場合は番兵ノード自体へのポインタになります。

同じ手法は、二重リンク線形リストを単一の番兵ノードを持つ循環二重リンクリストに変換することで、その処理を簡素化するためにも使用できます。ただし、この場合、ハンドルはダミーノード自体への単一のポインタである必要があります。^{[ 8 ]}

循環連結リストでは、すべてのノードがヌルを使用せずに連続した円状に連結されます。先頭と末尾を持つリスト（キューなど）の場合、リストの最後のノードへの参照を格納します。最後のノードの次のノードが最初のノードになります。要素は定数時間でリストの末尾に追加したり、先頭から削除したりできます。

循環リンクリストは、単方向リンクまたは双方向リンクのいずれかになります。

どちらのタイプの循環連結リストも、任意のノードからリスト全体を走査できるという利点があります。これにより、 firstNodeとlastNode を格納する必要がなくなる場合が多くなりますが、リストが空になる可能性がある場合は、空のリストを表す特別な表現が必要になります。例えば、リスト内のノードを指す、または空の場合はnull となるlastNode変数などです。ここでは、そのようなlastNodeを使用しています。この表現により、空でないリストでのノードの追加と削除が大幅に簡素化されますが、空のリストは特別なケースとなります。

function iterate(someNode) if someNode ≠ null node := someNode する node.value を使って何かを行う node := node.next ノードがsomeNodeと異なる間

function insertAfter( Node node, Node newNode) if node = null // リストが空であると仮定します newNode.next := newNode それ以外 newNode.next := node.next node.next := newNode必要に応じてlastNode変数 を更新する

insertAfter(L, newNode) L := newNode

insertAfter(L, newNode) if L = null L := newNode

function insertBefore( Node node, newVal) if node = null // リストが空であると仮定します newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal node.next := newNode必要に応じてfirstNode変数 を更新してください。

function remove( Node node) if node ≠ null and size of list > 1 removedData := node.data node.data := node.next.data node.next = node.next.next 削除されたデータを返す

参照をサポートしない言語でも、ポインタを配列インデックスに置き換えることでリンクを作成できます。この方法は、レコードの配列を保持し、各レコードに配列内の次の（場合によっては前の）ノードのインデックスを示す整数フィールドを持たせるというものです。配列内のすべてのノードを使用する必要はありません。レコードもサポートされていない場合は、代わりに並列配列を使用できる場合が多くあります。

例として、ポインタの代わりに配列を使用した以下のリンクリストレコードを考えてみましょう。

record Entry { integer next; // 配列内の次のエントリのインデックスinteger prev; // 前のエントリ (二重リンクの場合) string name; real balance; }

これらの構造体の配列を作成し、最初の要素のインデックスを格納する整数変数を用意することで、連結リストを構築できます。

整数リスト ヘッダー エントリレコード[1000]

要素間のリンクは、次の（または前の）セルの配列インデックスを、特定の要素内の「次へ」または「前へ」フィールドに配置することによって形成されます。例：

上記の例では、ListHeadはリストの最初のエントリの位置である 2 に設定されます。エントリ 3 と 5 ～ 7 はリストに含まれていないことに注意してください。これらのセルは、リストへの追加に使用できます。ListFree整数型の変数を作成することで、使用可能なセルを追跡するためのフリーリストを作成できます。すべてのエントリが使用されている場合は、新しいエントリをリストに格納する前に、配列のサイズを増やすか、一部の要素を削除する必要があります。

以下のコードはリストを走査し、名前と口座残高を表示します。

i := listHead while i ≥ 0 // リストをループ処理 print i, Records[i].name, Records[i].balance // エントリを出力 i := Records[i].next

選択を迫られた場合、このアプローチの利点は以下のとおりです。

• リンクリストは再配置可能であり、メモリ内で自由に移動できるだけでなく、ディスクへの保存やネットワーク経由での転送のために、迅速かつ直接的にシリアル化することもできます。
• 特にリストが小さい場合、配列インデックスは多くのアーキテクチャにおいて、完全なポインタよりも大幅に少ないスペースしか占有しない。
• 参照の局所性は、ノードをメモリ内でまとめて保持し、定期的に再配置することによって改善できるが、これは汎用ストアでも行うことができる。
• 単純な動的メモリ割り当てでは、割り当てられるノードごとに過剰なオーバーヘッドストレージが発生する可能性がありますが、このアプローチではノードごとの割り当てオーバーヘッドはほとんど発生しません。
• 事前に割り当てられた配列からエントリを取得する方が、各ノードに動的メモリ割り当てを行うよりも高速です。なぜなら、動的メモリ割り当てでは通常、目的のサイズの空きメモリブロックを検索する必要があるからです。

しかし、このアプローチには大きな欠点が1つあります。それは、ノードごとに専用のメモリ空間を作成・管理する必要があることです。これにより、以下のような問題が発生します。

• 実装の複雑さが増す。
• 配列がいっぱいになったときに、それを拡張するのは困難または不可能な場合がある一方、大きな汎用メモリプール内で新しいリンクリストノードのためのスペースを見つけるのは比較的容易な場合がある。
• 動的配列に要素を追加すると、配列がいっぱいになったときなどに、定数時間ではなく線形時間（ O (n)）がかかることがあります（ただし、償却定数時間であることに変わりはありません）。
• 汎用メモリプールを使用すると、リストのサイズが予想よりも小さい場合や、多くのノードが解放された場合に、他のデータに使用できるメモリが増えます。

こうした理由から、この手法は主に動的メモリ割り当てをサポートしていない言語で使用されます。また、配列作成時にリストの最大サイズが既知であれば、これらの欠点は軽減されます。

内部ストレージを使用して、家族とそのメンバーのリンクリストを作成する場合、構造は次のようになります。

レコードメンバー{ // 家族のメンバーnext ; string firstName; integer age; } record family { // 家族自体family next; string lastName; string address; member members // この家族のメンバーリストの先頭 }

内部ストレージを使用して家族とそのメンバーの完全なリストを印刷するには、次のように入力します。

aFamily := Families // 家族リストの先頭から開始while aFamily ≠ null // 家族リストをループ処理 家族に関する情報を印刷する aMember := aFamily.members // この家族のメンバーのリストの先頭を取得while aMember ≠ null // メンバーのリストをループ処理 会員に関する情報を印刷する aMember := aMember.next aFamily := aFamily.next

外部ストレージを使用すると、以下の構造を作成できます。

レコードノード{ // 一般的なリンク構造ノードネスト; ポインタデータ// ノード内のデータへの一般的なポインタ } レコードメンバー{ // 家族メンバーの構造string firstName; integer age } record family { // 家族の構造string lastName; string address; node members // この家族のメンバーリストの先頭 }

外部ストレージを使用して家族とそのメンバーの完全なリストを印刷するには、次のように入力します。

famNode := Families // 家族リストの先頭から開始while famNode ≠ null // 家族リストをループ aFamily := (family) famNode.data // ノードから家族を抽出 家族に関する情報を印刷する memNode := aFamily.members // 家族メンバーのリストを取得while memNode ≠ null // メンバーのリストをループ処理 aMember := (member)memNode.data // ノードからメンバーを抽出 会員に関する情報を印刷する memNode := memNode.next famNode := famNode.next

外部ストレージを使用する場合、ノードからレコードを抽出して適切なデータ型にキャストするために、追加の手順が必要になることに注意してください。これは、ファミリーのリストとファミリー内のメンバーのリストの両方が、同じデータ構造（ノード）を使用する2つのリンクリストに格納されており、この言語にはパラメトリック型がないためです。

メンバーが所属できるファミリーの数がコンパイル時に分かっている限り、内部ストレージで問題ありません。しかし、メンバーを任意の数のファミリーに含める必要があり、その具体的な数が実行時にしか分からない場合は、外部ストレージが必要になります。

連結リスト内の特定の要素を見つけるには、たとえソート済みであっても、通常はO( n )の時間（線形探索）が必要です。これは、連結リストが他のデータ構造に比べて抱える主な欠点の1つです。上記で説明したバリエーションに加えて、検索時間を改善する2つの簡単な方法を以下に示します。

順序付けされていないリストにおいて、平均検索時間を短縮するためのシンプルなヒューリスティックの一つに、要素が見つかったらリストの先頭に移動させる「先頭移動」というヒューリスティックがあります。この方法は、シンプルなキャッシュを作成する際に便利で、最近使用した項目を最も早く見つけられるようにします。

もう一つの一般的なアプローチは、より効率的な外部データ構造を使用してリンクリストに「インデックス」を付けることです。例えば、リンクリストのノードへの参照を要素とする赤黒木やハッシュテーブルを構築できます。このようなインデックスは、1つのリスト上に複数作成できます。欠点は、ノードが追加または削除されるたび（あるいは少なくとも、そのインデックスが再び使用される前）に、これらのインデックスを更新する必要がある場合があることです。

ランダムアクセスリストは、リスト内の任意の要素を読み取ったり変更したりするための高速ランダムアクセスをサポートするリストです。^{[ 9 ]}可能な実装の 1 つは、特殊な特性を持つツリーのリストを含む、スキューバイナリ数システムを使用したスキューバイナリランダムアクセスリストです。これにより、最悪の場合定数時間のヘッド/コンス操作と、インデックスによる要素への最悪の場合対数時間のランダムアクセスが可能になります。^{[ 9 ]}ランダムアクセスリストは、永続データ構造として実装できます。^{[ 9 ]}

ランダムアクセスリストは、同じO(1)の先頭操作と末尾操作をサポートするという点で、不変リンクリストと見なすことができる。^{[ 9 ]}

ランダムアクセスリストの簡単な拡張として、min-listがあります。これは、リスト全体の最小要素を定数時間で取得する追加の操作を提供します (変更の複雑さはありません)。^{[ 9 ]}