単方向リンクリスト

配列は、値を隙間なく 1 列に並べて置きます。先頭に 1 個割り込ませたいだけでも、後ろ全部を 1 つずつずらすことになります。値そのものに「次はこれ」という札を持たせておけば、ずらす必要はなくなります。これが リンクリスト の発想です。

作った直後に、属性を手で書き足すのがつらい

c = Coupon()
c.code = "SPRING"
c.discount = 300

3 行がそろって初めて 1 個ぶんです。2 行目を書き忘れても、その場では何も起きません。ずっと後の c.code を読むところで初めて落ちます。作った瞬間に必ず埋まっていてほしい値は、作るときに渡します。

引数で個体差をつける

class Coupon:
    def __init__(self, code, discount):
        self.code = code
        self.discount = discount
        self.used = False

class Coupon {
  constructor(code, discount) {
    this.code = code;
    this.discount = discount;
    this.used = false;
  }
}

Coupon("SPRING", 300) と Coupon("AUTUMN", 500) は、同じ設計図から作られた別々の個体です。渡した引数の違いが、そのまま個体差になります。

used には引数がありません。作る時点では決まっておらず、後から変わる値だからです。「まだ何も無い」を表す初期値を置いておくのは、__init__ のもう 1 つの役割です。

まだ繋がっていないことを、null で表す

リンクリストの部品は、値を 1 つと、次の部品を指す札を 1 つ持ちます。値は作るときに引数で受け取り、次を指す札は「まだ何も指していない」状態、つまり None や null から始めます。

最後の部品の札だけが null のままです。この 1 個だけ違う状態が、「ここで終わり」の合図になります。たどる側は、札が null になるまで次へ次へと移り続ければ、全部の値を順番に見られます。

配列なら先頭に 1 個割り込ませるだけで後ろ全部がずれますが、この形なら札を 2 本繋ぎ替えれば済みます。代わりに、5 番目の値がほしいときは先頭から 5 回たどることになります。得意な操作がはっきり分かれる、という違いです。

やってみよう

ひな形の TODO を完成させてください。ノードをつなぐ操作と、next をたどる走査を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

Node は値と次のノードを持ち、None は次がない印です。たとえば 4 → 9 → None のリストでは、4 を読んだ後に next で 9 へ移動し、その次で止まります。先頭ノードと出力配列は用意しました。残りをつなぐ本体と、値を集めながら next をたどるループを書きます。

1. ノードをつなぐ操作と、next をたどる走査を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える