Linked List - tanakakenji/Rinko GitHub Wiki

イントロダクション

配列（array）と同様に、リンクドリスト（linked list）も順序付きデータを表すために使われます。ただし、配列とは異なり、メモリ上で要素が連続的に配置されているわけではありません。リンクドリストでは、各要素（ノード）が次の要素のアドレスを持つことで要素同士を連結しています。つまり、複数のノードを並べてシーケンスを表すデータ構造です。

最も基本的な形では、各ノードは以下を持ちます:

データ
次のノードを指す参照（リンク）

長所 (Advantages)

ノードの挿入と削除：特定のノード位置さえわかっていれば、挿入と削除は O(1) で実行できます。一方、配列では要素を挿入・削除する際に、後続の要素をシフトする必要があるため、コストが大きくなります。

短所 (Disadvantages)

アクセス時間：ノードを直接アクセスする機能がないため、先頭から順にたどる必要があり、要素アクセスは O(n) かかります。配列の場合は arr[4] のように即時アクセスが可能ですが、リンクドリストではそういったアクセスが不可能です。

学習リソース (Learning resources)

読み物

動画

リンクドリストの種類 (Types of linked lists)

単方向リスト (Singly linked list)

各ノードが次のノードへの参照を持ち、最後のノードは null（または None）を指します。

双方向リスト (Doubly linked list)

各ノードが次のノード（next）と前のノード（prev）の両方を指す参照を持ちます。最初のノードの prev と最後のノードの next は null となります。

循環リスト (Circular linked list)

単方向リストの場合、最後のノードが最初のノードを指す形を取ります。双方向の場合はさらに、最初のノードの prev が最後のノードを指すなど、リストをぐるっと循環させる形です。

実装 (Implementations)

主要言語の中ではJavaのみが標準でリンクドリストの実装（LinkedList）を提供しています。ですが、どの言語でもリンクドリストの実装は比較的簡単に書くことができます。

言語	API
C++	`std::list`
Java	`java.util.LinkedList`
Python	N/A
JavaScript	N/A

時間計算量 (Time complexity)

操作	Big-O	備考
アクセス	O(n)
検索	O(n)
挿入	O(1)	挿入位置まで移動（走査）が終わっていることが前提
削除	O(1)	削除するノードまで移動（走査）が終わっていることが前提

よく使われるルーチン (Common routines)

リンクドリストの問題では、以下のルーチンを使うケースが多いので、実装方法に慣れておきましょう。

リンクドリストのノード数を数える
リンクドリストをインプレース（その場）で反転させる
2つのポインタ（高速ポインタ／低速ポインタ）を使ってリストの中央ノードを見つける
2つのリンクドリストをマージする

コーナーケース (Corner cases)

空のリンクドリスト（head が null）
ノードが1つだけの場合
ノードが2つだけの場合
リンクドリストにサイクルがある場合
- 面接の前に、サイクルが発生し得るかを確認しましょう。通常はサイクルを考慮しなくてよいとされることが多いですが、場合によっては処理が必要になるかもしれません。

テクニック (Techniques)

番兵（ダミー）ノード (Sentinel/dummy nodes)

先頭や末尾に番兵（ダミー）ノードを追加することで、先頭や末尾での操作の特殊ケースを軽減できます。番兵ノードを使うと、リストの先頭や末尾の処理でヌル参照に対する条件分岐をする必要がなくなり、実装がシンプルになります。操作後にダミーを取り除くのを忘れないようにしましょう。

2つのポインタ (Two pointers)

リンクドリストでも2つのポインタを使う手法はよく用いられます。有名な例として：

後ろからk番目のノードを取得
- 1つのポインタを先にkステップ進めてから、もう一方のポインタと同時に進めます。先のポインタが末尾に着いたとき、もう一方のポインタは後ろからk番目にいます。
サイクルの検出
- 2つのポインタを使い、一方をもう一方の2倍の速さで進めます。もし2つのポインタが同じノードで交わったら、リストにサイクルがあることを示します（Floydのサイクル検出アルゴリズム）。
リストの中央ノードの取得
- 2つのポインタを使い、一方をもう一方の2倍の速さで進めます。高速ポインタが末尾に達したとき、低速ポインタは中央ノードにいます。

スペースを使う (Using space)

多くのリンクドリスト問題では、新しいリンクドリストを作って解く方法でも実現可能です。しかし、追加のスペースを使うと問題の難易度が低下するため、インタビュアーからは「既存リストをインプレースで変更するように」と要求されることが多いです。要素の並び替えなど、リンクドリストをその場で変更するような実装方法（たとえば「Reverse a Linked List」の考え方）を参考にしましょう。

洗練された変更操作 (Elegant modification operations)

前述のとおり、リンクドリストは要素が連続したメモリに格納されているわけではないので、配列とは異なる形で効率的に要素の変更や再構成が行えます。具体例は以下のとおり：

リストの切り詰め（トランケート）
- 最後の要素の next を null に設定すれば、リストを任意の場所で切り取ることが可能です。
ノードの値のスワップ
- 配列同様、2つのノードの値を交換するだけなら単純にデータだけを入れ替えればよく、ポインタそのものを入れ替える必要はありません。
2つのリストの結合
- 1つ目のリストの末尾を2つ目のリストの先頭につなげるだけで実現できます。

Linked List（連結リスト）は、CPUやOSの内部で、動的なメモリ管理、プロセスの管理、データ構造の取り扱いに使われています [1, 2, 4]。特にサイズが予測できないデータを柔軟に管理できるのが利点です。

オペレーティングシステム（OS）

メモリ管理: 連結リストは空きメモリのブロックを管理するために使われます[2, 4, 15]。OSはフリーリストという連結リストを使って、利用可能なメモリを追跡します。プロセスがメモリを必要とするとき、システムはフリーリストからブロックを割り当てます。プロセスが終了すると、メモリはフリーリストに戻されます。
プロセススケジューリング: OSは、スケジューラでプロセスを管理するために連結リストを使用します [4, 5]。各プロセスはリストのノードであり、スケジューラは連結リストを操作して、プロセスを異なるキュー（準備完了、待機中、実行中）間で移動させることができます。たとえば、ラウンドロビン・スケジューリングでは、環状連結リストがプロセスを順番に処理するために使用されます[4, 7]。
デバイスドライバ管理: デバイスドライバは連結リストを使って管理できます。各ドライバがノードとなり、OSがハードウェアデバイスを動的にロード、管理、および通信できるようになります。

CPU

キャッシュミス: 配列とは異なり、連結リストの要素はメモリ内のどこにでも配置できます。連結リストを反復処理すると、キャッシュミスが発生し、パフォーマンスのオーバーヘッドにつながる可能性があります[3, 6]。これは、配列がメモリ内に連続して要素を格納し、CPUがデータを予測してプリフェッチできるためです[3, 6]。
割り込み処理: 割り込み駆動型システムでは、割り込みハンドラを連結リストでリンクできます。割り込みが発生すると、システムはリストをトラバースして、適切なハンドラを見つけて実行します。

その他の応用

DMAコントローラ: 連結リストは、DMAコントローラを介したスキャッタ/ギャザリングをサポートします。
タスクスケジューリング: リアルタイムオペレーティングシステムでは、連結リストがタスクキューを保持します [1, 4]。
バッファ管理: 連結リストは、UARTまたはSPI通信バッファを効率的に管理します。
動的なセンサーデータストレージ: センサーの読み取り値を、事前に割り当てられた配列でメモリを無駄にすることなく、動的に保存します。
ハッシュテーブル: 連結リストは、ハッシュテーブルで衝突を処理するために使用されます。2つのデータが同じ場所になった場合、連結リストは両方のアイテムを順番に保存します。
スタックとキュー: 連結リストは、アルゴリズムとプログラミングの基本的なデータ構造であるスタックとキューを実装します [2, 14]。
グラフ表現: グラフを隣接リストとして表現します。各ノードは、隣接するノードのリストを指します。
元に戻す機能: テキストエディタなどのアプリケーションでは、連結リストは「元に戻す」機能のためにアクションの履歴を保持します。
プレイリスト: 連結リストはプレイリストを表すことができ、次の項目または前の項目への簡単なナビゲーションを可能にします[5, 8]。
Webブラウザのナビゲーション: Webブラウザは、順方向および逆方向のナビゲーションに連結リストを使用します。アクセスした各ページはノードであり、ユーザーはリスト内を移動できます。

重要問題 (Essential questions)

このトピック（リンクドリスト）を学習する際に、まず最初に練習しておくべき問題はこちらです。

Reverse a Linked List
Detect Cycle in a Linked List