単方向リンクリスト
配列は、値を隙間なく 1 列に並べて置きます。先頭に 1 個割り込ませたいだけでも、後ろ全部を 1 つずつずらすことになります。値そのものに「次はこれ」という札を持たせておけば、ずらす必要はなくなります。これが リンクリスト の発想です。
作った直後に、属性を手で書き足すのがつらい
Python
c = Coupon()
c.code = "SPRING"
c.discount = 3003 行がそろって初めて 1 個ぶんです。2 行目を書き忘れても、その場では何も起きません。ずっと後の c.code を読むところで初めて落ちます。作った瞬間に必ず埋まっていてほしい値は、作るときに渡します。
引数で個体差をつける
Python
class Coupon:
def __init__(self, code, discount):
self.code = code
self.discount = discount
self.used = FalseJavaScript
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 回たどることになります。得意な操作がはっきり分かれる、という違いです。
やってみよう
linkedListFromArray(values) を書いてください。まずノードを表すクラスを定義し、値を引数で受け取り、次を指す属性を None で初期化します。values から順にノードを作って繋ぎ、最後に先頭からたどって値を配列に集めて返します。空配列が来たら空配列を返してください。繋ぐ作業には「いまどこまで作ったか」を覚えておく変数が 1 つ要ります。
要件
Nodeクラスを定義し、valueとnext属性を持たせる- values から Node をひとつずつ作り、
nextでつないで単方向リンクリストを構築する - リンクリストを先頭からたどり、値を配列にして返す
入出力例
linkedListFromArray([10,20,30]) → [10,20,30]
linkedListFromArray([42]) → [42]
linkedListFromArray([1,2,3,4,5]) → [1,2,3,4,5]
linkedListFromArray([100,50,25]) → [100,50,25]
linkedListFromArray([7,7,7]) → [7,7,7]ヒント
