Core Data Structures Tour

Why a tour first

Every algorithm pattern you'll learn is really "the right data structure, moved the right way." This lesson is a fast tour of the structures that appear in interviews, what each is uniquely good at, and what each costs. Skim the table now, then read the notes; come back to the table whenever you need a refresher.

Arrays and dynamic arrays

An array is a row of numbered boxes in one contiguous block of memory. Knowing an index means jumping straight to that box — that O(1) access is the whole superpower. The price: inserting in the middle forces everything after it to shuffle over, which is O(n).

A dynamic array (Python list, JavaScript array, Java ArrayList) is an array that grows itself: when full, it allocates a block about twice the size and copies everything over. The rare copies average out, so appending at the end is amortized O(1) — occasional spikes, constant on average.

Strings

A string is an array of characters, but in most languages it's immutable: "changing" one character secretly builds a whole new string. The classic trap is concatenating in a loop — each += recopies everything built so far, turning an innocent-looking loop quadratic. Build the pieces in a list and join once at the end.

Hash maps and hash sets

A hash map stores key–value pairs; a hash set stores just keys. A hash function converts any key into a slot number, so insert, lookup, and delete are all O(1) on average, regardless of size. When two keys land in the same slot (a collision), they chain together in a small list — rare enough that the average stays constant, though the worst case is O(n).

This is the single most-used interview structure. Whenever a brute-force inner loop is merely asking "have I seen this before?" or "how many of these so far?", a hash map deletes that loop. Two caveats: entries have no reliable ordering, and the O(1) costs O(n) memory.

Stacks

A stack is a pile of plates: you add and remove only at the top — Last In, First Out (LIFO). It fits any situation where the most recent unfinished thing is the next thing to deal with: matching brackets, undo history, and the function call stack itself. Push, pop, and peek are all O(1).

Queues and deques

A queue is a checkout line: first come, first served (FIFO). This fairness is the heart of breadth-first search. A deque (double-ended queue, pronounced "deck") opens both ends, with O(1) push and pop at either side.

One trap: popping from the front of a plain dynamic array is O(n), because everything shifts left. If you need front removal, use a real deque (collections.deque in Python).

Linked lists

A linked list is a treasure hunt: each node holds a value and a pointer to the next node. There are no indexes — reaching item 500 costs 500 hops. In exchange, splicing a node in or out at a known position is one pointer rewrite, O(1), with no shifting. A doubly linked list adds a back-pointer, letting you remove a node given only that node — the trick behind LRU caches.

Trees and binary search trees

A binary tree gives every node up to two children. Nearly everything about trees is recursion: a tree is a root plus two smaller trees, so you solve for the children and combine.

A binary search tree (BST) adds a filing rule: smaller values live in the left subtree, larger in the right. Each comparison discards half the tree, so search and insert are O(log n) — when balanced. Insert already-sorted data without rebalancing and the tree collapses into a chain, degrading to O(n). Library ordered maps (like Java's TreeMap) self-balance to keep the O(log n) guarantee.

Heaps

A heap (priority queue) is a complete binary tree, stored flat in an array, with one rule: every parent beats its children — smaller, in a min-heap. It promises only that the champion sits at the root: peek at the best in O(1), pop it or push a new item in O(log n). It is not for searching — finding an arbitrary element is O(n). Reach for it whenever a problem says "repeatedly take the best" or "top k."

Tries

A trie (prefix tree) is a tree of characters where each root-to-node path spells a prefix, so words sharing a beginning share a path. Checking "does anything start with pre-" costs three steps whether the dictionary holds ten words or ten million — O(L) in the query's length, independent of dictionary size. It powers autocomplete and any problem with "prefix" in it.

Graphs

A graph is nodes plus connections — the most general structure. The standard representation is an adjacency list: for each node, the list of nodes it connects to, like everyone keeping their own contact list instead of a giant everyone-by-everyone spreadsheet (the adjacency matrix). For the sparse graphs interviews use, the list wins: O(V + E) space versus the matrix's O(V^2), and iterating a node's neighbors costs only as many steps as it has neighbors. Step one of most graph problems: convert the given edge list into an adjacency list.

How to use this tour

You don't memorize this table by staring at it — it sticks by use. The modules ahead each take one or two of these structures and drill the movement patterns built on them. When a problem stumps you, come back and scan the superpower column: one of these rows almost always fits.