Open Data Structures PDF Download – Pat Morin (Java Edition) BSCS

BSCS students can download the complete data structures textbook “Open Data Structures” by Pat Morin, free as a PDF in its Java edition. It is one of the few widely-assigned data structures books written as an open-source project from the start — the LaTeX source, the Java/C++/pseudocode implementations, and the build scripts are all maintained publicly on GitHub, which is exactly what lets it stay current instead of freezing the way most free textbooks do once their author stops updating them.

The book is denser and more formal than an introductory programming text: every data structure comes with a running-time table, a correctness argument, and a set of proof-style exercises, not just working code. That makes it a natural second-course book — it assumes you can already read and write code comfortably and takes you into the analysis (worst-case, amortized, and expected running time) that a Data Structures course is actually meant to teach.

Book Overview

Course	Data Structures
Degree Programs	BSCS
Level	University — second course, after Programming Fundamentals
Edition	Edition 0.1G — a living, continuously-updated text
Author	Pat Morin
Structure	14 chapters, one data-structure family per chapter
Exercises	171 across the book, counted from the source, many proof-style
Language Editions	Complete in Java and pseudocode; the C++ edition is beta (the book’s own repository calls it “still under development”)
Language	English
License	CC BY 2.5 Canada — Model: Link-only
Format	Free PDF (Java, C++, and pseudocode editions), source on GitHub

Chapter List

Chapter 1: Introduction

Difficulty: Easy · Key topics: interface vs. implementation, the List/USet/SSet interfaces, the word-RAM model, worst-case vs. amortized vs. expected time

The chapter opens with a concrete argument for why efficiency matters: a data set of a million items, searched a million times with a naive O(n) scan, costs roughly sixteen minutes even on a fast processor — and real applications are far bigger. It then draws the line the rest of the book depends on: an interface defines what operations a structure supports and what they mean, while an implementation defines how those operations actually work, so the same interface can have many different implementations. Three interfaces recur throughout — List, USet (an unordered set) and SSet (a sorted set) — and the chapter defines the word-RAM model of computation that every running-time claim in the book is measured against.

Key Points:

• Interface = what a structure does; implementation = how. Chapters 2 and 3 both implement the same List interface in different ways.
• The three core interfaces used throughout the book: List (an indexed sequence), USet (an unordered set with no duplicates), and SSet (a sorted set supporting ordered queries).
• Running times are measured in the w-bit word-RAM model, where a data set of size n satisfies n ≤ 2^w and basic operations on one word of memory take O(1) time.
• The book always states which kind of bound a running time is: worst-case (every run), amortized (averaged over a sequence of operations), or expected (averaged over random choices the structure makes).

Practice Tip: Before reading Chapter 2, implement the List interface yourself using a plain array, with no optimizations. Feeling why add(0,x) is slow on a plain array is what makes the six array-based structures in the next chapter click.

Common Mistake: Treating “expected O(log n)” (a randomized guarantee, as in Chapters 4 and 7) as the same promise as “worst-case O(log n)” (a deterministic guarantee, as in Chapter 9). They are different strengths of claim, and the book is precise about which one each structure makes.

Important Questions:

• What is the difference between an interface and an implementation? An interface specifies the operations a structure supports and their meaning; an implementation supplies the internal representation and the algorithms that carry those operations out. One interface can have many implementations.
• Why does the book distinguish worst-case, amortized, and expected running time instead of giving one number per operation? Because these are different guarantees: worst-case holds on every single call, amortized holds only when averaged over a long sequence of calls, and expected holds only when averaged over the structure’s own random choices — conflating them overstates what a structure actually promises.

Chapter 2: Array-Based Lists

Difficulty: Medium · Key topics: ArrayStack, FastArrayStack, ArrayQueue, ArrayDeque, DualArrayDeque, RootishArrayStack, amortized doubling

This chapter implements the List and Queue interfaces on top of a single backing array, and studies six variations in turn. ArrayStack gets O(1) access but O(n) insertion/removal in the middle. ArrayQueue and ArrayDeque use the array as a circular buffer so that additions and removals near either end cost O(1) amortized instead of shifting the whole array. DualArrayDeque builds a deque from two stacks glued back to back. RootishArrayStack is the odd one out: it stores data in a series of growing arrays rather than one contiguous block, cutting wasted space from O(n) down to O(√n) while keeping O(1) access.

Key Points:

• get(i)/set(i,x) is O(1) for every structure in this chapter — the backing array gives direct indexing.
• add(i,x)/remove(i) costs O(1+n−i) for ArrayStack and RootishArrayStack, and the cheaper O(1+min{i,n−i}) for ArrayDeque and DualArrayDeque, since both ends are fast.
• All of these bounds are amortized: any single call can trigger a resize, but the cost averages out over a long sequence of calls.
• The resizing rule is always “grow or shrink by doubling/halving,” never by a fixed increment — that is what turns resizing from an O(n)-per-call cost into O(1) amortized.
• RootishArrayStack trades a slightly more complex index calculation for O(√n) wasted space instead of the O(n) a single over-allocated array can waste.

Practice Tip: Implement grow() and shrink() for an ArrayStack yourself and print the backing array’s length after every operation. Watching exactly when reallocation fires is what makes “amortized O(1)” stop being an abstract phrase.

Common Mistake: Growing the backing array by a fixed amount (say, 10 slots) instead of doubling it. That single change quietly turns amortized O(1) add(x) back into O(n) per call, because the array is reallocated roughly every 10 insertions instead of exponentially less often.

Important Questions:

• Why is add(i,x) not O(1) even though get(i) is? Inserting in the middle of a backing array requires shifting every element after position i by one slot, which costs O(n−i) in the worst case regardless of how fast indexing itself is.
• After remove(i) on an ArrayStack, the backing array still holds n+1 non-null values even though the list now has only n elements — where did the extra value go? The last surviving copy of the removed element (or whatever was shifted into its old slot) is left behind at the end of the backing array, past the list’s logical size, until it is overwritten or garbage-collected.

Chapter 3: Linked Lists

Difficulty: Medium · Key topics: SLList, DLList, SEList, singly vs. doubly linked, space-efficient lists

This chapter implements the same List interface using pointer-based nodes instead of an array. SLList, a singly-linked list, gives O(1) Stack and FIFO Queue operations but cannot support fast access to an arbitrary index. DLList, doubly-linked, adds a back-pointer to every node so Deque operations (adding/removing at either end) run in O(1) too. SEList is the chapter’s most interesting structure: it groups several elements into each node, like a hybrid between a linked list and an array, trading a little array-style shifting inside each block for far fewer pointers to follow overall.

Key Points:

• SLList supports push(x)/pop() and FIFO add(x)/remove() in O(1), but has no fast way to reach an arbitrary index.
• DLList supports get(i)/set(i,x)/add(i,x)/remove(i) in O(1+min{i,n−i}) — it walks from whichever end is closer.
• SEList packs b elements per node, cutting per-element pointer overhead roughly by a factor of b compared to DLList.
• The core trade-off versus Chapter 2’s arrays: linked structures lose O(1) random access but gain O(1) insertion/removal once you already hold a reference to the right node.

Practice Tip: Draw the pointer diagram, before and after, for every add/remove you trace by hand. Almost every real bug in a linked-list implementation is a forgotten or misdirected pointer at exactly one of these boundary steps.

Common Mistake: Updating only one neighbour’s pointer when removing a node from a DLList — for example fixing prev.next but forgetting next.prev. The list looks correct when traversed forward and silently breaks when traversed backward.

Important Questions:

• Why can’t a dummy header node eliminate all the special cases in an SLList? A dummy node fixes the empty-list case, but SLList still needs separate tracking of the tail for O(1) FIFO add(x), since a singly-linked list has no way to reach the node before the tail in O(1) once it needs updating.
• Why does get(i) on a DLList cost O(min{i,n−i}) rather than simply O(i)? Because the list is doubly-linked, the traversal can start from whichever end — head or tail — is closer to index i, so the cost is bounded by the shorter of the two walks.

Chapter 4: Skiplists

Difficulty: Hard · Key topics: SkiplistList, SkiplistSSet, randomized height, coin-toss construction, expected O(log n)

Skiplists solve the same problem balanced trees solve — O(log n) search — using randomization instead of rebalancing rules. Every node is given a random height using simulated coin tosses, and a taller node participates in more “express lane” levels that let a search skip over many elements at once. SkiplistList uses this structure to give O(log n) expected time for get(i)/add(i,x)/remove(i) — a real improvement over Chapter 3’s linked lists for random access. SkiplistSSet uses the same idea to implement a sorted set with O(log n) expected find/add/remove.

Key Points:

• A skiplist has no rebalancing step at all — height is assigned once, randomly, when a node is created, and never changed afterward.
• Both SkiplistList and SkiplistSSet achieve O(log n) expected time for their core operations, and the skiplist’s height is O(log n) with high probability.
• Search works top-down: start at the tallest level, move right as far as possible without overshooting, then drop one level and repeat.
• SkiplistList supports fast random access to an unordered sequence by indexed position — something a plain sorted structure like SkiplistSSet does not need.

Practice Tip: Trace a find(x) search by hand on a small drawn skiplist before writing any code — move right at the top level until you’d overshoot, drop a level, repeat. That single procedure is the entire algorithm; the code is just this trace with pointers.

Common Mistake: Assuming a skiplist’s height is bounded the way a balanced tree’s is. It is not — an unlucky run of coin tosses can (in principle, with vanishing probability) produce an arbitrarily tall skiplist. The O(log n) bound is a statement about the expectation, not a hard guarantee for every possible run.

Important Questions:

• What determines the height assigned to a new node when it is added to a skiplist? A sequence of simulated coin tosses: the node’s height increases by one level for each consecutive “heads,” giving taller nodes exponentially decreasing probability, so on average only a small fraction of nodes reach any given level.
• Why is a skiplist’s O(log n) time described as “expected” rather than “worst-case”? Because it depends on the random heights actually distributing the way the coin-toss model predicts; an adversarial or extremely unlucky sequence of random choices could (with tiny probability) produce a slower structure, which worst-case bounds by definition must rule out entirely.

Chapter 5: Hash Tables

Difficulty: Hard · Key topics: ChainedHashTable, LinearHashTable, hash codes, multiplicative hashing, load factor

Hash tables store a small number n of items drawn from a much larger universe of possible keys, using an integer hash code to decide roughly where each item lives in an array of size proportional to n. The chapter covers two implementations: ChainedHashTable, where each array slot holds a small list of the items that hashed there, and LinearHashTable, where a collision is resolved by scanning forward to the next open slot instead of using a separate list. Both resize themselves — growing or shrinking the backing array — to keep the ratio of items to slots (the load factor) roughly constant, which is what keeps operations fast as the table grows. The second half of the chapter explains how to turn an arbitrary object into the integer hash code either method needs.

Key Points:

• Both ChainedHashTable and LinearHashTable give O(1) expected/amortized find(x) and add(x)/remove(x).
• ChainedHashTable resolves collisions with a small list per bucket; LinearHashTable resolves them by probing forward through the array itself.
• A hash table must be resized as n grows — keeping too many items per slot degrades every operation from O(1) toward O(n).
• A hash code maps an arbitrary object to an integer; multiplicative hashing then maps that integer down into the table’s actual index range.

Practice Tip: Implement the resize step for a ChainedHashTable and deliberately disable it, then insert far more items than the initial table size. Watching every bucket’s chain grow long — and find(x) slow to O(n) — is what makes “you must resize to keep O(1)” concrete rather than a rule to memorise.

Common Mistake: Reusing a fixed, easily-guessable multiplier in a multiplicative hash function. The book notes this can be deliberately attacked — an adversary who knows the multiplier can choose keys that all collide, degrading every operation to O(n) regardless of how good the hash table’s code is otherwise.

Important Questions:

• What is the practical difference between hashing with chaining and linear probing? Chaining keeps a separate list per slot, so a “full” slot just grows a list; linear probing keeps everything in the one backing array and resolves a collision by scanning forward to the next empty slot, which avoids extra list-node overhead but is more sensitive to a high load factor.
• Why is find/add/remove only O(1) expected rather than worst-case for a hash table? The bound depends on the hash function spreading keys roughly evenly across the table; a bad hash function or an adversarial set of keys can, in the worst case, send every item to the same slot, and no hash table can rule that out with certainty for arbitrary input.

Chapter 6: Binary Trees

Difficulty: Medium · Key topics: BinaryTree, BinarySearchTree, root/parent/child, tree traversal, unbalanced height

This chapter introduces the binary tree formally: a connected, acyclic graph in which no node has more than two children, rooted at a distinguished node r. It defines BinaryTree, the base structure every tree in the rest of the book builds on, along with the standard vocabulary — parent, child, subtree, height, depth — and the traversal orders (preorder, inorder, postorder) used to visit every node. BinarySearchTree then adds the ordering property that makes search possible: every node’s left subtree holds smaller keys and its right subtree holds larger ones, giving O(h) find/add/remove, where h is the tree’s height — a bound that is only useful once later chapters show how to keep h at O(log n).

Key Points:

• A binary tree is rooted, with every node having at most two children, called its left and right child.
• BinarySearchTree gives O(h) find(x)/add(x)/remove(x), where h is the current height of the tree.
• An unbalanced BST built from already-sorted input degenerates toward a straight line, making h as bad as O(n) — the exact problem Chapters 7–9 each solve differently.
• Preorder, inorder and postorder traversal differ only in when a node is visited relative to its children — inorder traversal of a BST visits keys in sorted order.

Practice Tip: Implement recursive preorder, inorder and postorder traversal by hand before moving on. Every self-balancing tree in Chapters 7–9 reuses this same traversal logic on top of a more complex insert/remove.

Common Mistake: Assuming any BinarySearchTree is automatically balanced. It is not — inserting already-sorted data into a plain BST with no rebalancing produces a structure that behaves like a linked list, with O(n) find/add/remove instead of the O(log n) a balanced tree would give.

Important Questions:

• Why does a plain BinarySearchTree‘s running time depend on its height rather than a fixed bound like O(log n)? Because nothing in the basic structure prevents the tree from becoming lopsided; height is only guaranteed to be O(log n) when a chapter’s specific balancing technique (randomization, partial rebuilding, or colour invariants) is actually applied.
• What is the relationship between a binary tree’s height and the number of nodes it contains? A tree with n nodes has height at least ⌈log(n+1)⌉−1 (the best case, fully balanced) and at most n−1 (the worst case, a straight chain) — the whole point of Chapters 7–9 is forcing the tree closer to the first bound.

Chapter 7: Random Binary Search Trees (Treaps)

Difficulty: Hard · Key topics: Treap, random priority, heap-order plus BST-order, expected O(log n) height

This is the first of three chapters presenting a different way to keep a binary search tree balanced; a course only needs to cover one of the three unless the syllabus specifically compares them. A Treap assigns every node a random numeric priority when it is created, then maintains two properties simultaneously: BST order on the keys, and heap order on the priorities (every node’s priority is smaller than its children’s). The result behaves, in expectation, exactly like a binary search tree built by inserting the keys in a uniformly random order — even if the actual insertion order is adversarial — because the random priorities effectively re-randomize the shape. Rotations restore the heap-order property after an insertion or deletion changes it.

Key Points:

• A Treap combines BST order (on keys) with heap order (on independently-chosen random priorities).
• find(x)/add(x)/remove(x) all run in O(log n) expected time — the randomization comes from the priorities, not from the order keys are inserted in.
• A Treap behaves like a randomly-built BST regardless of insertion order, which is exactly what defeats an adversary who knows the algorithm and chooses input order to try to unbalance it.
• Rotations (the same left/right rotation operations used in Chapters 8 and 9) restore heap order after every insert and remove.

Practice Tip: Implement rotateLeft/rotateRight as two small standalone functions before touching Treap‘s insert logic — Scapegoat Trees and Red-Black Trees, the next two chapters, both reuse the identical rotation code.

Common Mistake: Reusing the same priority value, or assigning priorities in a predictable (non-random) order. Doing either breaks the guarantee entirely — the whole expected-O(log n) argument depends on every node’s priority being an independent random draw.

Important Questions:

• Why does giving each node a random priority make a Treap behave like a randomly-built BST, even for adversarial insertion order? Because the tree’s shape is determined entirely by the relative order of the priorities, not by the order keys were inserted, and since priorities are drawn independently and uniformly at random, the resulting shape has exactly the same distribution as a BST built from a random insertion order.
• What operation restores the heap-order property after a key is added to or removed from a Treap? A sequence of rotations, applied until the newly-inserted (or newly-exposed) node’s priority is correctly ordered relative to its parent and children.

Chapter 8: Scapegoat Trees

Difficulty: Hard · Key topics: ScapegoatTree, partial rebuilding, weight balance, amortized O(log n)

A ScapegoatTree takes a completely different approach to balance: instead of randomization or continuous small adjustments, it lets the tree drift out of balance and then, when an insertion makes some subtree too lopsided, rebuilds only that subtree — the “scapegoat” — into a perfectly balanced one. Rebuilding walks the unbalanced subtree into a sorted array, then recursively picks the middle element as the new local root, which is the simplest way to build a perfectly balanced BST from sorted data. Because a node only gets caught up in a rebuild occasionally, the expensive O(subtree size) rebuild cost averages out to O(log n) amortized over a long sequence of insertions, even though find(x) is worst-case O(log n) at every single call.

Key Points:

• find(x) is worst-case O(log n) at all times, because a Scapegoat Tree is always weight-balanced enough to bound its height logarithmically between rebuilds.
• add(x)/remove(x) are O(log n) amortized — the occasional expensive rebuild is paid for by many cheap operations in between.
• A rebuild only touches the specific unbalanced subtree (the “scapegoat”), never the whole tree — that locality is what keeps the amortized cost low.
• Rebuilding a subtree into a balanced one is simple and reusable: sort its nodes into an array, then recursively make the middle element the root.

Practice Tip: Implement the array-to-balanced-subtree rebuild as one standalone function first. It never changes regardless of which node triggers it, so getting it right once means every rebuild in the tree already works.

Common Mistake: Rebuilding the entire tree on every insertion instead of only the unbalanced subtree. That defeats the entire point of “partial” rebuilding and turns an amortized O(log n) structure into an O(n)-per-insert one.

Important Questions:

• How does a Scapegoat Tree decide which node needs to be rebuilt after an insertion? It walks back up from the newly-inserted node looking for the first ancestor whose subtree has become too unbalanced by the tree’s weight criterion — that ancestor is the scapegoat, and only its subtree is rebuilt.
• Why is find(x) worst-case O(log n) while add(x) is only amortized O(log n)? The weight-balance invariant guarantees the tree’s height never exceeds O(log n) at any moment, which bounds every single find; but achieving that guarantee occasionally requires an expensive rebuild, and only averaging that cost over many insertions makes add‘s bound hold.

Chapter 9: Red-Black Trees

Difficulty: Hard · Key topics: 2-4 trees, simulated 2-4 tree, red/black colouring, worst-case O(log n), rotations

Red-Black Trees are the third and most widely used self-balancing BST in the book — they appear as the primary search structure in the Java Collections Framework, several C++ Standard Template Library implementations, and inside the Linux kernel. The chapter builds them by first explaining 2-4 trees, a structure where each node holds one, two, or three keys, and then showing how a Red-Black Tree simulates a 2-4 tree using ordinary binary nodes, coloured red or black, where a red node represents a key still merged into its black parent’s 2-4 node. This gives a tree with height at most 2 log n, worst-case O(log n) add/remove, and — unlike a Scapegoat Tree’s amortized rebuilds — only a constant number of rotations amortized per operation.

Key Points:

• A Red-Black Tree simulates a 2-4 tree using binary nodes coloured red (merged into parent) or black (a real 2-4 node boundary).
• Height is at most 2 log n, and find(x)/add(x)/remove(x) are all worst-case O(log n) — a stronger guarantee than Scapegoat’s amortized bound.
• The amortized number of rotations per add(x)/remove(x) is constant, even though the worst case for a single operation can require O(log n) colour flips.
• Used in production inside the Java Collections Framework, several C++ STL implementations, and the Linux kernel — one of the most deployed data structures in this entire book.

Practice Tip: For any Red-Black Tree you trace by hand, draw the corresponding 2-4 tree alongside it. The colour-flip and rotation rules stop looking arbitrary once you can see them as a 2-4 node splitting or merging.

Common Mistake: Treating Red-Black rebalancing as a list of rotation cases to memorise rather than as maintaining one invariant — every root-to-leaf path passes through the same number of black nodes. Losing sight of that invariant makes the rotation cases look like arbitrary special-casing instead of one consistent rule.

Important Questions:

• What guarantee does a Red-Black Tree give that a plain, unbalanced BinarySearchTree from Chapter 6 does not? A worst-case height bound of 2 log n, guaranteeing O(log n) find/add/remove on every single call, regardless of insertion order — a plain BST gives no such guarantee and can degrade to O(n).
• Why are Red-Black Trees preferred over some other balanced trees in real-world library implementations? Because they guarantee worst-case O(log n) operations (stronger than Scapegoat’s amortized bound) while needing only a constant amortized number of rotations per operation, making them fast in practice as well as provably efficient.

Chapter 10: Heaps

Difficulty: Medium · Key topics: BinaryHeap, MeldableHeap, implicit array-based tree, priority queue, meld

This chapter covers two implementations of the priority queue — a structure that always gives up its smallest (or largest) element first, unlike the FIFO Queue from Chapter 3. BinaryHeap stores a complete binary tree implicitly inside a single array, using index arithmetic instead of pointers to find a node’s parent and children, which makes it extremely fast and memory-efficient; it is the structure behind heap-sort in the next chapter. MeldableHeap takes a different, pointer-based approach specifically to support meld(h) — absorbing an entire second priority queue in one operation — something the array-based BinaryHeap cannot do efficiently.

Key Points:

• BinaryHeap represents a complete binary tree implicitly in an array — no node pointers are stored at all.
• A node at array index i has children at 2i+1 and 2i+2, and parent at (i−1)/2 — every BinaryHeap operation is built from these three formulas.
• add(x)/remove() on a BinaryHeap run in O(log n); a heap only guarantees a parent is smaller (or larger) than its children, not full sorted order.
• MeldableHeap supports meld(h) — merging two whole priority queues — which a plain array-based BinaryHeap has no efficient way to do.

Practice Tip: Implement the three index formulas for BinaryHeap yourself and trace them on paper for a 7-element heap before writing add/remove. Every heap operation is just those three formulas plus “swap upward” or “swap downward” until order is restored.

Common Mistake: Assuming a heap is a sorted structure, the way a binary search tree is. It is not — a heap only guarantees each parent is ordered relative to its own children, so reading a BinaryHeap‘s array left to right, or doing an inorder traversal, does not produce sorted output.

Important Questions:

• What index arithmetic locates a node’s children and parent in an implicit BinaryHeap? For a node stored at array index i, its children are at 2i+1 and 2i+2, and its parent is at (i−1)/2 (integer division) — no pointers are needed.
• Why can’t BinaryHeap support an efficient meld(h) operation, while MeldableHeap can? BinaryHeap‘s array layout requires the tree to stay “complete” (filled left to right with no gaps), so combining two such arrays requires re-inserting every element; MeldableHeap‘s pointer-based structure has no such shape constraint and can splice two trees together directly.

Chapter 11: Sorting Algorithms

Difficulty: Medium · Key topics: merge-sort, quicksort, heap-sort, the O(n log n) comparison lower bound, counting sort, radix sort

The chapter is here because two of its algorithms are directly built on structures from earlier chapters — quicksort mirrors the random binary search tree from Chapter 7, and heap-sort is BinaryHeap from Chapter 10 used as a sorting engine. It covers three comparison-based algorithms that each run in O(n log n) time, and proves that no comparison-based algorithm can do better — any algorithm restricted to comparing elements must make roughly n log n comparisons in the worst and even the average case. The second half moves past that limit by sorting integers without comparisons at all: counting sort and radix sort achieve O(n) by using the values themselves as array indices instead of comparing pairs of elements.

Key Points:

• Merge-sort, quicksort, and heap-sort each run in O(n log n) time, and are proven asymptotically optimal for comparison-based sorting.
• No algorithm that sorts using only comparisons can beat roughly n log n comparisons in the worst case or the average case — this is a proven lower bound, not just an observation about these three algorithms.
• Quicksort’s expected running time analysis mirrors Chapter 7’s Treap; heap-sort is literally BinaryHeap‘s add/remove used repeatedly.
• Counting sort and radix sort sort n integers in O(n) time by using the integer values as array indices, sidestepping the comparison lower bound entirely — but only for integer (or integer-key) data.

Practice Tip: Implement merge-sort operating directly on a DLList (Chapter 3) without copying into an auxiliary array — a real exercise from the book. It forces you to reason about pointer splicing instead of array indexing, which is a different, useful skill from the textbook-standard array version.

Common Mistake: Assuming counting sort or radix sort can simply replace comparison-based sorting in general. They cannot — both require the keys to be integers (or reducible to integers) within a bounded, known range; neither works on arbitrary comparable objects the way merge-sort or quicksort do.

Important Questions:

• Why can no comparison-based sorting algorithm beat O(n log n) in the worst case? Sorting n distinct elements requires distinguishing between n! possible orderings, and each comparison can rule out at most half the remaining possibilities, so at least log₂(n!) ≈ n log n comparisons are needed in the worst case — a limit no comparison-based algorithm can get around.
• How are quicksort and heap-sort each connected to a data structure from earlier in the book? Quicksort’s expected O(n log n) analysis is the same argument used for the random binary search tree (Treap, Chapter 7); heap-sort is BinaryHeap (Chapter 10) used as the sorting engine — repeatedly removing the minimum.

Chapter 12: Graphs

Difficulty: Medium · Key topics: AdjacencyMatrix, AdjacencyLists, directed graph, path, cycle, traversal

This chapter studies two ways of representing a directed graph G=(V,E), where E is a set of ordered pairs of vertices, and the traversal algorithms that use each representation. AdjacencyMatrix stores an n×n grid marking which edges exist, giving instant O(1) lookup of whether a specific edge exists, at the cost of O(n²) space regardless of how many edges the graph actually has. AdjacencyLists stores, for each vertex, a list of only its actual neighbours, using space proportional to the number of edges rather than the square of the number of vertices, at the cost of a slower “does this specific edge exist” check. The chapter defines the vocabulary — path, simple path, cycle, reachability — used by every graph algorithm in the book.

Key Points:

• A directed graph is a pair G=(V,E); an edge (i,j) is directed from source i to target j.
• AdjacencyMatrix gives O(1) “is there an edge (i,j)” queries but always uses O(n²) space, whatever the actual number of edges.
• AdjacencyLists uses O(n+m) space (where m is the number of edges) and gives O(1+deg(i)) traversal of a vertex’s neighbours.
• A path is simple if all its vertices are distinct; a cycle is a path whose last edge returns to its starting vertex.

Practice Tip: Implement both representations for the same small graph and time an “is there an edge (i,j)” query against a “list all of vertex i’s neighbours” query on each. The space/speed trade-off between the two representations stops being abstract once you can see it on one concrete example.

Common Mistake: Defaulting to AdjacencyMatrix for a large, sparse graph (one with far fewer than n² edges). The O(n²) space cost becomes impractical once n reaches even a few thousand vertices with relatively few edges, where AdjacencyLists stays efficient.

Important Questions:

• When is an adjacency matrix more space-efficient than an adjacency list, and when is it less? A matrix is competitive (or better) for a dense graph, where the number of edges m approaches n²; for a sparse graph, where m is much smaller than n², an adjacency list’s O(n+m) space is far smaller than the matrix’s fixed O(n²).
• What makes a path “simple” rather than just any path? A path is simple if every vertex on it is visited at most once; a general path is allowed to revisit vertices (and, if it does and returns to its start, becomes a cycle).

Chapter 13: Data Structures for Integers

Difficulty: Hard · Key topics: BinaryTrie, XFastTrie, YFastTrie, w-bit integers, digital search

This chapter returns to the SSet interface, but with a key restriction that turns out to be a huge advantage: every element is assumed to be a w-bit integer rather than an arbitrary comparable object. BinaryTrie, the simplest of the three, is a digital search tree that walks a key’s bits one at a time, giving O(w) time — not obviously impressive on its own, since w ≥ log n always. XFastTrie adds a hash table at every level of the trie, cutting search to O(log w) expected time by binary-searching over the levels instead of walking them one by one. YFastTrie combines an XFastTrie with a forest of small BinaryTries to bring add/remove down to O(log w) expected as well, not just find.

Key Points:

• All three structures assume keys are w-bit integers, and every running-time bound here is stated in terms of w, not n.
• BinaryTrie: O(w) find/add/remove, by walking the key’s bits one at a time.
• XFastTrie: O(log w) expected find, by hashing at each trie level to binary-search over levels instead of scanning them.
• YFastTrie: O(log w) expected for find, add and remove, by pairing an XFastTrie with a forest of small backing BinaryTries.

Practice Tip: Trace a BinaryTrie search for a small 4-bit key by hand before reading further. Both XFastTrie and YFastTrie are exactly this same bit-walking structure with a hash table layered on top, so the base case has to be completely solid first.

Common Mistake: Assuming O(log w) automatically beats the O(log n) bounds from Chapters 7–9. It does not in general — w is a fixed word size (32 or 64 on real hardware), so for a small or moderate n, a plain O(log n) balanced tree can easily be faster in practice than the extra hashing overhead these structures carry.

Important Questions:

• Why does a BinaryTrie‘s running time depend on w (the word size) rather than n (the number of elements stored)? Because the search walks the key’s bits one at a time, from the most significant bit to the least, so the number of steps is fixed by how many bits the key has — regardless of how many other elements are in the structure.
• What does XFastTrie add to a plain BinaryTrie to speed up find(x) from O(w) to O(log w)? A hash table at every level of the trie, which lets a search binary-search directly over the w levels for the deepest level containing a prefix match, instead of walking down one bit at a time.

Chapter 14: External Memory Searching

Difficulty: Medium · Key topics: Block Store, B-Trees, external memory model, disk/SSD access time, O(log_B n)

Every structure so far assumes the whole data set fits in RAM, where the word-RAM model from Chapter 1 applies. This chapter drops that assumption: when a data set is too large for memory and must live on external storage, a single access becomes drastically slower — the book quotes roughly 19ms for a hard-disk access and 0.3ms for a solid-state drive, both enormous compared to a RAM access. The BlockStore abstraction reads and writes one fixed-size block of B keys at a time, and the B-Tree built on top of it is a multi-way search tree whose branching factor is chosen to match B, giving height O(log_B n) instead of O(log n) — so a search touches only O(log_B n) slow external accesses rather than O(log n) individual elements.

Key Points:

• External storage access is vastly slower than RAM — the book’s own measurements: roughly 19ms for a hard disk, 0.3ms for an SSD, versus nanosecond-scale RAM access.
• BlockStore reads and writes one block of B keys at a time, matching how real disks and SSDs actually transfer data.
• A B-Tree‘s branching factor is tied to B, giving height O(log_B n) — far shorter than a binary tree’s O(log n) once B is in the thousands.
• find/add/remove cost O(log_B n) block accesses — the metric that actually matters when each access is a slow disk operation.

Practice Tip: Implement the BlockStore abstraction first — a simple read-one-block/write-one-block interface — before touching the B-Tree logic itself. Once that boundary exists, the B-Tree is just a multi-way search tree layered cleanly on top of it.

Common Mistake: Applying a Red-Black Tree or Scapegoat Tree (Chapters 8–9) directly to disk-resident data. Each node access becomes a separate slow disk read in a binary tree, while a B-Tree deliberately packs many keys into each block so a single disk read accomplishes far more useful comparison work.

Important Questions:

• Why does a B-Tree’s branching factor matter so much specifically for data stored on disk? Because each block access is enormously slow compared to RAM, so minimising the number of block accesses (by making each block hold many keys, i.e. a high branching factor) matters far more than minimising in-memory comparisons within a block.
• What is the practical gap in access time between RAM, an SSD, and a hard disk that motivates this whole chapter? The book’s own figures put a hard-disk access at roughly 19ms and an SSD access at roughly 0.3ms, both many orders of magnitude slower than RAM access — a gap large enough that minimising the count of external accesses dominates every other consideration.

---

Download Open Data Structures PDF (Free)

This book is free from its official source. Click below to open the author’s own site and download the complete Java edition PDF — the pseudocode and beta C++ editions are also available there if your course needs a different language.

↓ Download PDF

---

How to Study This Book

Read Chapters 1 through 3 in order first — they are the foundation everything else builds on. Chapter 1 defines the interfaces (List, USet, SSet) and the word-RAM model that every later running-time claim is measured against; Chapters 2 and 3 give you the array-based and pointer-based ways of building a List, and the amortized-analysis habit of mind you will need for almost every chapter after this one.

Chapters 4 (Skiplists) and 5 (Hash Tables) each build directly on Chapters 1–3 and can be read in either order — they solve different problems (ordered access vs. unordered lookup) and don’t depend on each other.

Chapters 7, 8 and 9 — Treaps, Scapegoat Trees and Red-Black Trees — are three different, competing answers to the same question Chapter 6 leaves open: how do you keep a binary search tree’s height at O(log n)? Most Data Structures courses only require one of the three; check your syllabus before assuming you need to read all three cover to cover. If you do read more than one, Treap (Chapter 7) is the gentlest introduction since it reuses randomization the way Chapter 4 already did, and Red-Black Trees (Chapter 9) is the one most worth knowing well since it is the one actually used inside Java’s, C++’s and Linux’s own libraries.

Read Chapter 10 (Heaps) before Chapter 11 (Sorting) if your course covers heap-sort, and read Chapter 7 (Treaps) before Chapter 11 if it covers quicksort’s expected-time analysis — Chapter 11 assumes both connections and does not re-explain them. Chapter 12 (Graphs) is mostly self-contained and only needs Chapter 1’s definitions.

Chapter 13 (Data Structures for Integers) assumes Chapter 5’s hashing is already comfortable — XFastTrie and YFastTrie are both built by adding a hash table on top of the BinaryTrie from earlier in the same chapter. Chapter 14 (External Memory Searching / B-Trees) assumes Chapter 6’s binary search tree vocabulary, applied to a very different cost model.

Two honesty notes. First, this is a proof-driven book: many exercises ask you to prove a bound or illustrate a sequence of operations on paper, not just write code. If your course is purely implementation-focused, read the discussion prose for the guarantees and treat the pure-proof exercises as optional unless assigned. Second, the C++ edition of this book is explicitly marked beta and incomplete by the author’s own repository — this page links the Java edition because it is the complete one; use the pseudocode edition if your course is language-agnostic, or the C++ edition only if your instructor specifically requires it and you’re prepared for gaps.

---

Used In These Programs

This book is used for the Data Structures course in: BS Computer Science. Browse all Data Structures books or all Computer Science books.

Who Should Read This

Open Data Structures is written for a student who has already finished a first programming course and is comfortable reading code, not for someone learning to program for the first time — it moves quickly into formal running-time analysis and proof-style exercises that assume that comfort. It suits a second-year BSCS student taking Data Structures, and it suits a student preparing for a follow-on Algorithms course, since Chapters 7, 9, 10 and 11 build the exact vocabulary (randomization, amortized analysis, balanced trees, sorting lower bounds) that course will assume. It is a stronger fit for a course that wants formal analysis alongside working code than for one that wants a gentle, example-driven walkthrough; students who want the latter first might prefer to pair this book with lecture notes that build intuition before working through the proofs here.

---

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

FAQs

Related Books

• Problem Solving with Algorithms and Data Structures using Python
• Data Structures in C++ – Aikman Series BSCS
• Think Python – Allen B. Downey (3rd Edition)

Open Data Structures is the most rigorously proof-driven free book in this collection, and one of the very few maintained as an open-source project rather than a fixed PDF — which is exactly why it hasn’t gone stale the way most free textbooks eventually do. Browse more Computer Science books for the rest of your semester.

Open Data Structures, Edition 0.1G (Java), by Pat Morin. Free under the Creative Commons Attribution 2.5 Canada licence. Official source: https://opendatastructures.org/