Open Data Structures: An Introduction

Citation

Morin, P. (2013). Open Data Structures: An Introduction. AU Press. Free official edition: https://opendatastructures.org/

Chapter Summary

Chapter 1: Introduction

The opening chapter explains why efficiency matters, using a rough calculation in which a million searches over a million unsorted items would take far too long, and then defines the interfaces used for the rest of the book: Queue, Stack and Deque, List, USet (unordered set) and SSet (sorted set). It reviews the mathematics needed (logarithms, factorials, asymptotic notation, and randomization with expectation and indicator variables), fixes the w-bit word-RAM model of computation, and distinguishes worst-case, amortized and expected running times with an analogy of paying a mortgage versus buying a house outright and buying fire insurance. It also explains that the Java code is simplified (no public or private) and gives summary tables of every structure in the book.

Chapter 2: Array-Based Lists

This chapter implements List and Queue on top of a backing array. It starts with ArrayStack and its amortized analysis of growing and shrinking, then gives an optimized version using bulk array copies, a circular ArrayQueue, an ArrayDeque that supports fast operations at both ends, and a DualArrayDeque built from two stacks that are rebalanced when one runs low. It ends with the RootishArrayStack, which wastes only about √n space by storing elements in blocks of increasing size, including a discussion of computing square roots.

Chapter 3: Linked Lists

Linked lists trade constant-time indexing for constant-time insertion and removal next to a known node. The chapter implements a singly-linked list (for stack and queue operations), a doubly-linked list with a dummy node, and an SEList, a space-efficient list that stores small blocks in each node, with an amortized analysis of how blocks are spread and gathered.

Chapter 4: Skiplists

Skiplists use random coin tosses to build a hierarchy of linked lists. The chapter implements an SSet with O(log n) expected time per operation and a SkiplistList that supports indexed access, then analyses expected search-path length and space.

Chapter 5: Hash Tables

The first part implements hashing with chaining, using multiplicative hashing, and linear probing, with an analysis of linear probing and an introduction to tabulation hashing. The second part explains how to build hash codes for primitive types, compound objects, arrays and strings. The author notes that the "random" constants in the code were generated from atmospheric noise.

Chapter 6: Binary Trees

After defining binary-tree terminology, the chapter writes recursive and non-recursive traversals and an unbalanced BinarySearchTree with searching, addition and removal. The closing discussion previews three ways to obtain O(log n) behaviour in the next chapters: randomization, amortization and worst-case balancing.

Chapter 7: Random Binary Search Trees

The chapter first proves that a binary search tree built from a random permutation has expected search paths of logarithmic length, then uses that result to design the Treap, which assigns random priorities to keep the tree random under insertion and deletion.

Chapter 8: Scapegoat Trees

Scapegoat trees stay balanced by occasionally rebuilding an entire subtree into a perfectly balanced one. The chapter implements the rebuild and proves O(log n) amortized cost for updates while searches run in O(log n) worst-case time.

Chapter 9: Red-Black Trees

This is the most technical chapter. It first presents 2-4 trees, then implements red-black trees as a simulation of them, using a left-leaning variant, and works through addition and removal case by case. It explains why red-black trees are used in libraries such as the Java Collections Framework: logarithmic height, worst-case O(log n) updates and an amortized constant number of rotations.

Chapter 10: Heaps

Two priority queues are developed: the BinaryHeap, which stores a complete binary tree in an array using Eytzinger's layout, and the MeldableHeap, a randomized heap whose merge operation also supports melding two heaps.

Chapter 11: Sorting Algorithms

The chapter covers merge-sort, quicksort and heap-sort, proves the lower bound for comparison-based sorting, and then presents counting sort and radix sort for integers, linking quicksort to random search trees and heap-sort to the BinaryHeap.

Chapter 12: Graphs

Graphs are represented by an adjacency matrix and by adjacency lists, with a comparison of their costs, followed by breadth-first and depth-first search, including a non-recursive depth-first search.

Chapter 13: Data Structures for Integers

Returning to the SSet problem for w-bit integer keys, the chapter builds the BinaryTrie (O(w) operations), the XFastTrie, which uses hashing to search in O(log w) time, and the YFastTrie, which combines an XFastTrie sample with ordinary SSets to achieve O(log w) expected time for all operations.

Chapter 14: External Memory Searching

The final chapter drops the assumption that all data fits in memory. Using measured access times for RAM, a solid-state drive and a hard disk to motivate the external-memory model, it introduces a block store and implements B-trees with searching, addition, removal and an amortized analysis of splits and merges.

Key Concepts

Chapter 1: Introduction

• Interface versus implementation: an interface (List, USet, SSet) says what operations exist; a data structure is one way to implement them.
• Amortized versus expected time: amortized bounds average the cost over a sequence of operations, while expected bounds average over the structure's own random choices.
• Word-RAM model: a model in which basic operations on w-bit words take constant time, with w at least log n.

Chapters 2–3: Array-Based Lists and Linked Lists

• Backing array with resizing: doubling and halving the array keeps the amortized cost of add and remove constant at the end.
• Circular array: using indices modulo the array length so a queue or deque can grow at either end.
• Space-efficient structures: RootishArrayStack and SEList reduce wasted space to about √n or a small fraction of n.

Chapter 4: Skiplists

• Randomized levels: each element is promoted to the next list with probability one half, giving logarithmic expected search paths.

Chapter 5: Hash Tables

• Hashing with chaining: each array slot holds a list of the elements that hash to it.
• Linear probing: elements are stored directly in the array, and collisions are resolved by scanning forward to the next free slot.
• Hash codes: functions that turn arbitrary objects into integers, combined so that equal objects get equal codes.

Chapters 6–9: Binary Search Trees

• Binary search tree property: every node's value is larger than those in its left subtree and smaller than those in its right subtree.
• Treap: a search tree that is also a heap on random priorities, which keeps its shape random.
• Partial rebuilding: rebuilding an unbalanced subtree from scratch, the idea behind scapegoat trees.
• Red-black tree as a 2-4 tree: colouring nodes so that a binary tree encodes a 2-4 tree, guaranteeing height at most 2 log n.

Chapters 10–11: Heaps and Sorting

• Implicit binary tree: storing a complete binary tree in an array so that parent and child positions are computed arithmetically.
• Comparison lower bound: any comparison-based sort needs roughly n log n comparisons in the worst and average case.

Chapters 12–14: Graphs, Integers and External Memory

• Adjacency lists: a graph representation that stores, for each vertex, the list of its out-neighbours.
• Trie over binary keys: a tree whose root-to-leaf paths spell out the bits of integer keys.
• B-tree: a balanced search tree with large nodes sized to a disk block, minimizing the number of block reads.

Critical Analysis

Strengths

• Interface, implementation and proof together. Each structure is introduced against one of a small set of interfaces, implemented in full, and analysed with a stated theorem; most sections end with a short summary of running times. The tables in Section 1.7 let readers compare all the structures at a glance.
• Coverage beyond the usual first course. Alongside lists, hash tables, search trees and heaps, the book treats skiplists, treaps, scapegoat trees, meldable heaps, X-fast and Y-fast tries and B-trees, so it shows several ways (randomization, amortization, worst-case balancing) to reach the same bounds.
• Careful treatment of the three kinds of guarantees. The distinction between worst-case, amortized and expected time is set up in Chapter 1 with concrete analogies and then reused throughout, which helps students understand why, for instance, red-black trees are preferred in libraries despite their complexity.
• Open and adaptable. The preface explains that the book is run like an open-source project: the LaTeX and Java sources are on GitHub under a Creative Commons Attribution licence, and Java, C++ and pseudocode editions are available. Each chapter's discussion section gives historical background and references.

Limitations

• Mathematically demanding for a first course. Proofs use probability, indicator variables and amortized arguments from early on (Chapter 4 onwards), and Chapter 9's red-black tree removal is long. Students without discrete mathematics may struggle.
• Code simplified rather than idiomatic. The Java samples deliberately omit access modifiers and class hierarchies; readers must go to the accompanying source for complete implementations, and the book does not teach how to use library collections.
• Graphs and algorithms are brief. Chapter 12 covers only representations, breadth-first and depth-first search; shortest paths, minimum spanning trees and other graph algorithms are left out, as are balanced trees such as AVL trees (mentioned only in the discussion).
• Dated edition details. The edition read (0.1G) is from the early 2010s, and some examples, such as the 32-bit JVM word size and disk timings, reflect that period. No exercise solutions are provided.

Where It Fits in the Course

Among the data-structures books in this course, Morin sits between the gentle illustrated books (Bhargava's Grokking Algorithms and Wengrow's A Common-Sense Guide to Data Structures and Algorithms) and the specialist texts (Okasaki's Purely Functional Data Structures and Brass's Advanced Data Structures). Students who find formal analysis unfamiliar can start with one of the illustrated books, which are generally described as building intuition with little mathematics, and then move to Morin for proofs and complete implementations.

Goodrich, Tamassia and Goldwasser's Data Structures and Algorithms in Java covers similar ground; it is generally described as a broader, conventional textbook with more on Java programming and algorithms, so it can serve as the main course book with Morin as a free, more analytical companion, or the other way round. After Morin, Brass is the natural next step for students interested in more advanced search structures, and Okasaki for those who want to see how the same ideas look in a purely functional setting.

How to Use This Book

The book suits second-year computer science students who have completed one programming course and some discrete mathematics; Chapter 1 reviews the probability and asymptotic notation used later. Java familiarity helps but is not essential, since the code is written in a simplified style readable by anyone who knows a C-like language.

For a one-semester course, the core is Chapter 1, Chapter 2 (at least ArrayStack, ArrayDeque and DualArrayDeque), Chapter 3 (singly- and doubly-linked lists), Chapter 5, Chapter 6, either Chapter 7 or Chapter 8 for balancing, Chapter 10 and Chapter 11. Chapter 4 on skiplists is a good introduction to randomized analysis. Chapter 9 can be read at the level of the 2-4 tree correspondence, with the full deletion cases optional. Chapters 12–14 suit a longer course or self-study.

Work some of the exercises at the end of each chapter (there are well over 150 in total); many ask you to implement or modify a structure, and the downloadable source code lets you test your versions against the book's. Read the discussion sections for the history of each idea and pointers to further reading.

Edition and Sources

This guide is based on Open Data Structures (in Java), Edition 0.1G, read in the free PDF (ods-java.pdf) from the author's official site, https://opendatastructures.org/; the print edition was published by AU Press in 2013. It draws on the acknowledgments, the "Why This Book?" preface, the full table of contents, Chapter 1 in full (Sections 1.1–1.8), and for Chapters 2–14 the chapter introductions, every section heading, the summaries and running-time tables, and the "Discussion and Exercises" sections.