リンクリスト構築と長さの計算
配列の途中に 1 件差し込むと、後ろの要素はすべて 1 つずつ後ろへずれます。先頭に差し込めば、全件が動きます。この「ずらす」をやめるために作られた形が連結リストです。
途中に 1 件足すたび、後ろが全部ずれる
配列は箱が隙間なく並んでいるので、割り込むには後ろを動かすしかありません。連結リストは箱をばらばらの場所に置き、それぞれが「次はどこにあるか」という札を持ちます。割り込みたいときは札を 2 枚書き換えるだけで、他の箱は 1 つも動きません。
代わりに失うものもあります。
| 操作 | 配列 | 連結リスト |
|---|---|---|
| 100 番目を見る | すぐ届く | 先頭から 100 回たどる |
| 先頭に差し込む | 全件ずらす | 札を 2 枚書き換える |
| 1 件あたりの容量 | 値だけ | 値と札 |
ノードは「中身」と「次はどこか」の 2 つを持つ
連結リストの 1 単位をノードと呼びます。持ち物は 2 つだけです。
Python
class Node:
def __init__(self, value):
self.value = value
self.next = NoneJavaScript
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}next の初期値が空なのが大事です。空は「この先はもう無い」という末尾の印になります。
末尾を探すのに、毎回先頭から歩くことになる
再生キューを思い浮かべてください。曲を 1 曲足すには、末尾のノードの next に新しいノードをつなぎます。ところが末尾がどこかは、先頭から札をたどらないと分かりません。
Python
cur = head
while cur.next is not None:
cur = cur.next
print(cur.value) # 最後の曲1 曲足すたびにこれをやると、曲数が増えるほど遅くなります。だから組み立てる側は、末尾のノードを覚えておく変数をもう 1 つ持ちます。新しいノードをつないだら、その変数も新しいノードへ移してください。移し忘れると、同じノードの next を何度も上書きすることになり、つないだはずの 2 個目以降が消えます。
もう 1 つ、先頭のノードを指す変数は絶対に動かさないでください。歩くときは作業用の変数を別に用意します。先頭を進めてしまうと、そこより前のノードを指す札がどこにも無くなり、リストごと行方不明になります。歩き終わったあとに先頭へ戻れないのが、連結リストの怖いところです。
先頭が空のときは、上の while が 1 度も回りません。空のリストは長さ 0 で、たどる相手がいない状態です。逆に中身が n 件あれば、末尾に着くまでに必ず n 回たどることになります。配列の要素数がその場で分かるのとは対照的です。
今回の課題では、この歩き方をしながら通ったノードの数を数えます。配列の要素数をそのまま返してしまうと、たどる練習になりません。
要件
- 内部で Node オブジェクト (value + next) を組み立てること
- head から next ポインタを辿ってノード数を数えること
- arr.length / len(arr) を直接返さないこと (走査が前提)
入出力例
listLength([1,2,3]) → 3
listLength([42]) → 1
listLength([5,6,7,8,9]) → 5
listLength([0,0,0,0]) → 4
listLength([-1,-2,-3]) → 3
listLength([1,2,3,4,5,6,7,8,9,10]) → 10ヒント
