Open Data Structures (in Java)

About this Book

Open Data Structures by Prof. Pat Morin (Carleton University) is an internationally celebrated open-access textbook. It covers the design and mathematical analysis of fundamental data structures with strict efficiency proofs. The book starts with array-based lists, circular buffers, and dynamically resizing vectors that power modern language runtimes. It investigates linked lists, skip lists, and randomized binary search trees (Treaps) that achieve O(log n) expected performance. Hash tables are covered thoroughly, comparing chained hashing with open-addressing and modern linear probing algorithms. Heaps and priority queues, including binary heaps and Meldable heaps, are presented with complete correctness proofs. It explores sorting algorithms such as Quicksort, Mergesort, and Radix Sort, analyzing comparison bounds and cache behavior. B-Trees, external memory algorithms, and secondary storage indexing techniques are detailed for database engineers. Every data structure includes rigorous space-time complexity analysis alongside clean Java implementations. Essential reading for systems architects, backend developers, and students wanting mathematical rigor in data structures.