リンクリスト

コンピュータサイエンスにおいて、リンクリストとは、メモリ内の物理的な配置によって順序が指定されないデータ要素の線形コレクションです。代わりに、各要素は次の要素を指します。これは、一緒になってシーケンスを表すノードのコレクションで構成されるデータ構造です。最も基本的な形式では、各ノードにはデータと、シーケンス内の次のノードへの参照（つまり、リンク）が含まれます。この構造により、反復中にシーケンス内の任意の位置から要素を効率的に挿入または削除できます。より複雑なバリアントでは、追加のリンクが追加され、任意の位置でノードをより効率的に挿入または削除できます。リンクリストの欠点は、データアクセス時間がリスト内のノードの数に対して線形であることです。ノードはシリアルにリンクされているため、どのノードにアクセスするにも、事前に前のノードにアクセスする必要があります（これにより、パイプラインが困難になります）。ランダムアクセスなどの高速アクセスは実現できません。配列は、リンクリストと比較して キャッシュの局所性が優れています。

リンク リストは、最も単純で最も一般的なデータ構造の 1 つです。リンク リストは、リスト、スタック、キュー、連想配列、S 式など、他の一般的な抽象データ型を実装するために使用できますが、リンク リストを基礎として使用せずにこれらのデータ構造を直接実装することも珍しくありません。

従来の配列と比較したリンク リストの主な利点は、データ項目をメモリまたはディスクに連続して格納する必要がないため、構造全体を再割り当てまたは再編成することなく、リスト要素を簡単に挿入または削除できることです。一方、実行時に配列を再構築すると、はるかにコストのかかる操作になります。リンク リストでは、リスト内の任意のポイントでノードの挿入と削除が可能で、リストのトラバース中にメモリに追加または削除されるリンクの前のリンクを保持することで、定数の操作数で挿入と削除を実行できます。

一方、単純なリンク リストだけではデータへのランダム アクセスや効率的なインデックス作成が不可能なため、リストの最後のノードの取得、特定のデータを含むノードの検索、新しいノードを挿入する場所の特定など、多くの基本操作ではリスト要素のほとんどまたはすべてを反復処理する必要がある場合があります。

リンク リストは、1955 年から 1956 年にかけて、RAND 社とカーネギー メロン大学のAllen Newell、Cliff Shaw、Herbert A. Simonによって、情報処理言語(IPL)の主要なデータ構造として開発されました。著者らは IPL を使用して、Logic Theory Machine、General Problem Solver 、コンピュータ チェス プログラムなど、いくつかの初期の人工知能プログラムを開発しました。著者らの研究成果は、1956 年の IRE Transactions on Information Theory、1957 年から 1959 年にかけてのいくつかの会議の議事録 (1957 年と 1958 年の Proceedings of the Western Joint Computer Conference、1959 年の Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) など) に掲載されました。現在では定番となっている、リスト ノードを表すブロックと、後続のリスト ノードを指す矢印で構成される図は、Newell と Shaw が Proc. WJCC、1957 年 2 月。ニューウェルとサイモンは、1975 年に「人工知能、人間の認知心理学、リスト処理への基本的な貢献」によりACMチューリング賞を受賞しました。自然言語処理のための機械翻訳の問題から、マサチューセッツ工科大学(MIT)のビクター・イングヴェは、言語学の分野でのコンピューター研究のために COMIT プログラミング言語でリンク リストをデータ構造として使用するようになりました。この言語に関するレポート「機械翻訳のためのプログラミング言語」が 1958 年の Mechanical Translation に掲載されました。^{[引用が必要]}

リンクリストのもう一つの初期の登場は、1953年1月にIBMの社内メモを書いたハンス・ピーター・ルーンによるもので、連鎖ハッシュテーブルでリンクリストを使用することを提案した。^[1]

LISPはリストプロセッサの略で、 1958年にジョン・マッカーシーがMIT在籍中に考案し、1960年に「Communications of the ACM」誌に「記号式の再帰関数と機械による計算、パート1」と題する論文でその設計を発表しました。LISP の主要なデータ構造の1つはリンクリストです。

1960 年代初頭までに、リンク リストと、これらの構造を主なデータ表現として使用する言語の両方の有用性が確立されました。MITリンカーン研究所のバート グリーンは、1961 年 3 月に IRE Transactions on Human Factors in Electronics に「シンボル操作のためのコンピュータ言語」と題するレビュー記事を発表し、リンク リスト アプローチの利点をまとめました。その後のレビュー記事、ボブロウとラファエルによる「リスト処理コンピュータ言語の比較」は、1964 年 4 月に Communications of the ACM に掲載されました。

Technical Systems Consultants (当初はインディアナ州ウェストラファイエット、後にノースカロライナ州チャペルヒルに移転)が開発したいくつかのオペレーティング システムでは、ファイル構造として片側リンク リストが使用されていました。ディレクトリ エントリはファイルの最初のセクターを指し、ファイルの後続部分はポインタをトラバースすることで見つけられました。この手法を使用するシステムには、Flex ( Motorola 6800 CPU 用)、mini-Flex (同じ CPU)、Flex9 (Motorola 6809 CPU 用) などがあります。TSC が開発し、カリフォルニア州のSmoke Signal Broadcastingが販売した変種では、同様に双方向リンク リストが使用されていました。

IBM が System 360/370 マシン用に開発した TSS/360 オペレーティング システムでは、ファイル システム カタログに二重リンク リストが使用されていました。ディレクトリ構造は Unix に似ており、ディレクトリにはファイルと他のディレクトリを含めることができ、任意の深さまで拡張できます。

リンク リストの各レコードは、多くの場合、「要素」または「ノード」と呼ばれます。

次のノードのアドレスを含む各ノードのフィールドは、通常、「次のリンク」または「次のポインタ」と呼ばれます。残りのフィールドは、「データ」、「情報」、「値」、「貨物」、または「ペイロード」フィールドと呼ばれます。

リストの「ヘッド」は、リストの最初のノードです。リストの「テール」は、リストのヘッドの後の残りの部分、またはリストの最後のノードのいずれかを指します。Lisp およびいくつかの派生言語では、リストの次のノードは「 cdr」（発音は/'kʊd.əɹ/ ）と呼ばれ、ヘッド ノードのペイロードは「 car 」と呼ばれることがあります。

単一リンク リストには、ノードの行の次のノードを指す「値」フィールドと「次」フィールドを持つノードが含まれます。単一リンク リストで実行できる操作には、挿入、削除、トラバーサルなどがあります。

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

// リンク リスト内の各ノードは構造体です。ヘッド ノードはリストの最初のノードです。

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

「二重リンクリスト」では、各ノードには、次のノードへのリンクの他に、シーケンス内の「前の」ノードを指す 2 番目のリンク フィールドが含まれます。2 つのリンクは、「forward('s')」と「backwards」、または「next」と「prev('previous')」と呼ばれることがあります。

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

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

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

リンク リストの最後のノードでは、リンク フィールドにnull参照が含まれることが多く、特別な値を使用してそれ以上のノードがないことを示します。あまり一般的ではない規則として、リストの最初のノードを指すようにする方法があります。この場合、リストは「循環」または「循環的にリンク」されていると言われます。それ以外の場合は、「オープン」または「線形」であると言われます。これは、最後のノード ポインターが最初のノードを指すリストです(つまり、最後のノードの「次のリンク」ポインターには、最初のノードのメモリ アドレスがあります)。

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

一部の実装では、最初のデータ レコードの前または最後のデータ レコードの後に​​、追加の「センチネル」ノードまたは「ダミー」ノードが追加されることがあります。この規則により、すべてのリンクを安全に逆参照でき、すべてのリスト (データ要素が含まれていないものも含む) に常に「最初」のノードと「最後」のノードが含まれるようになるため、一部のリスト処理アルゴリズムが簡素化され、高速化されます。

空のリストとは、データ レコードが含まれていないリストです。これは通常、ノードが 0 個あることと同じです。センチネル ノードが使用されている場合、リストにセンチネル ノードのみが含まれているときは通常、リストは空であると言われます。

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

最初のノードへの参照はリスト全体へのアクセスを与えるので、その参照はリストの「アドレス」、「ポインター」、または「ハンドル」と呼ばれることがよくあります。リンク リストを操作するアルゴリズムは通常、入力リストへのハンドルを取得し、結果のリストへのハンドルを返します。実際、このようなアルゴリズムのコンテキストでは、「リスト」という単語は「リスト ハンドル」を意味することがよくあります。ただし、状況によっては、最初のノードと最後のノードを指す 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 つに結合されます。この特性により、クアッド エッジやフェイス エッジなどの一部のアルゴリズムとデータ構造が大幅に簡素化されます。

空の循環リストの最も単純な表現は(それが意味をなす場合)、リストにノードがないことを示す null ポインターです。この選択肢がなければ、多くのアルゴリズムはこの特殊なケースをテストし、個別に処理する必要があります。対照的に、空の線形リストを示すために null を使用する方が自然であり、特殊なケースが少なくなることがよくあります。

アプリケーションによっては、循環型と線形型、または線形の初期セグメントを持つ循環型の間で変化する単一リンク リストを使用すると便利な場合があります。これらのリストを検索または操作するアルゴリズムでは、誤って無限ループに陥らないように注意する必要があります。よく知られている方法の1 つは、2 番目のポインターでリストを半分または 2 倍の速度で移動し、両方のポインターが同じノードで出会ったら、サイクルが見つかったと判断することです。

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

ただし、センチネル ノードは余分なスペースを消費し (特に、多数の短いリストを使用するアプリケーションの場合)、他の操作 (新しい空のリストの作成など) を複雑にする可能性があります。

ただし、循環リストが線形リストをシミュレートするためだけに使用される場合は、最後のデータ ノードと最初のデータ ノードの間に、すべてのリストに 1 つのセンチネル ノードを追加することで、この複雑さをある程度回避できます。この規則では、空のリストはセンチネル ノードのみで構成され、次のノード リンクを介してそれ自体を指します。リスト ハンドルは、リストが空でない場合は、センチネルの前の最後のデータ ノードへのポインターになります。リストが空の場合は、センチネル自体へのポインターになります。

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

リンク リストをインプレースで操作する場合、以前の割り当てで無効にした値を使用しないように注意する必要があります。これにより、リンク リスト ノードを挿入または削除するアルゴリズムが多少複雑になります。このセクションでは、単一、二重、および循環リンク リストからインプレースでノードを追加または削除するための疑似コードを示します。全体を通して、リストの終了マーカーまたはセンチネルを参照するためにnull を使用します。これは、さまざまな方法で実装できます。

ノード データ構造には 2 つのフィールドがあります。また、リストの最初のノードを常に指す変数firstNodeも保持します。空のリストの場合は nullになります。

レコード ノード
{
    data; // ノードに格納されているデータ
    Node next //次のノードへの参照[2] 、最後のノードの場合はnull
}

レコード リスト
{
    Node firstNode // リストの最初のノードを指します。空のリストの場合は null です。
}

単一リンク リストのトラバースは簡単で、最初のノードから始まり、次の各リンクを最後までたどります。

node := list.firstNode
だがnode は null ではない
    (node.data で何かする)
    ノード := ノード.next

次のコードは、単方向リンク リスト内の既存のノードの後に​​ノードを挿入します。図は、その動作を示しています。既存のノードの前にノードを直接挿入することはできません。代わりに、前のノードを追跡し、その後にノードを挿入する必要があります。

function insertAfter( Node node, Node newNode) // ノードの後に​​newNodeを挿入する
    新しいノードの次:=ノードの次
    ノードの次:=新しいノード

リストの先頭に挿入するには別の関数が必要です。これにはfirstNode を更新する必要があります。

function insertBeginning( List list, Node newNode) // 現在の最初のノードの前にノードを挿入する
    newNode.next := list.firstNode
    リスト.firstNode := newNode

同様に、特定のノードの後のノードを削除する関数と、リストの先頭からノードを削除する関数があります。図は前者を示しています。特定のノードを見つけて削除するには、前の要素を追跡する必要があります。

function removeAfter( Node node) // このノードの後ろのノードを削除する
    廃止されたノード:= node.next
    ノード.next := ノード.next.next
    廃止されたノードを破棄する

function removeBeginning( List list) // 最初のノードを削除
    廃止されたノード:= list.firstNode
    list.firstNode := list.firstNode.next // 削除されたノードの先を指す
    廃止されたノードを破棄する

リスト内の最後のノードを削除するときに が にremoveBeginning()設定されることに注意してください。list.firstNodenull

後方への反復処理ができないため、効率的なinsertBeforeorremoveBefore操作は不可能です。特定のノードの前にリストを挿入するには、リストをトラバースする必要があり、最悪の場合、実行時間は O(n) になります。

連結リストを別の連結リストに追加する場合、末尾への参照がリスト構造の一部として保持されていないと、効率が悪くなることがあります。これは、末尾を見つけるために最初のリスト全体を走査し、次に 2 番目のリストをこれに追加する必要があるためです。したがって、2 つの線形連結リストがそれぞれの長さ である場合、リスト追加の漸近時間計算量は です。Lisp ファミリーの言語では、リスト追加は手順によって提供されます。 ${\displaystyle n}$${\displaystyle O(n)}$append

リンク リスト操作の特殊なケースの多くは、リストの先頭にダミー要素を含めることで排除できます。これにより、リストの先頭に特殊なケースがなくなり、 と の両方が不要になりますinsertBeginning()。removeBeginning()つまり、すべての要素またはノードは別のノードの隣にあります (最初のノードがダミー ノードの隣にある場合も含む)。この場合、リストの最初の有用なデータは にあります。 list.firstNode.next

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

循環リンク リストは、単一リンクまたは二重リンクのいずれかになります。

どちらのタイプの循環リンク リストも、任意のノードからリスト全体をトラバースできるという利点があります。これにより、多くの場合、firstNodeとlastNodeの保存を回避できますが、リストが空になる可能性がある場合は、リスト内のノードを指す lastNode 変数や、空の場合はnull になるlastNode変数など、空のリストの特別な表現が必要になります。ここでは、そのようなlastNode を使用します。この表現により、空でないリストでのノードの追加と削除が大幅に簡素化されますが、空のリストは特別なケースになります。

someNode が空でない循環単方向リンク リスト内のノードであると仮定すると、このコードはsomeNodeから始まるリストを反復処理します。

someNode ≠ nullの場合、関数iterate(someNode)
    
        ノード := someNode
    する
        node.valueを使って何かする
        ノード := ノード.next
    ノード≠someNode
の場合

テスト「while node ≠ someNode」はループの最後にある必要があることに注意してください。テストをループの先頭に移動すると、リストにノードが 1 つしかない場合は常に手順が失敗します。

この関数は、指定されたノード「node」の後に、循環リンク リストにノード「newNode」を挿入します。「node」が null の場合、リストは空であると想定されます。

function insertAfter( Node node, Node newNode)
     if node = null     // リストが空であると想定
        newNode.next := newNode
    それ以外
        新しいノードの次:=ノードの次
        ノードの次:=新しいノード必要に応じてlastNode変数

    を更新する

「L」が循環リンクリストの最後のノードを指す変数（リストが空の場合はnull）であるとします。リストの 最後に「newNode」を追加するには、次のようにします。

insertAfter(L, 新しいノード)
L := 新しいノード

リストの 先頭に「newNode」を挿入するには、次のようにします。

L = null の場合、 insertAfter(L, newNode)

    L := 新しいノード

この関数は、O(1) 時間で、指定されたノード「node」の前に値「newVal」を挿入します。「node」と次のノードの間に新しいノードを作成し、その新しいノードに「node」の値を入れ、「node」に「newVal」を入れます。したがって、firstNode変数のみを持つ単一リンクの循環リンク リストは、O(1) 時間で前方と後方の両方に挿入できます。

function insertBefore( Node node, newVal)
     if node = null     // リストが空であると仮定
        newNode := new Node(data:=newVal, next:=newNode)
    そうでない場合は
        newNode := new Node(data:=node.data, next:=node.next)
        ノードデータ:=新しい値
        ノードの次:=新しいノード必要に応じてfirstNode変数

    を更新する

この関数は、O(1) 時間で、サイズが 1 より大きいリストから null 以外のノードを削除します。次のノードからノードにデータをコピーし、ノードの次のポインタを設定して次のノードをスキップします。

ノードがnullでリストのサイズが 1より大きい場合、関数remove( Node node)
    を実行します。
        削除されたデータ:= node.data
        ノード.data := ノード.next.data
        ノード.next = ノード.next.next
        削除されたデータ
を返す

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

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

レコード エントリ{
    整数next; // 配列内の次のエントリのインデックス
    整数prev; // 前のエントリ（二重リンクされている場合）
    文字列name;
    実数balance;
}

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

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

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

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

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

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

選択に直面した場合、このアプローチの利点は次のとおりです。

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

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

• 実装の複雑さが増します。
• 大きな配列がいっぱいになったときにそれを拡張することは困難または不可能である可能性がありますが、大きな汎用メモリ プールで新しいリンク リスト ノード用のスペースを見つけることは簡単な場合があります。
• 動的配列に要素を追加すると、配列がいっぱいになったときに、定数時間ではなく線形時間 ( O (n)) が予期せずかかることがあります (それでも償却定数です)。
• 一般的なメモリ プールを使用すると、リストが予想よりも小さい場合や、多くのノードが解放されている場合に、他のデータ用により多くのメモリが残ります。

これらの理由から、このアプローチは主に、動的なメモリ割り当てをサポートしていない言語で使用されます。配列の作成時にリストの最大サイズがわかっている場合は、これらの欠点も軽減されます。

LispやSchemeなどの多くのプログラミング言語には、単方向リンク リストが組み込まれています。多くの関数型言語では、これらのリストはノードから構成され、各ノードはconsまたはcons セルと呼ばれます。cons には 2 つのフィールドがあります。carはノードのデータへの参照であり、cdr は次のノードへの参照です。cons セルは他のデータ構造の構築にも使用できますが、これが主な目的です。

抽象データ型またはテンプレートをサポートする言語では、リンク リスト ADT またはテンプレートを使用してリンク リストを構築できます。他の言語では、リンク リストは通常​​、レコードとともに参照を使用して構築されます。

リンク リストを構築する場合、リストのデータをリンク リスト ノード (内部ストレージと呼ばれる) に直接格納するか、データへの参照 (外部ストレージと呼ばれる) のみを格納するかという選択に直面します。内部ストレージの利点は、データへのアクセスがより効率的になること、全体的に必要なストレージが少なくて済むこと、参照の局所性が向上すること、リストのメモリ管理が簡素化されることです (リストのデータはリスト ノードと同時に割り当てられ、割り当て解除されます)。

一方、外部ストレージには、データのサイズに関係なく、同じデータ構造とマシン コードをリンク リストに使用できるという点で、より汎用的であるという利点があります。また、同じデータを複数のリンク リストに配置することも容易です。内部ストレージでは、ノード データ構造に複数の次の参照を含めることで、同じデータを複数のリストに配置することができますが、各フィールドに基づいてセルを追加または削除するための個別のルーチンを作成する必要があります。外部ストレージを使用して、内部ストレージを使用する要素の追加のリンク リストを作成し、追加のリンク リストのセルに、データを含むリンク リストのノードへの参照を格納することができます。

一般的に、データ構造のセットをリンク リストに含める必要がある場合、外部ストレージが最適なアプローチです。データ構造のセットを 1 つのリンク リストのみに含める必要がある場合、外部ストレージを使用する汎用リンク リスト パッケージが利用できない限り、内部ストレージの方が若干優れています。同様に、同じデータ構造に格納できる異なるデータ セットを 1 つのリンク リストに含める必要がある場合、内部ストレージで十分です。

一部の言語で使用できる別のアプローチでは、異なるデータ構造を持ちますが、すべての初期フィールドは同じ場所にあり、次の参照(および二重リンク リストの場合は前の参照) が含まれます。データのタイプごとに個別の構造を定義した後、他のすべての構造で共有され、構造の上部 (先頭) に含まれる最小限のデータを含む汎用構造を定義できます。次に、最小限の構造を使用してリンク リスト タイプの操作を実行する汎用ルーチンを作成できますが、個別のルーチンで特定のデータを処理できます。このアプローチは、メッセージ解析ルーチンでよく使用されます。このルーチンでは、複数のタイプのメッセージが受信されますが、すべてが同じフィールド セット (通常はメッセージ タイプのフィールドを含む) で始まります。汎用ルーチンは、新しいメッセージが受信されたときにキューに追加し、メッセージを処理するためにキューから削除するために使用されます。次に、メッセージ タイプ フィールドを使用して、特定のタイプのメッセージを処理するための適切なルーチンを呼び出します。

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

record  member { // 家族のメンバー
    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

外部ストレージを使用すると、次の構造が作成されます。

レコード ノード{ // 汎用リンク構造
    ノードnext;
    ポインタデータ// ノードのデータへの汎用ポインタ
}
record  member { // 家族メンバーの構造
    string firstName;
     integer age
}
レコード ファミリ{ // ファミリの構造
    string lastName;
     string address;
    ノードメンバー// このファミリのメンバーのリストの先頭
}

外部ストレージを使用して、ファミリとそのメンバーの完全なリストを印刷するには、次のように記述します。

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 つは、要素が見つかるとすぐにリストの先頭に移動する「先頭への移動」ヒューリスティックです。このスキームは、単純なキャッシュを作成するのに便利で、最近使用した項目が最も速く再び見つかることを保証します。

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

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

ランダムアクセスリストは、同様にO(1)のヘッドとテールの操作をサポートするという点で、不変のリンクリストと見なすことができます。^[9]

ランダムアクセスリストの単純な拡張はmin-listであり、これはリスト全体の最小の要素を定数時間で（^{[説明が必要]}変異の複雑さなしで）生成する追加の操作を提供します。^[9]

スタックとキューは両方ともリンク リストを使用して実装されることが多く、サポートされる操作の種類を単純に制限します。

スキップリストは、多数の要素をすばやく飛び越えて次の層に進むためのポインターの層が追加されたリンク リストです。このプロセスは、実際のリストである最下層まで続きます。

バイナリ ツリーは、要素自体が同じ性質のリンク リストであるリンク リストの一種と見ることができます。その結果、各ノードには、1 つまたは 2 つの他のリンク リストの最初のノードへの参照が含まれることがあり、それらの内容とともに、そのノードの下のサブツリーが形成されます。

アンロールされたリンク リストは、各ノードにデータ値の配列が含まれるリンク リストです。これにより、より多くのリスト要素がメモリ内で連続するためキャッシュパフォーマンスが向上し、リストの各要素に保存する必要があるメタデータが少なくなるためメモリ オーバーヘッドが削減されます。

ハッシュテーブルでは、ハッシュ テーブル内の同じ位置にハッシュされる項目のチェーンを格納するためにリンク リストが使用される場合があります。

ヒープはリンク リストの順序付けプロパティの一部を共有しますが、ほとんどの場合、配列を使用して実装されます。ノード間の参照の代わりに、次のデータ インデックスと前のデータ インデックスは、現在のデータのインデックスを使用して計算されます。

自己組織化リストは、何らかのヒューリスティックに基づいてノードを再配置し、よくアクセスされるノードをリストの先頭に保持することで、データ取得の検索時間を短縮します。

• Juan, Angel (2006)。「Ch20 –データ構造、ID06 - JAVA によるプログラミング (CayS. Horstmann 著『Big Java』のスライドの一部)」(PDF) 。p. 3。2012 年 1 月 6 日にオリジナル(PDF)からアーカイブ。2011 年 7 月 10 日に取得。
• Black, Paul E. (2004-08-16)。Pieterse, Vreda、Black, Paul E. (編)。「リンク リスト」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所。2004-12-14に取得。
• アントナコス、ジェームズ L.、マンスフィールド、ケネス C. Jr. (1999)。C/C++ を使用した実用的なデータ構造。Prentice-Hall。pp. 165–190。ISBN 0-13-280843-9。
• コリンズ、ウィリアム J. (2005) [2002]。データ構造と Java コレクション フレームワーク。ニューヨーク: McGraw Hill。pp. 239–303。ISBN 0-07-282379-8。
• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2003)。アルゴリズムの概要。 MITプレス。 205–213、501–505ページ。ISBN 0-262-03293-7。
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「10.2: リンクリスト」。アルゴリズム入門(第 2 版)。MIT プレス。204 ～ 209 ページ。ISBN 0-262-03293-7。
• Green, Bert F. Jr. (1961)。「シンボル操作のためのコンピュータ言語」。IRE Transactions on Human Factors in Electronics (2): 3–8。doi : 10.1109 /THFE2.1961.4503292。
• マッカーシー、ジョン( 1960 )。「記号式の再帰関数と機械による計算、パート I」。Communications of the ACM。3 ( 4): 184。doi : 10.1145/367177.367199。S2CID  1489409 。
• Knuth, Donald (1997)。「2.2.3-2.2.5」。基本アルゴリズム(第 3 版)。Addison-Wesley。pp. 254–298。ISBN 0-201-89683-4。
• Newell, Allen ; Shaw, FC (1957)。「論理理論マシンのプログラミング」。Western Joint Computer Conference Proceedings : 230–240。
• Parlante, Nick (2001) 「リンクリストの基礎」(PDF)スタンフォード大学2009 年 9 月 21 日閲覧。
• セジウィック、ロバート(1998)。Cアルゴリズム。アディソン・ウェスリー。pp. 90–109。ISBN 0-201-31452-5。
• Shaffer, Clifford A. (1998)。データ構造とアルゴリズム分析の実践的入門。ニュージャージー州: Prentice Hall。pp. 77–102。ISBN 0-13-660911-2。
• Wilkes, Maurice Vincent (1964)。「単純なリスト処理言語用の自己コンパイルコンパイラの実験」。自動プログラミングの年次レビュー。4 (1)。Pergamon Press: 1. doi : 10.1016/0066-4138(64)90013-8。
• Wilkes, Maurice Vincent (1964)。「リストとその有用性」。ACM全国会議議事録、フィラデルフィア 1964 (P–64)。ACM: F1–1。
• Shanmugasundaram, Kulesh (2005-04-04). 「Linux カーネルのリンク リストの説明」。2009-09-25 にオリジナルからアーカイブ。2009-09-21に取得。

ウィキメディア・コモンズには、リンクリストに関連するメディアがあります。

• アルゴリズムとデータ構造の辞書からの説明
• リンクリスト入門、スタンフォード大学コンピュータサイエンス図書館
• リンクリストの問題、スタンフォード大学コンピュータサイエンス図書館
• オープン データ構造 - 第 3 章 - リンク リスト、Pat Morin
• 複数のリンクリストに同時に存在するノードを持つというアイデアの特許（この技術は特許が付与される前から何十年も広く使用されていたことに注意してください）
• C言語での単方向リンクリストの実装
• C++ での単方向リンクリストの実装
• C での二重リンクリストの実装
• C++ での二重リンクリストの実装