リスト構造とポインタ（linked list / pointer）
データ1つずつに「次がどこにあるか」を持たせてつないだ並べ方。途中の出し入れが速い。
もう少し詳しい説明
リスト構造は、データ1つずつに「次がどこにあるか」を持たせて、数珠つなぎにした並べ方です。
ポインタは、場所を指す値です。データそのものではなく、どこにあるかだけを持ちます。
まず、配列と比べる
比べる相手がないと、どこが利点なのかが見えません。配列から見ます。
配列は、同じ大きさの箱を、すきまなく並べて置いたものです。座席の並んだ映画館を思い浮かべてください。1番、2番、3番と番号が振られ、番号を確かめれば、その席へまっすぐ行けます。
これが速さの理由です。先頭の場所と、箱1つの大きさが分かっていれば、5番目の場所は計算で出ます。何番目であっても、かかる手間は同じです。
困るのは、途中に割り込ませたいときです。3番と4番のあいだに1人入れるには、4番以降の全員が1つずつ後ろへ移ることになります。100人並んでいれば97人が動きます。
リストは、場所を自由にする
リストは、箱を並べて置くことをやめます。
箱はばらばらの場所にあってよく、かわりにそれぞれが「次の箱はどこか」というメモを持ちます。上の図の2行目がそれです。このメモがポインタです。
宝探しにたとえます。1枚目の紙に「次は本棚の裏」と書いてあり、本棚の裏の紙に「次は机の下」と書いてある。紙どうしは離れた場所にあっても、順番は決まっています。
最後の箱には次がありません。ここには何も指していないという印を入れます。プログラムでは null（ヌル。何も指していないことを表す値）と書かれます。
割り込ませるのが速い
リストの強いところがここです。
AとBのあいだにXを挟むには、書き換えるのは2か所だけです。
- Xの「次」を、Bの場所にする
- Aの「次」を、Bの場所からXの場所へ書き換える
B以降には手を触れません。 100人並んでいても、動かすのは2か所です。配列のように、後ろの全員がずれることがありません。
削除も同じです。 Bを外したいなら、Aの「次」をCの場所に書き換えるだけで済みます。Bは誰からも指されなくなるので、列から消えます。1か所の書き換えで終わります。
代わりに失うもの
良いことばかりではありません。たとえば5番目を取り出す場面では、配列より時間がかかります。
配列なら計算で一発です。リストは先頭から順にたどることになります。1番目のメモを読んで2番目へ行き、2番目のメモを読んで3番目へ行く。5番目に着くまで、4回たどります。
100番目なら99回です。番号で一発に取り出すことができません。
もう1つ、メモを置く場所が余分に要ります。データ1つにつき、ポインタ1つぶんの領域が増えます。
表にして並べる
| 配列 | リスト | |
|---|---|---|
| n番目を取り出す | 速い（計算で出る） | 遅い（先頭からたどる） |
| 途中へ挿入・削除 | 遅い（後ろをずらす） | 速い（2か所の書き換え） |
| 余分な領域 | 要らない | ポインタのぶん要る |
| 置き場所 | 連続していないと困る | ばらばらでよい |
得意なことが、ちょうど逆になっています。 どちらが優れているという話ではなく、何をよくするかで選びます。
計算量（件数が増えたときに手間がどう伸びるか）の言い方では、n番目の取り出しが配列は O(1)、リストは O(n) です。挿入・削除は、場所が分かっていれば配列が O(n)、リストは O(1) になります。
3つの形
リストには、持たせるメモの数と向きで3つの形があります。
| 形 | 持つメモ | できること |
|---|---|---|
| 単方向リスト | 次だけ | 前から後ろへたどる |
| 双方向リスト | 次と前 | 後ろへも戻れる |
| 環状リスト | 次（最後が先頭を指す） | ぐるぐる回れる。終わりが無い |
双方向リストは、戻れる代わりに書き換える場所が増えます。挿入のときは、前後それぞれの「次」と「前」を直すので、4か所になります。
環状リストは、最後の箱が先頭を指します。順番に処理を回し続けたい場面で使われます。
何の土台になっているか
リストは、ほかの構造の材料として使われます。
- キュー（先に入れたものから先に出す構造）… 先頭と末尾だけを触るリスト
- スタック（後に入れたものから先に出す構造）… 先頭だけを触るリスト
- 木構造（枝が分かれていく構造）… 子の場所を指すメモを複数持たせた形
メモを何本持たせるか、どの向きに持たせるかを変えると、別の構造になります。リストは、その一番単純な形にあたります。
試験ではこう出る
科目A（旧・午前）のアルゴリズムとプログラミングで出ます。科目B（旧・午後）でも、擬似言語の中に出てきます。
いちばん多いのは、配列とリストの比較です。「途中への挿入・削除は速いが、n番目の参照は遅い」が答えの向きになります。どちらが速いかを入れ替えた選択肢が誤答として並びます。
次に多いのが、挿入のときに書き換えるポインタを選ばせる問題です。図を見せて「どの要素のポインタを、どこへ向けるか」を答えさせます。単方向なら2か所、双方向なら4か所という数を覚えておくと、選択肢を絞れます。
順番を間違えると壊れる点も問われます。先にAの「次」をXへ向けてしまうと、Bの場所が分からなくなります。新しい箱のメモを先に書き、つなぎ替えは後という順です。
応用情報では、環状リストや双方向リストの操作まで出ます。環状リストは「終わりの判定ができない」ことが問われます。先頭に戻ったかどうかを自分で覚えておく必要があります。
関連する用語
- キュー
- 先に入れたものから先に出す構造。リストで作ることができる
- スタック
- 後に入れたものから先に出す構造。これもリストで作れる
- 木構造
- 枝が分かれていく構造。子の場所を指すポインタを複数持たせた形にあたる
- 計算量
- 件数が増えたときの伸び方。配列とリストは、得意な操作が逆になる
- 値呼出しと参照呼出し
- 引数の渡し方。場所を渡すという考え方はポインタと同じ
ミニクイズ
単方向リスト（各要素が次の要素の場所だけを持つリスト）で、要素Aと要素Bのあいだに新しい要素Xを挿入するとき、行う必要がある操作はどれか。
正解は 3番：Xの「次」をBにし、Aの「次」をXに書き換える
単方向リストでは、要素が自分の次の場所だけを持っています。AとBのあいだにXを挟むには、Xの「次」をBに設定し、Aの「次」をBからXへ書き換えます。この2か所だけで済み、B以降には手を触れません。要素をずらすのは配列での挿入のやり方で、リストではその必要がありません。Xの「次」をAにすると向きが逆になり、つながりが壊れます。全要素を書き換える必要もありません。
この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）
最終更新：2026-11-05