AlgoScope

Data Structures

The containers themselves: how each one is laid out, and which operation that layout makes cheap.

62 topics39 lessons12 families

A data structure is a layout decision plus the operations that layout makes cheap. An array puts values side by side, so any index is one address calculation. A linked list scatters them and joins them with pointers, so an insert is two writes instead of a shift. Nothing about the values themselves changes; only where they sit.

Every structure here buys one operation by giving up another. A hash table says whether a key is present in expected O(1) but cannot tell you the next largest key. A balanced search tree answers that in O(log n) but pays for a rotation on the way back up. A heap hands you the smallest element in O(1) and will not say a word about the second smallest without more work.

So the question is never which structure is best, but which operations you run a million times and which you run once. Read the cost line on each page as a profile: the operations marked O(1) are what the structure was built for, and the O(n) ones are the price it charges for them.

After this you can

  • Read a structure by its cost line and say which operation it was built for
  • Choose between an array, a linked list, a hash table and a search tree for a given access pattern
  • Explain why a hash table lookup is expected O(1) and what its worst case costs
  • Say what keeping a search tree balanced buys, and what it charges per insert
  • Recognise when a structure is a plain array underneath, as a heap and a hash table both are
501142234856i

Move 8 from index 4 to index 5.

Open in the player →or start at step 2

In this order

  1. ArrayNumbered slots side by side, so reaching any one of them costs the same.
  2. Dynamic ArrayAn array that doubles its capacity when full, so appends are amortized O(1).
  3. Singly Linked ListEach node points at the next. To reach the tenth you walk the first nine.
  4. Doubly Linked ListEach node points to both neighbours, so a node can be unlinked in O(1) given only the node, as the LRU cache's moves rely on.
  5. StackOnly the top is reachable. The last thing down is the first thing up.
  6. QueueYou join at the back and leave from the front, like a queue at a counter.
  7. DequeInsert and remove at both ends in O(1).
  8. Hash FunctionTurns a key into a slot number. Here it is key mod capacity, weak on purpose so collisions show.
  9. Hash TableTurns a key into a slot number so lookup does not have to search.
  10. Hash MapA hash table storing key-value pairs; the key picks the bucket and the value travels with it.
  11. Binary TreeEach node has at most two children. Every tree lesson here builds on this shape.
  12. Binary Search TreeSmaller values sit left, larger sit right, so a search walks one path down.
  13. AVL TreeA search tree that rotates itself back into balance whenever two sides differ in height by two.
  14. Binary HeapA complete tree where every parent outranks its children, stored in a plain array.
  15. Priority QueueAlways hands back the highest-priority item, usually by keeping a binary heap underneath.
  16. TrieA tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.
  17. GraphVertices joined by edges; the model for networks, maps and dependencies.
  18. Adjacency ListFor each vertex, a list of its neighbours; compact for sparse graphs.
  19. Disjoint Set UnionA parent array where following pointers leads to a root that names the set; union links two roots.
  20. Segment TreeA binary tree whose leaves are the array and whose every parent summarises its two children.

Also in this category

Graph Representations

Linear Structures

Graph Structures

Hash Tables and Collision Handling

Heaps

Range Structures

Caches and Filters

Balanced Search Trees

Linked Lists

String Structures

Where people go wrong

Expected is not guaranteed

A hash table is O(1) expected, which assumes keys spread across the buckets. With a poor hash function or a nearly full table, every operation walks a chain and the worst case is O(n). Structures with a log n bound have no such assumption.

A search tree is only log n if something keeps it balanced

Insert sorted keys into a plain binary search tree and you get a linked list with extra pointers, height n and searches to match. Sorted input is not a rare case, and AVL and red-black trees exist because of it.

Counting the pointers

A linked node carries a pointer per link, which for small values can double the memory, and it puts the values anywhere in the heap. A traversal then misses cache lines that an array walk of the same data would have hit.

Or a different category

Array Algorithms and Techniques

The container is already an array and the question is how to move through it.

Complexity Analysis

You have chosen the structure and need to reason about what the whole program costs.

Lessons that teach these