連結リスト
連結リストの先頭に値を加えるときに変えるポインターは2つです。リストの値が4個でも400万個でも同じです。
次の値を指す値
配列は値を隣り合わせに並べるので、先頭を変えるのに費用がかかります。連結リストはこの決まりをなくします。それぞれの値はノードと呼ばれる小さな記録に入り、ノードはメモリのどこに置かれてもかまいません。MITの6.006の講義資料では、ノードには2つの欄があります。項目（item）と、次のノードを指すポインターの next です。リスト自体はheadと呼ばれる最初のノードだけを覚えています。最後のノードの next は null で、これが終わりの印です。
リストを読むには、head から始めて next ポインターを1つずつたどります。次のメモが隠してある場所を書いたメモを、順に追っていくようなものです。これには費用がかかります。4番目のノードの番地を求める式はないので、位置 i の値を得るには i + 1 個のノードを訪ねなければなりません。MITの資料では、連結リストの get at(i) は O(n) です。配列なら1ステップでできたことです。
// 値ごとに1つのノード: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// リストをたどる
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4つなぎ直してリストを変える
うまみが出るのはリストを変えるときです。先頭に新しい値を入れるには、next が今の head を指すノードを作り、head をその新しいノードに向けます。ポインターを2つ変えるだけで、ほかには何も動きません。先頭のノードを消すのは1回の変更で、head を head.next に向けるだけです。同じ操作ですべての値が動いた配列とくらべてみてください。
途中の位置では、場所を探すことが仕事になります。位置 i に挿入するには、そのすぐ前のノードまでたどり（i 回の訪問）、同じように2つのポインターを変えます。new.next = prev.next、次に prev.next = new です。この順番が大切です。先に prev.next を変えると、リストの残りを指すものがなくなり、残りが失われてしまいます。ラボでは、ノードを1つ訪ねるか、ポインターを1つ変えるのが1ステップです。だから4ノードのリストの位置2に挿入すると、訪問2回と変更2回で4ステップです。
ドラッグで回転、スクロールまたはピンチで拡大・縮小。
| 操作 | 配列（n個の値） | 連結リスト（n個のノード） |
|---|---|---|
| 位置 i の値を得る | 1 | i + 1 回の訪問 |
| 先頭に挿入 | 移動n回 + 書きこみ1回 | ポインターの変更2回 |
| 先頭を削除する | 読み1回 + 移動 (n − 1) 回 | ポインターの変更1回 |
| 位置 i に挿入する | (n − i) 回の移動 + 書き込み1回 | i 回の訪問 + 変更2回 |
| 値を探す | 最大 n 回の読み取り | 最大 n 回の訪問 |
使いどころ
連結リストが向いているのは、変更のほとんどが先頭のように、すでにポインターを持っている場所で起こり、位置 i をめったに使わないときです。キューやスタックは連結リストで作ることができ、次のユニットのハッシュテーブルの中のチェインも同じです。いくつかの変種があります。双方向連結リストは各ノードに prev ポインターも持たせるので、逆向きにたどれ、ノードを手に入れていれば1ステップで削除できます。head に加えて tail ポインターも持っておくと、末尾への追加が安くなります。
ふだんのJavaScriptで連結リストを書くことはあまりありません。配列はよく最適化されていて、最近のプロセッサーのキャッシュは隣り合わせに保存された値に有利だからです。それでもこの考え方は大切です。木やグラフ、多くのライブラリの構造は、まさにこのようにノードとポインターから作られています。
- 単方向連結リストのノードは、どの2つの欄を持っていますか？
- item と next
- index と value
- left と right
- head と tail
- リスト 12 → 7 → 30 → 4 があります。先頭に新しい値を挿入するのは何ステップですか（ポインターの変更）？
- 同じリストで、位置2に挿入するのは何ステップですか（訪問とポインターの変更の合計）？
- 同じリストで、30を探すと何個のノードを訪ねますか？
- 同じリストで、99を探すと null に着くまでに何個のノードを訪ねますか？
- 同じリストで、位置3のノード（4）を削除するのは何ステップですか？
- 余裕のある配列に1,000個の値が入っています。先頭に挿入するのは何ステップですか？
- 配列より連結リストに向いている仕事はどれですか？
- 位置500の値を何度も読む
- 先頭で何度も追加と削除をする
- 二分探索
- インデックスで並べかえる
- ノード p の後ろに挿入するとき、リストの残りを失わないのはどの順番ですか？
- p.next = new、次に new.next = p.next
- new.next = p.next、次に p.next = new
- どちらの順番でもよい
- 先に p を削除する
- 1956年ごろRANDで作られ、マスをつないだリスト処理を初めて取り入れた言語はどれですか？
- Fortran
- IPL
- C
- JavaScript
- 連結リストはそれぞれの値を next ポインターを持つノードに保存し、リストは head を覚えています。
- 先頭での挿入や削除はポインターを1つか2つ変えるだけで、何も動きません。
- 位置 i に着くには i + 1 回の訪問が必要なので、get at(i) は O(n) です。
- 前のノードをつなぎ直す前に new.next を設定します。
このコースの出典 (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
確認日: 2026-10-18