連結リスト

場所ではなく、つながりで並ぶ

第3章で扱った配列は、値がメモリ上に隙間なく並んでいて、添字を指定すれば1回で目的の要素にたどり着けました。そのかわり、途中に1つ入れたければ後ろの要素を全部ずらす必要があります。

連結リストは考え方が逆です。要素どうしがばらばらの場所にあってよく、各要素が「次はどこか」を表すポインタ (次の要素の位置を示す値) を持ちます。並び順を決めているのは置かれた場所ではなく、このつながりです。

1つの要素は、値を入れる部分と、次の要素を指す部分の2つでできています。先頭の要素の位置はリスト自身が覚えていて、最後の要素の次は「何も指していない」ことを表す未定義の値になります。

list.先頭 → [A|・] → [B|・] → [C|・] → [D|未定義]

挿入と削除はポインタの付け替えだけ

B と C の間に X を入れたいとします。やることは要素の移動ではなく、次の2つだけです。まず X の次に C を指させ、次に B の次を X に付け替えます。B より後ろの要素は1つも動きません。

削除はもっと簡単で、B を消したければ、A の次を B の次 (つまり C) に付け替えるだけです。B 自体は誰からも指されなくなるので、リストからは消えたことになります。

p.次 ← p.次.次 /* p の次の要素を1つ飛ばして外す */

順番が命

挿入で必ず問われるのが、2つの付け替えをどちらから行うか、です。先に B の次を X にしてしまうと、B から C への唯一のつながりが消え、C 以降がどこにあるか分からなくなります。新しい要素の次を先につないでから、前の要素の次を付け替える、この順番が鉄則です。試験でも、2行の順序を入れ替えた選択肢が誤答として並びます。

配列との使い分け

連結リストは、途中への挿入と削除が前後のポインタの付け替えだけで済むので速いという長所があります。一方で、k 番目の要素を見たいときは先頭から k 回たどる必要があり、添字で一発というわけにはいきません。要素の位置を頻繁に指定して読むなら配列、途中の出し入れが多いなら連結リストです。

先頭方向へも戻れるように、次と前の両方のポインタを持たせたものを双方向リスト、最後の要素の次が先頭を指すものを環状リストと呼びます。双方向リストなら、削除したい要素そのものを渡されても、前の要素をたどり直さずに外せます。呼び名と、その形にする理由をあわせて押さえておきましょう。

端の扱いに気を付ける

連結リストの問題でもう1つ狙われるのが、先頭と末尾です。先頭に入れる場合は前の要素が存在しないので、新しい要素の次に元の先頭を入れてから、リストが覚えている先頭を新しい要素へ書き換えます。末尾に入れる場合は、次が未定義の要素までたどってからつなぎます。どちらも、途中に入れるときの手順がそのまま当てはまらないため、擬似言語では if で場合分けされていることが多い箇所です。空のリストに1つ目を入れる場合も同じ理由で別扱いになります。

選択肢の擬似言語を読むときは、この場合分けが抜けていないかを確かめると、誤答をすばやく落とせます。

次のトレースで、指定した位置まで p をたどり、そこへ新しい要素をつなぐ動きを追ってみましょう。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. p と q には、その要素が持っている値を書く
  4. list は先頭から順にたどった並びを {A, B} の形で書く

ヒント

1 / 9 行目のトレース

1○なし: sonyuu(リスト: list, 文字列型: atai, 整数型: k)
2 要素: p, q
3 整数型: i
4 p ← list.先頭
5 for (i を 1 から k - 1 まで 1 ずつ増やす)
6   p ← p.次
7 endfor
8 q ← 新しい要素(atai)
9 q.次 ← p.次
10 p.次 ← q
実行した行listpqi
実行前{A, B, C, D}———
4 行目

4 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。