リンクリスト構築と長さの計算

配列の途中に 1 件差し込むと、後ろの要素はすべて 1 つずつ後ろへずれます。先頭に差し込めば、全件が動きます。この「ずらす」をやめるために作られた形が連結リストです。

途中に 1 件足すたび、後ろが全部ずれる

配列は箱が隙間なく並んでいるので、割り込むには後ろを動かすしかありません。連結リストは箱をばらばらの場所に置き、それぞれが「次はどこにあるか」という札を持ちます。割り込みたいときは札を 2 枚書き換えるだけで、他の箱は 1 つも動きません。

代わりに失うものもあります。

ノードは「中身」と「次はどこか」の 2 つを持つ

連結リストの 1 単位をノードと呼びます。持ち物は 2 つだけです。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

next の初期値が空なのが大事です。空は「この先はもう無い」という末尾の印になります。

末尾を探すのに、毎回先頭から歩くことになる

再生キューを思い浮かべてください。曲を 1 曲足すには、末尾のノードの next に新しいノードをつなぎます。ところが末尾がどこかは、先頭から札をたどらないと分かりません。

cur = head
if cur is not None:
    while cur.next is not None:
        cur = cur.next
    print(cur.value)   # 最後の曲

1 曲足すたびにこれをやると、曲数が増えるほど遅くなります。だから組み立てる側は、末尾のノードを覚えておく変数をもう 1 つ持ちます。新しいノードをつないだら、その変数も新しいノードへ移してください。移し忘れると、同じノードの next を何度も上書きすることになり、つないだはずの 2 個目以降が消えます。

もう 1 つ、先頭のノードを指す変数は絶対に動かさないでください。歩くときは作業用の変数を別に用意します。先頭を進めてしまうと、そこより前のノードを指す札がどこにも無くなり、リストごと行方不明になります。歩き終わったあとに先頭へ戻れないのが、連結リストの怖いところです。

先頭が空のときは、上の if の中へ入らず、while の条件も調べません。空のリストは長さ 0 で、たどる相手がいない状態です。中身が n 件あれば、末尾に着くまでに next を n - 1 回たどります。長さを数える演習では末尾も含む n 個のノードを見て、最後は None へ進みます。配列の要素数がその場で分かるのとは対照的です。

今回の課題では、この歩き方をしながら通ったノードの数を数えます。配列の要素数をそのまま返してしまうと、たどる練習になりません。

1. 用意済みの buildList を使う
2. cur が None になるまで next をたどって数える
3. len(arr) を直接返さない