リンクリスト

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
ノードに整数値と次のノードへのリンクの2つのフィールドが含まれるリンクリスト。最後のノードは、リストの終わりを示すために使用されるターミネータにリンクされています。

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

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

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

一方、単純なリンクリスト自体では、データへのランダムアクセスや効率的なインデックス作成が許可されないため、リストの最後のノードの取得、特定のデータを含むノードの検索、新しいノードを挿入する場所を特定する—ほとんどまたはすべてのリスト要素を反復処理する必要がある場合があります。リンクリストを使用することの長所と短所を以下に示します。

歴史

リンクされたリストはで、1955年から1956年に開発されたアレン・ニューウェルクリフ・ショーハーバート・サイモンRAND社プライマリとしてデータ構造そのための情報処理言語。 IPLは、Logic Theory Machine、General Problem Solver、コンピューターチェスプログラムなど、いくつかの初期の人工知能プログラムを開発するために著者によって使用されました。彼らの研究に関する報告は、1956年の情報理論に関するIREトランザクション、および1957年と1958年の西部合同コンピュータ会議の議事録および情報処理(最初の議事録)を含む1957年から1959年までのいくつかの会議議事録に掲載されました。1959年のユネスコ情報処理に関する国際会議)。連続するリストノードを指す矢印の付いたリストノードを表すブロックで構成される現在の古典的な図は、Proc。のNewellとShawによる「Programmingthe LogicTheoryMachine」に掲載されています。 WJCC、1957年2月。ニューウェルとサイモンは、「人工知能、人間の認知の心理学、およびリスト処理に基本的な貢献をした」ことで、1975年にACMチューリング賞を受賞しました。自然言語処理のため機械翻訳の問題によりマサチューセッツ工科大学のVictorYngveが(MIT)言語学の分野でのコンピューター研究のための彼のCOMITプログラミング言語のデータ構造としてリンクリストを使用する「機械的翻訳のためのプログラミング言語」と題されたこの言語に関するレポートは、1958年にMechanicalTranslationに掲載されました。[引用が必要]

リンクリストのもう1つの初期の登場は、1953年1月にチェーンハッシュテーブルでのリンクリストの使用を提案するIBMの内部覚書を書いたHans PeterLuhnによるものでした[1]

リストプロセッサの略であるLISPはジョン・マッカーシーがMIT在籍中に1958年に作成し、1960年に、Communications of theACMの論文「Communicationsofthe Symbolic Expressions and their Computation by Machine、Part。私"。 LISPの主要なデータ構造の1つは、リンクリストです。

1960年代初頭までに、これらの構造を主要なデータ表現として使用するリンクリストと言語の両方の有用性が十分に確立されました。バート・グリーンMITリンカーン研究所は、リンクリストのアプローチの利点をまとめた1961年3月における電子における人間の要因に関するIRE取引で「シンボル操作のためのコンピュータ言語」と題したレビュー記事を掲載しました。 BobrowとRaphaelによる後の総説「リスト処理コンピュータ言語の比較」は、1964年4月のCommunications of theACMに掲載されました。

テクニカルシステムコンサルタント(元々はインディアナ州ウェストラファイエット、後にノースカロライナ州チャペルヒル)によって開発されたいくつかのオペレーティングシステムは、ファイル構造として単一リンクリストを使用していました。ファイルの最初のセクターを指すディレクトリエントリと、ファイルの後続の部分は、ポインタをトラバースすることによって見つけられました。この手法を使用するシステムには、Flex(Motorola 6800 CPU用)、mini-Flex(同じCPU用)、およびFlex9(Motorola 6809 CPU用)が含まれていました。カリフォルニアのSmokeSignal BroadcastingのためにTSCによって開発され、販売されたバリアントは、同じ方法で二重にリンクされたリストを使用しました。

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

基本的な概念と命名法

リンクリストの各レコードは、「要素」または「ノードと呼ばれることがよくあります

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

リストの「先頭」はその最初のノードです。リストの「テール」は、リストの先頭の後の残りの部分、またはリストの最後のノードのいずれかを参照する場合があります。Lispといくつかの派生言語、次のノードは、「と呼ばれることができるCDR(発音」可能性-ERヘッドノードのペイロードが「車」と呼ばれてもよいが、リストの)。

単一リンクリスト

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

ノードに整数値と次のノードへのリンクの2つのフィールドが含まれる単一リンクリスト

次のコードは、データ「値」を持つ新しいノードを単一リンクリストの最後に追加する方法を示しています。

node addNode node head int value {     
    ノード温度p ; // 2つのノードTEMPおよびp宣言TEMP = createNodeを(); // createNodeがdata = 0で、次にNULLを指す新しいノードを作成すると仮定します。temp- > data = value ; //要素の値をノードのデータ部分に追加しますif head == NULL {   
       
       
        
        ヘッド=温度; //リンクリストが空の場合}       
    
    else { 
        p =; //ヘッドをpに割り当てますwhile p- > next != NULL {   
            
            p = p- >; // pが最後のノードになるまでリストをトラバースします。最後のノードは常にNULLを指します。}   
        
        p- > next = temp ; //前の最後のノードが作成された新しいノードを指すようにします。}   
    
    リターンヘッド; 
}

二重リンクリスト

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

ノードに3つのフィールドが含まれる二重リンクリスト:整数値、次のノードへの前方へのリンク、および前のノードへの後方へのリンク

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

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

乗算リンクリスト

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

循環リンクリスト

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

循環リンクリスト

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

センチネルリンパ節

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

空のリスト

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

ハッシュリンク

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

リストハンドル

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

選択肢を組み合わせる

上記の選択肢は、ほぼすべての方法で任意に組み合わせることができるため、センチネルのない循環二重リンクリスト、センチネルのある循環単一リンクリストなどがあります。

トレードオフ

コンピュータプログラミングと設計のほとんどの選択肢と同様に、すべての状況に適した方法はありません。リンクリストのデータ構造は、ある場合にはうまく機能するかもしれませんが、別の場合には問題を引き起こします。これは、リンクリスト構造に関連するいくつかの一般的なトレードオフのリストです。

リンクリストと動的配列

リストデータ構造の比較
ピーク …で変更(挿入または削除) 余剰スペース、
平均
始まり 終わり 真ん中
リンクリスト Θ(n Θ(1) Θ(1)、既知の終了要素。
Θ(n)、未知の末端要素
ピーク時間+
Θ(1)[4] [5]
Θ(n
配列 Θ(1) 該当なし 該当なし 該当なし 0
動的配列 Θ(1) Θ(n Θ(1)償却 Θ(n Θ(n[6]
バランスツリー Θ(logn) Θ(logn) Θ(log n Θ(log n Θ(n
ランダムアクセスリスト Θ(logn)[7] Θ(1) 該当なし[7] 該当なし[7] Θ(n
ハッシュ化された配列ツリー Θ(1) Θ(n Θ(1)償却 Θ(n Θ(√ N

ダイナミックアレイは、隣接メモリ内のすべての要素を割り当てるデータ構造であり、要素の現在の数のカウントを維持します。動的配列用に予約されたスペースを超えると、動的配列が再割り当てされ、(場合によっては)コピーされます。これはコストのかかる操作です。

リンクリストには、動的配列に比べていくつかの利点があります。リストの特定のポイントでの要素の挿入または削除は、ノードへのポインター(削除されるノードの前、または挿入ポイントの前)に既にインデックスが付けられていると仮定すると、一定時間の操作です(それ以外の場合はこれがありません)。参照はO(n))ですが、動的配列にランダムな位置に挿入するには、平均して要素の半分を移動する必要があり、最悪の場合はすべての要素を移動する必要があります。スロットを「空」としてマークすることにより、一定時間で配列から要素を「削除」できますが、これにより断片化発生し、反復のパフォーマンスが妨げられます。

さらに、任意の数の要素をリンクリストに挿入できますが、使用可能なメモリの合計によってのみ制限されます。一方、動的配列は最終的にその基礎となる配列データ構造を埋め、再割り当てする必要があります。これはコストのかかる操作であり、メモリが断片化されている場合でも不可能な場合がありますが、再割り当てのコストは挿入全体で平均化できます。再割り当てによる挿入は、引き続き償却されますO(1)。これは、配列の最後に要素を追加するのに役立ちますが、中央の位置に挿入(または削除)すると、データが連続性を維持するために移動するため、依然として法外なコストがかかります。多くの要素が削除された配列も、スペースの浪費を避けるためにサイズを変更する必要がある場合があります。

一方、動的配列(および固定サイズの配列データ構造)では、一定時間のランダムアクセスが許可されますが、リンクリストでは要素への順次アクセスのみが許可されます。実際、単一リンクリストは一方向にのみ簡単に移動できます。これにより、リンクリストは、ヒープソートなど、インデックスで要素をすばやく検索するのに役立つアプリケーションには適していません。配列と動的配列へのシーケンシャルアクセスは、参照の局所性が最適であり、データキャッシュをうまく利用するため、多くのマシンのリンクリストよりも高速です

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

一部のハイブリッドソリューションは、2つの表現の利点を組み合わせようとします。 Unrolled Linked Listは、各リストノードにいくつかの要素を格納し、参照のメモリオーバーヘッドを減らしながら、キャッシュパフォーマンスを向上させます。CDRコーディングは、参照を参照レコードの終わりから拡張される実際のデータに置き換えることにより、これらの両方も実行します。

動的配列とリンクリストを使用することの長所と短所を強調する良い例は、ヨセフス問題を解決するプログラムを実装することです。ヨセフス問題は、人々のグループを輪になって立たせることによって機能する選挙方法です。あらかじめ決められた人から始めて、円の周りをn回数えることができます一度n到達した人は、サークルから削除し、メンバーにサークルを閉じてもらう必要があります。このプロセスは、1人だけが残るまで繰り返されます。その人が選挙に勝ちます。これは、リンクリストと動的配列の長所と短所を示しています。これは、循環リンクリストでユーザーが接続ノードとして表示されている場合、リンクリストがノードを簡単に削除できることを示しているためです(必要なのは異なるノードへのリンクを再配置します)。ただし、リンクリストは削除する次の人を見つけるのに苦労し、その人が見つかるまでリストを検索する必要があります。一方、動的配列は、すべての要素をリストの1つ上に個別にシフトしないと、1つのノードを削除できないため、ノード(または要素)の削除が不十分になります。ただし、見つけるのは非常に簡単です配列内の位置によって直接参照することにより、サークル内のn番目の人。

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

バランスのとれたツリーは、ランダムアクセスのためにO(ログn)の代わりに、O(N)の時間を割いて、はるかに効率的な索引付けを可能にしながら、リンクされたリストと同様に、メモリ・アクセス・パターンとスペースのオーバーヘッドを有します。ただし、バランスを維持するためのツリー操作のオーバーヘッドのため、挿入および削除操作はよりコストがかかります。樹木が自動的にバランスの取れた状態を維持するためのスキームが存在します:AVL木または黒木

単一リンクの線形リストと他のリスト

二重リンクリストと循環リストには、単一リンクの線形リストよりも利点がありますが、線形リストには、状況によっては好ましいといういくつかの利点があります。

単一リンクの線形リストは、同じタイプのより小さなオブジェクトへのポインターが含まれているため再帰的なデータ構造です。そのため、単一にリンクされた線形リストに対する多くの操作(2つのリストのマージ、要素の逆順の列挙など)には、反復コマンドを使用するどのソリューションよりもはるかに単純な、非常に単純な再帰アルゴリズムが含まれることがよくあります。これらの再帰的ソリューションは、二重リンクリストと循環リンクリストに適合させることができますが、手順には通常、追加の引数とより複雑な基本ケースが必要です。

線形の単一リンクリストでは、テール共有、つまりサブリストの共通の最終部分を2つの異なるリストの終端部分として使用することもできます。特に、リストの先頭に新しいノードが追加された場合、以前のリストは新しいノードの末尾として引き続き使用できます。これは、永続データ構造の簡単な例です。繰り返しますが、これは他のバリアントには当てはまりません。ノードが2つの異なる循環リストまたは二重リンクリストに属することはありません。

特に、エンドセンチネルノードは、単一にリンクされた非循環リスト間で共有できます。そのようなすべてのリストに同じエンドセンチネルノードを使用できますLispで表される特別なノードへのリンクと、例えば、すべての適切なリストが終了nil又は()CARおよびCDRリンク自体を指します。したがって、Lispプロシージャは任意のリストのCARまたはCDR安全に取得できます。

ファンシーバリアントの利点は、効率ではなく、アルゴリズムの複雑さに制限されることがよくあります。特に循環リストは、通常、追加コストなしで、最初と最後のノードを指す2つの変数とともに線形リストによってエミュレートできます。

二重リンクと単一リンク

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

循環リンクと線形リンク

循環リンクリストは、自然に円形の配列を表すための自然なオプションです。たとえば、ポリゴンのコーナーFIFO(「先入れ先出し」)の順序で使用および解放されるバッファのプール、または一連のラウンドロビン順タイムシェアリングする必要があるプロセスこれらのアプリケーションでは、任意のノードへのポインタがリスト全体へのハンドルとして機能します。

循環リストを使用すると、最後のノードへのポインターを使用すると、1つのリンクをたどることで、最初のノードにも簡単にアクセスできます。したがって、リストの両端へのアクセスを必要とするアプリケーション(キューの実装など)では、循環構造により、2つではなく1つのポインターで構造を処理できます。

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

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

センチネルリンパ節の使用

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

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

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

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

リンクリスト操作

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

線形リンクリスト

単一リンクリスト

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

レコード ノード
{{
    データ; //ノードに格納されたデータ
    ノードは、//参照[2]次のノードへ、最後のノードの場合はnull
}
レコード リスト
{{
    Node firstNode //リストの最初のノードを指します。空のリストの場合はnull
}

単独リンクリストのトラバーサルは、最初のノードから始まり、それぞれ以下の、シンプルで次の私たちが最後に来るまでのリンクを:

node:= list.firstNode
 while node not null
     (node.dataで何かをする)
    node:= node.next

次のコードは、単一リンクリストの既存のノードの後に​​ノードを挿入します。この図は、それがどのように機能するかを示しています。既存のノードの前にノードを挿入することは直接行うことはできません。代わりに、前のノードを追跡し、その後にノードを挿入する必要があります。

単一リンクリストへのノードの挿入の図
function insertAfter(Node node、Node newNode)//ノードの後に​​newNodeを挿入します
    newNode.next:= node.next
    node.next:= newNode

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

function insertBeginning(List list、Node newNode)//現在の最初のノードの前にノードを挿入します
    newNode.next:= list.firstNode
    list.firstNode:= newNode

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

単一リンクリストからノードを削除する図
function removeAfter(Node node)//これを過ぎたノードを削除します
    obsoleteNode:= node.next
    node.next:= node.next.next
    obsoleteNodeを破棄します
function removeBeginning(リストリスト)//最初のノードを削除します
    obsoleteNode:= list.firstNode
    list.firstNode:= list.firstNode.next//削除されたノードを過ぎたポイント
    obsoleteNodeを破棄します

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

逆方向に繰り返すことができないため、効率的な操作insertBeforeremoveBefore操作はできません。特定のノードの前にリストに挿入するには、リストをトラバースする必要があります。これは、最悪の場合、実行時間がO(n)になります。

テールを見つけるために最初のリスト全体をトラバースしてから、これに2番目のリストを追加する必要があるため、テールへの参照がリスト構造の一部として保持されない限り、1つのリンクリストを別のリストに追加することは非効率的です。したがって、2つの線形リンクリストがそれぞれ長さである場合、リストの追加には漸近的な時間計算量がありますLispファミリーの言語では、リストの追加はappendプロシージャによって提供されます。

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

循環リンクリスト

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

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

循環リンクリストの両方のタイプは、任意のノードから始まる完全なリストをトラバースする機能の恩恵を受けます。これによりfirstNodelastNodeの保存を回避できることがよくありますが、リストが空の場合は、リスト内のノードを指すlastNode変数や、空の場合nullなど、空のリストの特別な表現が必要です。ここではそのようなlastNodeを使用します。この表現により、空でないリストを持つノードの追加と削除が大幅に簡素化されますが、空のリストは特殊なケースです。

アルゴリズム

someNodeが空でない循環単一リンクリスト内のノードであると仮定すると、このコードはsomeNodeで始まるそのリストを繰り返し処理します

someNode≠ nullの場合、関数iterate(someNode)
    
        node:= someNode
    NS
        node.valueで何かをする
        node:= node.next
    一方、ノード≠someNode

「テストすることを通知しながらノード≠someNode」はループの最後でなければなりません。テストがループの先頭に移動された場合、リストにノードが1つしかない場合は常に、プロシージャは失敗します。

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

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

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

insertAfter(L、newNode)
L:= newNode

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

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

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

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変数を
    更新します

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

関数remove(ノードノード)
    ノード≠ nullで、リストのサイズが1より大きい場合
        removeData:= node.data
        node.data:= node.next.data
        node.next = node.next.next
        リターンremovedData

ノードの配列を使用したリンクリスト

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

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

レコード エントリ{
    整数次; //配列
    整数の次のエントリのインデックスprev; //前のエントリ(二重リンクされている場合)
    文字列名;
    本当のバランス;
}

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

整数listHead
エントリレコード[1000]

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

索引 前へ 名前 バランス
0 1 4 ジョーンズ、ジョン 123.45
1 -1 0 スミス、ジョセフ 234.56
2(listHead) 4 -1 アダムス、アダム 0.00
3 無視、イグナティウス 999.99
4 0 2 別の、アニタ 876.54
5
6
7

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

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

I:= listHead
ながら私≥0リストを//ループは
    I、レコードを印刷する[I] .nameの、レコード[i]は.balance //プリントエントリ
    i:= Records [i] .next

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

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

ただし、このアプローチには1つの主な欠点があります。それは、ノードのプライベートメモリスペースを作成および管理することです。これにより、次の問題が発生します。

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

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

言語サポート

LispSchemeなどの多くのプログラミング言語には、単一リンクリストが組み込まれています。多くの関数型言語では、これらのリストは、それぞれが短所または短所セルと呼ばれるノードから構成されます。 :短所は、二つのフィールドを有している、そのノードのデータへの参照、およびCDR、次のノードへの参照。 consセルは他のデータ構造を構築するために使用できますが、これが主な目的です。

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

内部および外部ストレージ

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

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

一般に、データ構造のセットをリンクリストに含める必要がある場合は、外部ストレージが最善のアプローチです。データ構造のセットを1つのリンクリストにのみ含める必要がある場合は、外部ストレージを使用する一般的なリンクリストパッケージが利用可能でない限り、内部ストレージの方がわずかに優れています。同様に、同じデータ構造に格納できる異なるデータセットを単一のリンクリストに含める場合は、内部ストレージで問題ありません。

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

内部ストレージと外部ストレージの例

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

レコード メンバー{ //
    次の家族のメンバー;
    文字列firstName;
    整数年齢;
}
レコード ファミリー{ //ファミリー自体
    ファミリーネクスト;
    文字列lastName;
    文字列アドレス;
    メンバーメンバー//このファミリーのメンバーのリストの先頭
}

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

aFamily:=ファミリ//ファミリリストの先頭から開始し
 aFamily≠ null  //ファミリのリストループします
    家族に関する情報を印刷する
    aMember:= aFamily.members //このファミリのメンバーのリストの先頭を取得し
     aMember≠ null  //メンバーのリストをループします
        メンバーに関する情報を印刷する
        aMember:= aMember.next
    aFamily:= aFamily.next

外部ストレージを使用して、次の構造を作成します。

レコード ノード{ //汎用リンク構造
    ノードnext;
    ポインタデータ//ノードのデータの汎用ポインタ
}
レコード メンバー{ //ファミリーメンバーの構造
    文字列firstName;
    整数年齢
}
レコード ファミリ{ //ファミリ
    文字列lastNameの構造;
    文字列アドレス;
    ノードメンバー//このファミリーのメンバーのリストの先頭
}

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

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

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

メンバーが属することができるファミリの数がコンパイル時にわかっている限り、内部ストレージは正常に機能します。ただし、メンバーを任意の数のファミリに含める必要があり、特定の数が実行時にのみ認識される場合は、外部ストレージが必要になります。

検索の高速化

リンクリスト内の特定の要素を見つけるには、たとえそれがソートされていても、通常はO(n)時間かかります(線形検索)。これは、他のデータ構造に対するリンクリストの主な欠点の1つです。上記のバリエーションに加えて、検索時間を改善する2つの簡単な方法を以下に示します。

順序付けされていないリストでは、平均検索時間を短縮するための1つの単純なヒューリスティックは、前に移動するヒューリスティックです。これは、要素が見つかると、リストの先頭に移動するだけです。このスキームは、単純なキャッシュを作成するのに便利であり、最近使用したアイテムをすばやく見つけることができます。

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

ランダムアクセスリスト

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

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

ランダムアクセスリストの単純な拡張はmin-listです。これは、リスト全体の最小要素を一定時間で生成する追加の操作を提供します([明確化が必要]突然変異の複雑さなしで)。[9]

関連するデータ構造

スタックキューどちらもリンクリストを使用して実装されることが多く、サポートされる操作のタイプを制限するだけです。

スキップリストは、迅速要素の多数を飛び越え、次いで次の層へ下降用ポインタの層で補強リンクされたリストです。このプロセスは、実際のリストである最下層まで続きます。

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

展開リンクされたリストは、各ノードは、データ値の配列を含有しているリンクされたリストです。これにより、メモリ内で隣接するリスト要素が増えるため、キャッシュパフォーマンスが向上し、リストの各要素に格納する必要のあるメタデータが少なくなるため、メモリのオーバーヘッドが削減されます。

ハッシュテーブルは、ハッシュテーブル内の同じ位置にそのハッシュアイテムのチェーンを保存するためにリンクされたリストを使用することができます。

ヒープ共有リンクリストの順序付けのプロパティのいくつかが、ほとんど常にアレイを使用して実装されています。ノードからノードへの参照の代わりに、次および前のデータインデックスは、現在のデータのインデックスを使用して計算されます。

自己組織化リストは、リストの先頭に頻繁にアクセスノードを保持することによってデータ検索のための検索時間を減少させるいくつかのヒューリスティックに基づいてノードを並び替えます。

注意事項

  1. ^ 動的配列に必要な制御データの量は、通常、次の形式です。、 どこ は配列ごとの定数であり、 は次元ごとの定数であり、 は次元数です。 通常は10バイトのオーダーです。

参考文献

  1. ^ クヌース、ドナルド(1998)。コンピュータプログラミングの芸術3:並べ替えと検索(第2版)。アディソン-ウェスリー。NS。547. ISBN  978-0-201-89685-5
  2. ^ B 「アーカイブコピー」アーカイブされたオリジナルの2015年9月23日に2015年7月31日取得CS1 maint:タイトルとしてアーカイブされたコピー(リンク
  3. ^ 「アーカイブされたコピー」(PDF)2016-10-01にオリジナル(PDF)からアーカイブされまし2021-08-31を取得 CS1 maint:タイトルとしてアーカイブされたコピー(リンク
  4. ^ 1日目の基調講演-ビャーネ・ストロヴストルップ:C ++ 11スタイルGoingNative 2012channel9.msdn.com分45から44または箔
  5. ^ ナンバークランチ:あなたは、これまでに、二度とあなたのコードにリンクされたリストを使用しないでくださいなぜkjellkod.wordpress.com
  6. ^ Brodnik、Andrej; カールソン、スヴァンテ; セッジウィック、ロバート; マンロー、JI; Demaine、ED(1999)、最適な時間と空間でのサイズ変更可能なアレイ(テクニカルレポートCS-99-09)(PDF)、ウォータールー大学コンピュータサイエンス学部
  7. ^ a b c クリス・オカサキ(1995)。「純粋関数型ランダムアクセスリスト」。機能プログラミング言語とコンピュータアーキテクチャに関する第7回国際会議の議事録:86–95。土井10.1145 /224164.224187
  8. ^ フォード、ウィリアム; Topp、William(2002)。STLを使用したC ++のデータ構造(第2版)。プレンティスホール。pp。466–467。ISBN 0-13-085850-1
  9. ^ a b c d e Okasaki、Chris(1995)。純粋関数型ランダムアクセスリスト(PS)関数型プログラミング言語とコンピュータアーキテクチャACMプレス。pp。86–95 2015年5月7日取得

さらに読む

外部リンク