データ構造

プログラムがデータをどう保存するかを学ぶ7つのユニットです。配列と動的配列、スタック、キューとリングバッファ、連結リスト、ハッシュテーブル、二分探索木、そしてそれらの選び方を扱います。各ユニットには、挿入と削除を1ステップずつ動かして仕事量を数えるラボ、ページ上で答え合わせできるJavaScriptの演習2つ、解説つきの練習問題10問があります。

進み具合

このコースの出典 (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