Introduction to Data Structures

A quick primer on Big-O

Big-O describes how an operation's running time grows as the amount of data (n) grows. It ignores fixed multipliers and smaller extra terms, and only looks at the overall shape of the curve.

An operation is one action on the data, such as adding an item or searching for one. Its running time is counted in steps. For example, an operation that takes 5n + 20 steps is still O(n): when n is large, doubling n roughly doubles the work, and the 5 and the 20 don't change that shape.

Where the numbers come from: log n (here log base 2) is how many times you can halve n before you reach 1. 1,000,000 can be halved about 20 times (2²⁰ = 1,048,576), so O(log n) is about 20 steps, and O(n log n) is 1,000,000 × 20 = 20,000,000. O(n²) is 1,000,000 × 1,000,000.

The Log scale button squeezes big numbers so each grid line is 10 times the one below it, letting all five curves fit on one chart.

Suggested learning order

Start with the linear structures, because the tree builds on the same ideas. The hash table stands alone and can be read at any time.

1. Stack (LIFO)

A stack only lets you add or remove at the top: the last item in is the first item out.

Think of a pile of plates. You put a new plate on top, and you take a plate off the top. You never pull one from the middle. That one rule, Last In, First Out, makes a stack simple and fast.

How it works

The stack is a Python list where the end of the list is the top. append() and pop() at the end of a list are both O(1): nothing else has to move. Using the front of the list as the top would be a mistake, because pop(0) shifts every other element, which costs O(n).

Where it shows up

• The call stack: every function call pushes a frame, and every return pops one.
• Undo in editors.
• Matching brackets and parsing expressions.
• Depth-first search of trees and graphs.

2. Queue (FIFO)

A queue adds at the back and removes from the front: the first item in is the first item out.

Picture a line at a shop. People join at the back and leave from the front, in the order they arrived. This version hides a neat trick inside: it is built from two stacks, _in and _out.

How it works: the two-stack trick

A plain list would make dequeue O(n), because list.pop(0) shifts every element. Instead:

• _in: new items are pushed here.
• _out: items are popped from here.

When _out is empty, every item in _in is moved over to _out. Moving them reverses their order, so the oldest item ends up on top of _out.

Where it shows up

• Print queues and task schedulers.
• Message brokers.
• Breadth-first search, e.g. the BST's level-order walk.

3. Singly Linked List (chain of nodes)

A linked list is a chain of nodes: each node holds a value and a pointer to the next node.

A pointer (also called a reference) tells you where another item is stored in the computer's memory, like a home address. Following a node's pointer takes you to the next node.

An array keeps its items side by side in one block of memory, numbered 0, 1, 2, …; a Python list works this way. A linked list is different: its items can live anywhere in memory. The list only remembers where the chain starts (head); the last node's next is None, Python's value for "nothing here". Think of a treasure hunt: each clue tells you where the next one is, so to reach clue 5 you must follow clues 1 to 4.

Reading the boxes: ● means next points at the neighbouring box (follow the arrow), ∅ means next is None, and →20 (orange) means it points at the node holding 20, which is not drawn next to it. Pointer variables like cur and prev are shown as labels above the nodes.

Arrays vs linked lists

How it works: key techniques

• insert(index, value): walk to the node before the position, then change pointers: cur.next = Node(value, cur.next). The new node grabs the old next first, so nothing is lost.
• remove(value): keep track of prev so you can bypass the removed node: prev.next = cur.next. If there is no prev, the node is the head, so head moves instead.
• reverse(): the classic interview question. Walk the list once and flip each pointer backwards with cur.next, prev, cur = prev, cur, cur.next.

Where it shows up

• The building block for stacks and queues when you want guaranteed O(1) at the front.
• Chains of entries in hash table buckets (separate chaining, see Hash Table).
• Immutable lists in functional languages (Lisp, Haskell): prepending shares the rest of the list.
• Interview questions: reverse a list, detect a cycle, find the middle node.

4. Binary Search Tree (BST)

A binary tree where everything in a node's left subtree is smaller and everything in its right subtree is larger, so, when the tree is well balanced, each comparison discards about half of what's left.

Each node has at most two children, and the BST property holds at every node. That makes searching like looking up a word in a paper dictionary: open it in the middle, see whether the word comes before or after, and ignore the other half. At each node you compare once and continue in only one direction. Think of a "guess the number" game where each answer is "higher" or "lower".

How it works

• contains(key): start at the root. Go left if the key is smaller, right if it's larger. Stop when you find it or fall off the tree (None).
• insert(key): search for the key, then attach a new node exactly where the search fell off. Duplicates are ignored.
• delete(key) has three cases:
  1. Leaf: just remove it.
  2. One child: replace the node with its only child (the whole subtree moves up).
  3. Two children: find the in-order successor (the smallest key in the right subtree: go right once, then left as far as possible), copy its key into this node, then delete the successor from the right subtree. The successor never has a left child, so that second delete is always case 1 or 2.

Traversals

Complexity

Where it shows up

• Ordered maps and sets (e.g. C++ std::map, Java TreeMap, which are red-black trees).
• Database indexes (B-trees are a wide, balanced generalization of the BST).
• Range queries and "next larger key" lookups, which a hash table can't do efficiently.

5. Hash Table (key → value, separate chaining)

A hash table stores pairs: a key (the name you look something up by, such as a word) and a value (what you want to find, such as how often the word appears). It keeps a row of numbered slots called buckets and turns each key into a bucket number, so a lookup takes O(1) on average.

Python's dict (key → value pairs, like {'apple': 3}) and set (a collection with no repeats) are both hash tables.

The idea

1. A hash function is a fixed recipe that turns any key into a whole number: hash("apple"). The same key always gives the same number.
2. Divide that number by the number of buckets and keep the remainder. This is called modulo, written % in Python: for example 13 % 8 = 5. With 8 buckets the remainder is always 0 to 7, so it always picks a valid bucket: hash(key) % len(buckets).
3. The (key, value) pair is stored in that bucket. To find it again, recompute the same bucket and look only there.

Think of a coat check with numbered hooks: the attendant computes the hook number from your ticket, so they go straight to it instead of searching every coat.

Collisions and separate chaining

Two different keys can land in the same bucket. This is called a collision. In the demo above, 'date' and 'fig' both land in bucket 3, and the default key 'mango' lands in bucket 7 next to 'apple'. This implementation uses separate chaining: each bucket is a small Python list of pairs, and get / put / delete scan that list comparing k == key. Rows with a collision get an orange left border and a "collision ×N" badge.

Load factor and resizing

The load factor is items / buckets. As it grows, chains get longer and lookups slow down. When it goes above 0.75, _resize() doubles the number of buckets and re-inserts every pair, because each key's bucket index (hash % capacity) changes when the capacity changes. Try it: starting from 5 items in 8 buckets, the 7th item pushes the load to 7/8 = 0.875 and triggers a resize to 16.

Rules for keys

Keys must be hashable, and equal keys must have equal hashes. That's why you can't use a list as a dict key: it can change after insertion, which would change its hash and strand it in the wrong bucket. Note that 1 and '1' are different keys here (an int and a string).

Complexity

Where it shows up

• Python's dict and set, and object attribute lookup
• Caches and memoization (an LRU cache is a hash table plus a doubly linked list)
• Counting and de-duplicating things (word frequencies, "have I seen this before?")
• Database hash indexes, compiler symbol tables, routing tables

Choosing the right structure

The real skill is matching a problem to a structure. For each scenario, pick the structure you'd reach for, then reveal the answer.

Quick reference

Complexity cheat sheet

Click a column header to sort, or filter to one operation to compare structures side by side.

* amortized   † average case  ·  dot color = growth class (same colors as the Big-O chart)

Final quiz & certificate

This is the last step of the course: one list of 10 questions covering every lesson. After each answer you'll see the correct option and why it's right. Score 80% or more (8 of 10) to earn a certificate with your name.