リストとは？配列との違い・連結リスト・二分木の表現を基礎から理解しよう

はじめに

プログラムでは、大量のデータを扱うためにデータ構造を利用します。

その代表的なものの一つが**リスト（List）**です。

リストは、

複数のデータを一定の順序で管理するデータ構造

です。

特に応用情報技術者試験では、連結リストのポインタを書き換えてデータを挿入・削除する問題や、リストを利用して木構造を表現する考え方を理解しておくことが重要です。

この記事では、

データ構造
↓
リスト
↓
連結リスト
↓
単方向・双方向・循環リスト
↓
挿入・削除
↓
二分木の表現

という順番で見ていきます。

1. データ構造とは

**データ構造（Data Structure）**とは、

コンピュータ上でデータを効率よく扱うためのデータの持ち方

です。

例えば、

りんご
みかん
ぶどう

という3つのデータがあったとします。

これらをバラバラに管理するのではなく、一定のルールに従ってまとめることで、検索・追加・削除などの処理を行いやすくします。

代表的なデータ構造には、

配列
リスト
スタック
キュー
木
グラフ

などがあります。

2. リストとは

**リスト（List）**とは、複数のデータを順番に並べて管理するデータ構造です。

例えば、

A → B → C → D

というようにデータを管理します。

このようにデータが一列に並んでいる構造を、線形構造といいます。

そのため、リストは代表的な線形データ構造の一つです。

3. 配列とリスト

複数のデータを扱う方法として、リストと一緒によく登場するのが**配列（Array）**です。

例えば配列では、

添字
 0   1   2   3
┌───┬───┬───┬───┐
│ A │ B │ C │ D │
└───┴───┴───┴───┘

のようにデータを並べます。

一般的な配列では、要素がメモリ上の連続した領域に配置されます。

そのため、

array[2]

のように添字を指定することで、目的の要素へ直接アクセスできます。

4. 連結リストとは

応用情報で特に重要なのが**連結リスト（Linked List）**です。

連結リストでは、それぞれの要素が、

┌──────────┬──────────┐
│ データ   │ 次の要素 │
└──────────┴──────────┘

のような情報を持ちます。

例えば、

[A | ●] → [B | ●] → [C | ●] → [D | NULL]

のようにつながります。

ここで重要なのが、

次の要素がどこにあるのかを示す情報

です。

このような参照情報を、問題やプログラミング言語によってはポインタや参照などと呼びます。

5. ノードとは

連結リストを構成する一つ一つの要素を**ノード（Node）**と呼びます。

基本的なノードは、

┌──────────┬──────────┐
│ データ   │ ポインタ │
└──────────┴──────────┘

という構造を持ちます。

例えば、

[A | →] → [B | →] → [C | NULL]

なら、

A
B
C

がデータ部分です。

そして、

→

が次のノードを示す情報です。

つまり、

ノード = データ + 次のノードを示す情報

と考えると分かりやすいです。

6. 先頭ポインタ

連結リストでは、最初のノードがどこにあるのかを知る必要があります。

そこで利用するのが先頭ポインタです。

head
 ↓
[A | →] → [B | →] → [C | NULL]

headから最初のノードAをたどり、

A
↓
B
↓
C

と順番にアクセスできます。

7. リストの終端

単方向の連結リストでは、最後のノードには次のノードがありません。

そこで、

[A | →] → [B | →] → [C | NULL]

のように、次の要素が存在しないことを表す値を持たせます。

代表的なのが、

NULL

です。

つまり、

NULL
=
次のノードが存在しない

と考えます。

8. 単方向リスト

ここまで説明してきた、

A → B → C → D

のようなリストを**単方向リスト（Singly Linked List）**と呼びます。

各ノードは、

次のノード

だけを覚えています。

[A | →] → [B | →] → [C | →] → [D | NULL]

そのため、基本的には前から後ろへ順番にたどっていきます。

9. 双方向リスト

前後どちらにも移動できるようにしたものが**双方向リスト（Doubly Linked List）**です。

各ノードが、

前のノード
データ
次のノード

の情報を持ちます。

NULL ← A ⇄ B ⇄ C ⇄ D → NULL

ノードの構造は、

┌────────┬────────┬────────┐
│ 前     │ データ │ 次     │
└────────┴────────┴────────┘

です。

これによって前方向だけでなく、逆方向にもたどれます。

10. 単方向リストと双方向リスト

違いを整理すると次のようになります。

種類	持っているリンク	移動
単方向リスト	次のノード	基本的に一方向
双方向リスト	前と次のノード	前後両方向

双方向リストは便利ですが、各ノードが前後2つの参照情報を持つため、その分必要な情報も増えます。

11. 循環リスト

**循環リスト（Circular List）**は、最後のノードから再び先頭ノードへ戻る構造です。

通常の単方向リストでは、

A → B → C → NULL

となります。

循環リストでは、

A → B → C
↑       ↓
└───────┘

となります。

つまり、最後まで進んでも終端にならず、再び先頭へ戻れます。

順番に処理対象を切り替えていくような処理と相性のよい構造です。

12. 連結リストへの挿入

例えば、

A → B → C

というリストのAとBの間にXを追加するとします。

完成形は、

A → X → B → C

です。

重要なのは、既存のデータ全体をずらすのではなく、リンクを書き換えることです。

13. 挿入時のリンク変更

もともと、

A → B

となっていたとします。

Xを挿入するなら、

A → X
X → B

となるように変更します。

ただし、ポインタを書き換える順番には注意が必要です。

① Xの次をBにする
② Aの次をXにする

つまり、

X.next = A.next
A.next = X

です。

結果、

A → X → B

となります。

🍯 既存のリンクを切る前に、必要なリンクを確保する

と覚えると分かりやすいです。

14. 連結リストからの削除

今度は、

A → B → C

からBを削除してみます。

完成形は、

A → C

です。

つまり、

A → B

となっていたリンクを、

A → C

へ変更します。

イメージすると、

変更前

A → B → C


変更後

A ─────→ C

です。

15. 配列と連結リストの挿入・削除

配列では、

[A][B][C][D]

のAとBの間へXを挿入すると、

[A][X][B][C][D]

となるように、必要に応じて後ろの要素を移動させます。

削除の場合も同様です。

一方、連結リストでは、

A → B → C → D

からBを削除するとき、

A ─────→ C → D

のようにリンクを変更します。

要素そのものを一つずつ前へ移動させる必要はありません。

16. では連結リストの方が速い？

ここで注意が必要です。

連結リストはリンクの変更による挿入・削除が得意ですが、

操作する場所を探す処理まで常に高速というわけではありません。

例えば、

A → B → C → D → E

からDを探す場合、

A
↓
B
↓
C
↓
D

と先頭から順番にたどる必要があります。

17. 配列は直接アクセスしやすい

配列では、

array[3]

のように添字を利用して目的の要素へ直接アクセスできます。

一方、連結リストで4番目の要素へアクセスするには、

1番目
↓
2番目
↓
3番目
↓
4番目

と順番にたどります。

18. 配列と連結リストの比較

項目	配列	連結リスト
データの配置	基本的に連続	連続している必要はない
要素へのアクセス	添字で直接アクセスしやすい	順番にたどる
途中への挿入	要素移動が必要になる場合がある	リンク変更で対応できる
途中からの削除	要素移動が必要になる場合がある	リンク変更で対応できる
追加情報	基本的に不要	ポインタ・参照情報が必要

つまり、

配列
→ 要素への直接アクセスが得意

連結リスト
→ リンク変更による挿入・削除が得意

という違いがあります。

19. 計算量で考える

アルゴリズムでは、処理に必要な計算量をオーダ記法で表します。

配列で添字から要素へアクセスする処理は、

O(1)

です。

一方、単方向連結リストでn番目の要素を先頭から探す場合は、

O(n)

となります。

連結リストでは、操作対象の位置が既に分かっていれば、リンクの変更自体は、

O(1)

で行えます。

ただし、

対象を探す
↓
リンクを書き換える

という処理なら、探索部分にO(n)かかる場合があります。

そのため、

連結リストの挿入・削除は必ずO(1)

と丸暗記しないことが大切です。

20. リストをたどる処理

単方向リストを先頭から最後まで処理する場合は、

現在位置 = 先頭

while 現在位置 != NULL
    データを処理
    現在位置 = 次のノード

という考え方になります。

例えば、

A → B → C → NULL

なら、

Aを処理
↓
Bを処理
↓
Cを処理
↓
NULLなので終了

です。

ポインタを使った問題では、この「現在位置を次へ進める」という考え方が非常に重要です。

21. リストによる二分木の表現

ここからは、リストの考え方を少し発展させます。

これまでの単方向リストでは、一つのノードが、

┌────────┬────────┐
│ データ │ 次     │
└────────┴────────┘

という構造を持っていました。

では、ポインタを2つ持たせるとどうなるでしょうか。

┌────────┬────────┬────────┐
│ 左     │ データ │ 右     │
└────────┴────────┴────────┘

このように、

左側のノードを示すポインタ
右側のノードを示すポインタ

を持たせることで、**二分木（Binary Tree）**を表現できます。

22. 二分木とは

二分木とは、

一つのノードが最大2つの子ノードを持つ木構造

です。

例えば、

という構造です。

Aから見ると、

左の子 → B
右の子 → C

となります。

Bから見ると、

左の子 → D
右の子 → E

です。

23. ノードに2つのポインタを持たせる

二分木のノードをリスト形式で表現すると、

┌──────────┬──────────┬──────────┐
│ 左ポインタ│ データ   │右ポインタ│
└──────────┴──────────┴──────────┘

のようになります。

例えばAなら、

┌─────┬─────┬─────┐
│ B   │ A   │ C   │
└─────┴─────┴─────┘

と考えられます。

これは、

A
├─ 左 → B
└─ 右 → C

という意味です。

24. 二分木を表で表してみよう

次の二分木を考えます。

これを各ノードが持つ情報として整理すると、

ノード	左の子	右の子
A	B	C
B	D	E
C	NULL	NULL
D	NULL	NULL
E	NULL	NULL

となります。

つまりAは、

左 → B
右 → C

Bは、

左 → D
右 → E

を覚えています。

そしてC・D・Eには子がいないため、

NULL

となります。

25. 連結リストから二分木へ

ここはかなり大事です。

単方向リストでは、

A → B → C

のように、一つのノードから1方向へリンクしていました。

ノード
└─ 次

一方、二分木では、

        A
       / \
      B   C

のように、一つのノードから最大2方向へリンクします。

ノード
├─ 左
└─ 右

つまり考え方としては、

単方向リスト
→ ポインタ1個

二分木
→ ポインタ2個

と捉えると理解しやすくなります。

26. 二分木もノードをたどってアクセスする

二分木でも、連結リストと同じようにポインタをたどってノードへアクセスします。

例えば、

でEへアクセスするなら、

A
↓ 左
B
↓ 右
E

とたどります。

つまり、

A.left.right

というイメージです。

連結リストで、

A.next.next

とたどっていた考え方が、木構造では、

left
right

へ広がったと考えることができます。

27. リストによる二分木表現のメリット

ポインタを使って二分木を表現すると、ノード同士をリンクによって接続できます。

そのため、

        A
       / \
      B   C

のような階層構造を表現できます。

さらにノードを追加するときも、

のように、必要なリンクを設定することで構造を作れます。

連結リストで学んだ、

ノード同士をポインタでつなぐ

という考え方が、そのまま木構造にもつながっています。

28. 子が存在しない場合はNULL

例えば、

        A
       / \
      B   C

でBとCに子が存在しない場合、

B.left  = NULL
B.right = NULL

C.left  = NULL
C.right = NULL

となります。

つまり、

NULL
=
その方向に子ノードが存在しない

という意味です。

これは連結リストの終端で、

C.next = NULL

としていたのと同じ考え方です。

29. 配列による二分木表現との違い

二分木は、リストだけでなく配列を利用して表現する方法もあります。

例えば完全二分木では、ノードを配列へ順番に格納することで、添字を利用して親子関係を求めることができます。

一方、リストを使った表現では、

ノード
├─ 左ポインタ
└─ 右ポインタ

によって親子関係を直接表現します。

そのため、

配列
→ 添字を利用して親子関係を表す

リスト
→ ポインタを利用して親子関係を表す

という違いがあります。

二分木については、木構造の記事でさらに詳しく扱います。

30. 応用情報で押さえたいポイント

リストでは、まず次の関係を理解しておきましょう。

単方向リスト

┌──────┬──────┐
│データ│ 次   │
└──────┴──────┘


双方向リスト

┌──────┬──────┬──────┐
│ 前   │データ│ 次   │
└──────┴──────┴──────┘


二分木

┌──────┬──────┬──────┐
│ 左   │データ│ 右   │
└──────┴──────┴──────┘

見た目は似ていますが、それぞれポインタの意味が異なります。

特に二分木では、

左ポインタ
→ 左の子ノード

右ポインタ
→ 右の子ノード

という関係を読み取れるようにしておくことが重要です。

31. まとめ

リストは、

複数のデータを一定の順序で管理するデータ構造

です。

連結リストでは、

ノード
=
データ
+
他のノードを示す情報

という考え方を利用します。

代表的な構造は、

構造	ポインタ
単方向リスト	次
双方向リスト	前・次
循環リスト	最後から先頭へ接続
二分木	左の子・右の子

です。

特に大切なのは、

リスト
↓
ノード同士をリンクする
↓
リンクを増やす
↓
木構造も表現できる

というつながりです。

この記事で覚えること

リストは順序を持ってデータを管理する
連結リストはノード同士をポインタでつなぐ
単方向・双方向・循環リストがある
挿入・削除ではリンクの付け替えが重要
配列と連結リストでは得意な操作が異なる
二分木は左右2つのポインタを持つノードで表現できる
子ノードが存在しない場合はNULLを設定する
連結リストの「ポインタをたどる」という考え方は木構造にもつながる

🍯 はちみつメモ

リストも二分木も基本は同じ。「データそのもの」だけでなく、「次はどこ？」という情報を持たせる。二分木では、その行き先が「左」と「右」の2つになる。