Data Structures Reference

This page is a quick reference / cheat sheet, not a lesson — keep it open while you solve problems or cram for an exam. Below is a summary of the data structures the course covers with the related session, followed by a master operation-cost table that drills into every operation, the matching Python built-in, and each structure’s common pitfall.

Session Summary Table

Data structure	Key idea	Headline complexity	Session
Array / List	Contiguous storage, index access	access O(1) · insert-middle O(n)	1.4
String	Sequence of characters, a kind of array	access O(1)	1.4
Linked List	Nodes joined by pointers, flexible insert/delete	insert/delete O(1) at a known node · search O(n)	2.1
Stack	Last-in-first-out (LIFO) — undo, recursion	push/pop O(1)	2.1
Queue	First-in-first-out (FIFO) — task scheduling	enqueue/dequeue O(1)	2.1
Hash Table / Dictionary	Key–value pairs, fast retrieval, the workhorse of real software	get/set average O(1)	2.2
Binary Tree	Hierarchy, each node has ≤ 2 children	depends on height	2.3
Binary Search Tree	Left < node < right	search O(log n) when balanced	2.3
Graph	Models relationships between nodes	depends on nodes and edges	3.3

Choosing one? See Choosing the Right Data Structure.

---

Master Operation-Cost Table

Notation: n = number of elements · times are worst-case unless marked average.

Structure	Access (index)	Search	Insert	Delete	Space
Array (fixed-size)	O(1)	O(n)	not supported (fixed size)	not supported	O(n)
Dynamic array	O(1)	O(n)	end: O(1) average · middle: O(n)	end: O(1) · middle: O(n)	O(n)
Singly linked list	O(n)	O(n)	head: O(1) · known node: O(1)	head: O(1) · known node: O(1)	O(n)
Doubly linked list	O(n)	O(n)	head/tail: O(1) · known node: O(1)	head/tail: O(1) · known node: O(1)	O(n)
Stack	O(n)*	O(n)*	push O(1)	pop O(1)	O(n)
Queue	O(n)*	O(n)*	enqueue O(1)	dequeue O(1)	O(n)
Deque	O(n)*	O(n)*	either end O(1)	either end O(1)	O(n)
Hash table	no index	average O(1) · worst O(n)	average O(1) · worst O(n)	average O(1) · worst O(n)	O(n)
Binary search tree (BST)	—	O(h), worst O(n)	O(h), worst O(n)	O(h), worst O(n)	O(n)
Balanced BST (AVL / Red-Black)	—	O(log n)	O(log n)	O(log n)	O(n)
Binary heap	min/max O(1)	O(n)	O(log n)	pop root O(log n)	O(n)

* Stacks/queues/deques usually aren’t designed for search or middle-access — if you find yourself needing that often, you picked the wrong structure.

Why dynamic arrays are “amortized O(1)”: most appends are O(1) because there’s spare capacity. When the buffer fills exactly, it must allocate a new, larger block (typically double the size) and copy everything over — that one call is O(n), but it happens rarely. Averaged over all appends, the cost per append is still O(1).

---

Per-Structure Detail

Array / Dynamic Array

Use when: you need frequent index access, the size is roughly known upfront, or you want cache locality (sequential reads are much faster than a linked list’s scattered nodes). Avoid when: you insert/delete in the middle of large collections often.

• Python built-in: list (already a dynamic array)
• Common pitfall: list.insert(0, x) or list.pop(0) are O(n) because every element must shift — if you need frequent operations at the front, use collections.deque instead of list.

Linked List (Singly / Doubly)

Use when: you insert/delete often at the head, or at a node you already hold a pointer to (e.g. implementing your own queue/stack, an LRU cache). Avoid when: you need frequent access to the k-th element — there’s no shortcut, you must walk node by node.

• Python built-in: no direct built-in — collections.deque uses a doubly linked list internally and covers most use cases.
• Common pitfall: forgetting to update tail/prev pointers when inserting or deleting at the ends, silently breaking the list or creating an infinite loop.

Stack

Use when: you need to reverse the most-recent-first order (undo, bracket matching, backtracking, the recursion call stack). Avoid when: you need to access anything other than the top element.

• Python built-in: list (append/pop at the end are O(1))
• Common pitfall: using list.pop(0) instead of list.pop() without noticing — silently turning an O(1) stack operation into O(n).

Queue and Deque

Use when: you must process items in arrival order (BFS, task scheduling, streaming data). Avoid when: you need LIFO (use a stack) or don’t care about order at all (a plain list is enough).

• Python built-in: collections.deque — popleft()/appendleft() are genuinely O(1), unlike list.
• Common pitfall: using list as a queue via pop(0) — correct results, but O(n) per dequeue. As n grows, the program crawls with no obvious cause.

Hash Table / Dictionary

Use when: you need the fastest possible search/insert/delete by key and don’t care about ordering (frequency counting, caches, key → value indexes). Avoid when: you need a stable sort order (Python’s dict preserves insertion order since 3.7, but that’s not the same as sorted order) or need range queries (use a BST instead).

• Python built-in: dict, set
• Common pitfall: using a mutable object (like a list) as a key — dicts require keys whose hash never changes; and overlooking the O(n) worst case under heavy collisions (a hash-flooding risk if keys come straight from untrusted user input).

Binary Search Tree (BST) and Balanced BST

Use when: you need both fast search and to preserve order (in-order traversal yields sorted data), range queries, or the next min/max. Avoid when: you only need key lookup and don’t care about order — a hash table is faster and simpler.

• Python built-in: no BST in the standard library — use sortedcontainers.SortedList (third-party) or the bisect module with a sorted list for simple range queries.
• Common pitfall: forgetting to balance the tree — inserting already-sorted data into a plain BST degenerates it into a linked list (height O(n)), making every operation O(n) when it was meant to be O(log n).

Binary Heap / Priority Queue

Use when: you repeatedly need the smallest/largest value fast (priority queues, Dijkstra, heap sort, top-k). Avoid when: you need to search for an arbitrary element — heaps don’t support general search in O(log n).

• Python built-in: heapq (min-heap only — build a max-heap by negating values)
• Common pitfall: assuming heapq.heappop() returns items in insertion order (it doesn’t — it always returns the smallest); and forgetting a heap isn’t fully sorted — only the root is guaranteed to be the minimum.

---

Python Built-in Cheat Sheet

Need…	Use	Not
Dynamic array	list	—
Stack	list (append/pop)	collections.deque works too, but list is enough
Queue / Deque	collections.deque	list (pop(0) is slow)
Key–value pairs	dict	—
Unique set	set	list with manual in checks (much slower)
Priority queue	heapq	re-sorting a list every time
Sorted data + fast search	bisect + list or sortedcontainers.SortedList	hand-rolled BST (unless you’re practicing)

Golden rule: before hand-rolling a data structure in Python, check collections, heapq, and bisect first — most of what you need is already there and well optimized.

---

Going Deeper

• MIT 6.006 — Introduction to Algorithms — systematic coverage of the data structure foundations
• Stanford CS161 — ties data structures tightly to complexity analysis
• Harvard CS50 — visual, beginner-friendly explanations
• CLRS (Cormen, Leiserson, Rivest, Stein) Introduction to Algorithms 4th ed. — the standard reference, with dedicated chapters on heaps (ch. 6), hash tables (ch. 11), BSTs (ch. 12), and red-black trees (ch. 13)
• Sedgewick & Wayne Algorithms 4th ed. — real implementations of every structure in this table, plus a detailed treatment of dynamic array amortized cost
• Weiss Data Structures and Algorithm Analysis — especially strong on hashing (multiple collision-resolution strategies) and balanced trees
• Goodrich, Tamassia & Goldwasser Data Structures and Algorithms in Python — uses Python directly, so it maps one-to-one onto the built-ins in this table
• Big-O Cheat Sheet (bigocheatsheet.com) — a similar complexity comparison table, good for cross-checking

Choosing one? See Choosing the Right Data Structure.