単方向リスト

2025年10月20日

単方向リスト

英語表記: Singly Linked List

概要

単方向リスト（Singly Linked List）は、データ構造の主要な分類である「リスト」の一種であり、「リンクリスト」に分類される基本的なデータ構造です。これは、要素が物理的に連続したメモリ領域に配置される「配列」とは異なり、各要素（ノード）が次の要素への参照（ポインタ）のみを保持することで、論理的な順序を形成します。

この構造の最大の特徴は、常に「次」の要素しか追跡できない点にあります。これにより、リストの先頭から末尾に向かって一方向にのみ辿っていくことが可能となり、動的なデータの追加や削除を効率的に行えるよう設計されています。

詳細解説

リンクリストの中での位置づけ

私たちが今学んでいるデータ構造の階層（データ構造 → 配列とリスト → リンクリスト）において、単方向リストはリンクリストの最もシンプルな形態です。配列が固定サイズで要素の追加・削除に手間がかかる（要素をずらす必要がある）という弱点を克服するために、リンクリストは誕生しました。単方向リストは、そのリンクリストの中でも「シンプルさ」と「メモリ効率」を追求した構造と言えます。

構成要素と動作原理

単方向リストは、主に以下の二つの要素で構成されています。

ノード (Node): リストにおける個々の要素のことです。
ヘッド (Head): リストの最初のノードを指し示す特別なポインタです。ここからリストの探索が始まります。

各ノードは、必ず二つの部分を持っています。

データ部 (Data): そのノードが実際に保持したい情報（数値、文字列など）を格納します。
ポインタ部 (Pointer / Next Reference): 次のノードがメモリ上のどこに位置しているかを示すアドレス情報（参照）を格納します。

リストの動作は非常に直感的です。ヘッドからスタートし、最初のノードのポインタに従って次のノードへ移動し、それを繰り返してリストを辿ります。リストの末尾のノードは、ポインタ部に「何も指さない」ことを示す特別な値（通常はNULLやNil）を持ちます。

挿入と削除の仕組み

単方向リストの最大のメリットは、要素の挿入（追加）と削除が非常に効率的であることです。

挿入: 新しいノードをリストの中間に挿入したい場合、挿入したい位置の「前のノード」のポインタを、新しいノードのアドレスに書き換え、新しいノードのポインタを元々次にあったノードのアドレスに設定し直すだけで完了します。配列のように大量の要素を物理的に移動させる必要はありません。
削除: あるノードを削除したい場合、そのノードの「前のノード」のポインタを、削除対象のノードの「次のノード」に直接つなぎ直す（バイパスする）だけで済みます。

ただし、単方向リストは「次」しか知らないため、あるノードXから「前」のノードに戻ることはできません。このため、特定のノードを削除するためには、必ずリストの先頭（ヘッド）から辿って、削除対象の「直前のノード」を見つけ出す必要があります。これは、後述の資格試験対策でも重要なポイントになります。

なぜ単方向リストが使われるのか

この構造が選ばれる理由は、主に「メモリの動的利用」と「非連続性」にあります。プログラムが実行中に必要なメモリサイズが変動する場合、単方向リストは必要な分だけノードを生成し、メモリの空いている場所に配置できるため、非常に柔軟です。また、メモリが断片化していても、ポインタで論理的な連続性を保てるため、大きな連続した領域を確保できない環境でも効率的に機能します。

具体例・活用シーン

単方向リストは、そのシンプルさから多くの基礎的なアプリケーションやシステム内部で利用されています。

OSのタスク管理: オペレーティングシステム（OS）は、現在実行待ちや処理待ちのタスクをリストとして管理しています。このタスクキューの実装に単方向リストが用いられることがあります。新しいタスクが来たらリストの末尾に追加され、処理が終わったタスクは先頭から取り除かれます。
Webブラウザの履歴管理: ユーザーがアクセスしたページの履歴を記録する際、単方向リストに似た構造で管理されることがあります。ただし、ブラウザの「戻る」機能を実現するためには、より高度な構造（双方向リストなど）が必要になることが多いですが、基本的なアクセス順序の記録には利用可能です。
データストリーム処理: データが次々と流れ込んでくる状況（ストリーム）において、データ構造のサイズを動的に変更する必要がある場合に有効です。

初心者向けのアナロジー：次への道順しか書かれていない宝の地図

単方向リストの動作を理解するために、少し物語仕立てのアナロジーを考えてみましょう。

あなたは宝探しをしています。手元にあるのは「宝の地図」です。しかし、この地図は少し変わっています。

最初のノード（ヘッド）: あなたが最初に手にするのは、最初の目印（ノード）がどこにあるかを示す「スタート地点」のメモです。
ノードの構成: 各目印の場所（ノード）には、「宝の一部（データ）」が隠されています。そして、その目印には必ず「次の目印がどこにあるか」という道順（ポインタ）が書かれたメモが一緒に置かれています。
単方向性: 重要なのは、この道順のメモには「次」の場所しか書かれていないことです。「前の目印に戻る道順」は一切書かれていません。

もし、途中で新しい目印（ノード）を追加したいと思ったらどうでしょうか。例えば、目印Cと目印Dの間に新しい目印Xを追加したい場合です。

目印Cのところへ行き、そこにあった「Dへの道順」を消して、「Xへの道順」に書き換えます。
目印Xのところに、「Dへの道順」を書き込みます。

これで、C→X→Dという新しいルートが完成し、地図全体を書き直す必要はありません。これが単方向リストの「効率的な挿入」のイメージです。

しかし、もしあなたが目印Dに到着して、「一つ前の目印Cに戻りたい」と思っても、Dには「次」の道順しか書かれていないため、戻ることはできません。Cの場所を知るためには、またスタート地点（ヘッド）に戻り、最初から道順を辿り直す必要があるのです。これが「単方向リストの制約」であり、この制約があるからこそ、双方向リストという別の構造が必要になる理由も理解できるはずです。

資格試験向けチェックポイント

単方向リストは、基本情報技術者試験（FE）や応用情報技術者試験（AP）において、データ構造の基礎として頻繁に出題されます。特にポインタ操作の理解度が問われます。

| 項目 | 概要と出題パターン | ITパスポート (IP) | 基本情報 (FE) | 応用情報 (AP) |
| :— | :— | :— | :— | :— |
| 定義と目的 | 配列との違い、動的メモリ管理のメリットなど、基本的な概念を問う問題が出ます。 | 〇 (基礎概念) | 〇 | 〇 |
| ノードの操作 | 特定のノードの挿入や削除を行う際の、ポインタの書き換え手順（アルゴリズム）を図示したり、穴埋め形式で問われます。特に「直前のノード」を見つける重要性が問われます。 | – | ◎ (重点項目) | 〇 |
| 計算量 | リストの先頭に要素を追加する際の計算量（O(1)）、特定の要素を検索する際の計算量（O(n)）など、操作にかかる時間の効率性が問われます。 | – | ◎ (重要) | 〇 |
| 双方向リストとの比較 | 単方向リストが「前」へ戻れないことのデメリットと、双方向リストのメリット（ポインタが2つ必要になることによるメモリ消費増）を比較させる問題が出ます。 | 〇 | 〇 | 〇 |
| スタック・キューとの関係 | 単方向リストを用いてスタック（LIFO）やキュー（FIFO）を実装する方法に関する問題が出題されることがあります。 | – | 〇 | 〇 |

学習のヒント:

挿入・削除の手順を紙に書く: 資格試験では、ポインタ操作のミスを誘う問題が多いです。新しいノードを挿入する際、「どのポインタを先に書き換えるか」を間違えると、リストの一部が失われてしまう（前のノードへの参照を失う）ため、手順を正確に覚えることが重要です。
検索はO(n): リストの中から特定のデータを探すには、最悪の場合、先頭からすべてのノードを辿る必要があります。このため、検索効率はリストのサイズ$N$に比例する$O(N)$である、という点をしっかり理解しておきましょう。