Choosing a data structure
Among 1,023 keys, a linear search for a missing key makes 1,023 comparisons, binary search makes 10, and a hash table with 1,023 buckets made at most 6 in the lab.
Start from the questions you will ask
No structure is best at everything. Each one makes some operations cheap by making others expensive, so the way to choose is to list what your program will do most often. MIT's 6.006 splits the possibilities into two interfaces. A sequence keeps items in an order you decide (first, second, third), and you ask for items by position. A set keeps items by key, and you ask whether a key is there, or for the smallest key, or the next one after a given key. A set without the order questions is called a dictionary.
A few common situations and the usual answer:
- Read items by position, add at the end: a dynamic array (a JavaScript array).
- Undo history, matching brackets, depth-first search: a stack, which is an array used only at its end.
- Jobs handled in arrival order, breadth-first search: a queue, with a head index or a ring buffer rather than shift on a long array.
- Look things up by name or id: a hash table, which in JavaScript means Map or Set.
- Keep keys sorted while inserting and deleting, ask for the next key: a balanced binary search tree.
- Many inserts and deletes at a spot you already hold: a linked list.
The same lookup in five structures
The lab below stores the same keys in five ways and counts the comparisons needed to find one of them. The keys are 15, 127 or 1,023 random whole numbers. The unsorted array uses linear search. The sorted array uses binary search. The balanced tree was built by inserting middle keys first, so it is as short as possible. The other tree was built from the keys in sorted order, so it is a chain. The hash table has as many buckets as keys and counts 1 for computing h(k).
Drag to turn. Scroll or pinch to zoom.
With 15 keys the differences are small: linear search needs 8 comparisons on average and binary search about 3.3. With 1,023 keys they are not. Linear search averages 512 and needs 1,023 for a missing key, while binary search and the balanced tree never need more than 10. The chain tree is as bad as linear search. The hash table stays between 2.3 and 2.5 on average at every size because its chains stay short, and in this lab its worst case for 1,023 keys was 6. That is why Map is the default choice for lookups, and why sorted structures are worth it only when you also need order.
| By position | Get item i | Insert or delete at front |
|---|---|---|
| Dynamic array | 1 | n |
| Linked list | n | 1 |
| Sorted array | 1 | n |
| By key | Find | Insert | Next key |
|---|---|---|---|
| Array or list | n | n | n |
| Sorted array | log n | n | log n |
| Hash table | 1 on average | 1 on average | n |
| Balanced BST | log n | log n | log n |
Each cell in these two tables is the growth rate of the cost for n items, following the tables in MIT's lecture notes 2, 4 and 7. Hash tables and search trees appear only in the second table because they work by key, not by position. In an unsorted array or a list, inserting a key costs n because you must first check that it is not already there. The sorted array finds quickly but has to move values to make room for a new key.
Map or object?
JavaScript programs often use a plain object as a dictionary, writing prices["apple"]. MDN lists reasons to prefer Map when the keys come from data: an object has a prototype, so it contains default keys that could collide with yours; a Map can use any value as a key, not only strings and symbols; its size is one property, map.size; and it is iterated in insertion order. Objects remain the natural choice for records with a fixed set of named fields.
- 1953: H. P. Luhn's IBM memorandum suggests hashing into buckets with chaining.
- About 1956: Newell, Shaw and Simon's IPL brings linked lists.
- 1957: Bauer and Samelson apply for a patent on the stack method; Fortran ships with arrays.
- 1962: Adelson-Velsky and Landis publish the AVL tree, the first balanced search tree.
- 2015: ECMAScript 2015 adds Map and Set to JavaScript.
- Linear search for a missing key among 1,023 keys makes how many comparisons?
- Binary search among 1,023 sorted keys makes at most how many comparisons?
- Linear search over 15 keys: what is the average number of comparisons over all 15 keys?
- A BST built from 127 keys inserted in sorted order: how many comparisons for the largest key?
- A text editor needs Undo. Which structure fits?
- Queue
- Stack
- Hash table
- Sorted array
- A print server must handle jobs in the order they arrive. Which structure fits?
- Queue
- Stack
- BST
- Linked list used as a stack
- You must look up a user record by its id many times per second. Which is the usual choice in JavaScript?
- An array searched with a loop
- A Map keyed by id
- A stack
- A linked list
- You need keys kept in sorted order while inserting and deleting, and you often ask for the next larger key. Which fits best?
- Hash table
- Balanced BST
- Queue
- Unsorted array
- In MIT 6.006 terms, a set without the order operations is called
- a sequence
- a dictionary
- a stack
- a queue
- According to MDN, why can a plain object be risky as a dictionary for keys that come from data?
- Objects cannot hold strings
- Its prototype brings default keys that may collide with yours
- Objects are always slower than arrays
- Objects forget values after a second
- Choose by the operations you will do most often.
- Sequence: array, linked list, stack, queue. Set: hash table, BST.
- For 1,023 keys: linear search up to 1,023 comparisons, binary search and a balanced tree up to 10.
- Map is the usual dictionary in JavaScript; use a balanced tree when you also need order.
Sources for this course (5)
- 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).
Checked: 2026-10-18