1 歩ずつ動かす
命令の列 (左から順に実行する)
- 先頭 (添字 0) に 1 を入れる
- 添字 2 に 7 を入れる
- 8 を削除
- 1 を削除
- head から読んだ並び
- 3 → 8 → 5
- いま見ているノード (cur)
- なし
- いま見ているノード (cur)
- その前のノード (prev)
- 作ったばかりのノード (下の行)
- いま書き換えた矢印
1 歩目 / 全 16 歩実行した命令 0 個たどったノード 0 個ノード 3 個
リストは 3 → 8 → 5 です。head が先頭の 3 を指しています。
いま動いている疑似コードの行
- 1insert(index, x)
- 2新しいノード n を作り、x を入れる
- 3index が 0 なら、n.next を head にして、head を n にする
- 4そうでなければ、head から添字 index - 1 のノード p まで進む
- 5n.next を p.next にして、p.next を n にする
- 6delete(x)
- 7head から順に、値が x のノードを探す
- 8先頭なら head をその次にし、途中なら前のノードの next をその次にする
見本を変える
予想してみる
いまの歩の次は、ポインタを書き換える歩ではありません。「1 歩進む」で、書き換える手前まで進めましょう。
今回わかること
- ノードが next でつながる形と、head の役目
- 先頭と途中に挿入するときの、ポインタを付け替える順番
- 削除のときに、前のノードの next を書き換える理由
前提
- 配列と添字
- 変数が別の値を指す (参照) という考え方
どんな入れ物か
連結リストは、値と「次のノードはどれか」を持つ小さな箱 (ノード) を、next でつないで並べる入れ物です。先頭を指す head を持っておけば、そこから next をたどって全部の値に行けます。
配列は値を隙間なく並べるので、途中に入れると後ろ全部をずらします。連結リストは next を 2 本付け替えるだけで済みます。そのかわり、添字 n の値を知るには head から n 回たどります。
手順と具体例
- 1新しいノードを作る (まだ列につながっていない)
- 2新しいノードの next を、入れる場所の次のノードにする
- 3前のノードの next (先頭なら head) を、新しいノードにする
- 4削除は、前のノードの next (先頭なら head) を、外すノードの次にする
| 命令 | たどったノード | 実行したあとの並び |
|---|---|---|
| 先頭 (添字 0) に 1 を入れる | 0 個 | 1 → 3 → 8 → 5 |
| 添字 2 に 7 を入れる | 2 個 | 1 → 3 → 7 → 8 → 5 |
| 8 を削除 | 4 個 | 1 → 3 → 7 → 5 |
| 1 を削除 | 1 個 | 3 → 7 → 5 |
たどる数と計算量
| 操作 | たどるノード | 計算量 |
|---|---|---|
| 先頭に入れる | 0 個 (head を付け替えるだけ) | O(1) |
| 添字 k に入れる | k 個 (1 つ前のノードまで) | O(n) |
| 値を探して削除する | 最大 n 個 (無いときは全部) | O(n) |
n はノードの数です。入れる場所の 1 つ前のノードをもう手に持っているなら、途中への挿入も O(1) です。手間の差は、そこまでたどる回数から来ます。見本の「ふつうの例」では、たどったノードが 0 個、2 個、4 個、1 個でした。
使いどころ
向いているとき
- 先頭への挿入と削除をくり返すとき (スタックを作る)
- 途中への挿入が多く、配列で後ろをずらす手間が重いとき
- 個数が決まっておらず、増えたり減ったりするとき
向いていないとき
- 添字で値を何度も直接読みたいとき (配列を使う)
- 値が小さく少ないとき (ノードごとに next の置き場が要る)
コード
疑似コード
- 1insert(index, x)
- 2新しいノード n を作り、x を入れる
- 3index が 0 なら、n.next を head にして、head を n にする
- 4そうでなければ、head から添字 index - 1 のノード p まで進む
- 5n.next を p.next にして、p.next を n にする
- 6delete(x)
- 7head から順に、値が x のノードを探す
- 8先頭なら head をその次にし、途中なら前のノードの next をその次にする
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 挿入のとき、前のノードの next を先に書き換えてはいけないのですか？
- 先に書き換えると、元の次のノードを指すものが無くなり、そこから先のノードに行けなくなります。新しいノードの next に元の次のノードをつないでから、前のノードの next を替えます。
- 外したノードは、どうなりますか？
- どこからも指されなくなったノードは、Python、JavaScript、Java では自動で片付けられます。C 言語のように自分で解放する言語では、解放し忘れるとメモリが残ります。
- 配列とは、どう使い分けますか？
- 添字で何度も読むなら配列、先頭への出し入れが多いなら連結リストです。実際には、配列のほうがメモリ上で連続していて速いことが多いので、迷ったら配列から始めます。
