Data structures

Choose how to store your data by the operations you need to make cheap. Start with arrays and linked lists, then build toward trees, graphs, and range queries.

The ideas here work across languages. Python examples make the algorithms readable; they are not the definition of each structure.

Start with the operation

You store arriving jobs. If you always take the oldest job, you need a queue. If you always take the most urgent job, you need a priority queue. The same data needs different organization.

An interface says what you can do: add a job, inspect the next job, remove it. An implementation says how values are stored. A queue can use a circular array or linked nodes. A priority queue can use a heap or a balanced search tree.

Question                 Interface          Possible representation
oldest job?              queue              circular array
most urgent job?         priority queue     binary heap
job with this ID?        map                hash table

A structure's invariant is a rule that every operation preserves. A heap keeps each parent no greater than its children. That rule makes its root a minimum, even though the whole collection is not sorted.

Read in this order

Read the diagrams and operation traces first. Open the implementation and exercise answers when you want more detail.

Sets, maps, and sequences

A set stores distinct items: adding the same item twice still leaves one copy. A multiset, or bag, also records how many copies exist. A map associates a unique key with a value, such as a job ID with its deadline. A sequence stores items by position and can contain duplicates.

“Hash” and “tree” describe implementations. A hash set and a tree-based ordered set both support membership; the ordered set also supports sorted traversal and neighboring keys. The same distinction applies to hash maps and ordered maps. Bitsets use a bit per possible integer item.

Compare costs fairly

Let n be the number of stored items. O(1) means work bounded independently of n. O(log n) grows slowly: doubling n adds roughly one step in a halving search. O(n) grows in proportion to n.

Amortized cost spreads expensive operations over a sequence. A dynamic array occasionally copies everything, but n appends still take O(n) total work. Expected cost depends on assumptions about randomness or how keys spread across buckets. Neither means every individual operation is cheap.

Unless stated otherwise, costs assume fixed-size values, constant-time comparisons, and constant-time arithmetic. Hashing or comparing a long string can take time proportional to its length. Memory figures include the stored structure, not just temporary variables.

For mostly static ordered data, a sorted array is often enough. Binary search takes O(log n); insertion still takes O(n). Python's list plus bisect supports this approach. Its standard library does not provide a general balanced ordered map or set.

Combine structures when operations conflict

An LRU cache finds entries by key and evicts the least recently used entry. A hash map finds nodes; a doubly linked list tracks recent use. On a hit, move the node to the most-recent end.

Insertion order and access order differ. Python's dict preserves insertion order, but reading a key does not move it. Some library containers support explicit reordering. The required invariant stays the same: each map entry refers to exactly one live list node.

Try this design question: support adding, deleting, and choosing a uniformly random item. An array gives random indexing; a hash map stores each item's index. Delete by moving the last item into the gap and updating its map entry. This sacrifices order.

Apply that combination in Insert Delete GetRandom O(1). Use patterns when you want to see how structures support complete problem-solving techniques.