Data Structures

Course Map

This page puts every chapter of the course on one map. Each chapter is a node, and an arrow shows which idea from an earlier topic the next one relies on. Read it before the course starts to see where the topics are heading, or during the course to see where you are.

Figure 1: The course map. Each arrow points from a topic to one that builds on it. Starting from arrays, the path branches into linked structures, trees, and graphs.

Figure 1 draws only the most direct connections. Table 1 lists every chapter that each chapter depends on, together with the idea that links them.

Table 1: Connections on the map.
Topic (chapter)	Builds on	Connection
Introduction (1)	—	How data is represented in memory, primitive and reference types, abstract data types: the vocabulary in which every structure is described.
Algorithm Analysis (2)	Introduction	Choosing a structure means measuring what its operations cost: Big O, Omega, and Theta.
Arrays (3)	Algorithm Analysis	The first structure: contiguous memory with O(1) access by index; analysis shows what insertion and deletion cost.
Recursion (4)	Algorithm Analysis, Arrays	Reducing a problem to smaller instances of itself, analyzed through the call stack and recurrence relations.
Linked Lists (5)	Arrays	Nodes remove the fixed size and shifting cost of arrays: O(1) insertion at the front, but no random access.
The List ADT and Java Collections (6)	Arrays, Linked Lists	Arrays and linked lists are two implementations of the same List ADT; Java collections and Iterator.
Stacks (7)	Arrays, Linked Lists	A list accessed only at the top: push and pop are O(1) with either an array or a linked list.
Queues and Deques (8)	Arrays, Linked Lists, Stacks	Access at both ends: a circular array or a linked list; a queue built from two stacks.
Trees (9)	Recursion, Linked Lists	A node can now link to several children; traversals are written recursively.
Search Trees (10)	Trees	An ordering condition makes search, insertion, and deletion O(h); balancing keeps the height O(log n).
Priority Queues and Heaps (11)	Queues and Deques, Trees	A priority version of the Queue ADT; a heap stores a complete binary tree in an array.
Maps and Hash Tables (12)	Arrays, The List ADT and Java Collections	The Map ADT; a hash table of array buckets and chaining lists gives O(1) on average.
Sets and Disjoint Sets (13)	Search Trees, Maps and Hash Tables	A set is a map without values: hash-based and tree-based implementations; disjoint sets as trees.
Graphs (14)	Queues and Deques, Trees, Priority Queues and Heaps, Sets and Disjoint Sets	A generalization of trees: BFS uses a queue, Dijkstra and Prim a priority queue, Kruskal disjoint sets.

The backbone of the map is analysis → array → linked structure → tree → graph. The first four chapters supply the tools for the whole course: every structure is defined as an abstract data type, and its operations are measured with Big O. Arrays and linked lists are the two basic ways of implementing everything that follows; stacks, queues, and the List ADT are built on top of them. Recursion leads to trees, and search trees and hash tables are the two ways of implementing maps and sets. The final chapter, on graphs, uses all of it: queues and stacks for traversal, priority queues, and disjoint sets.