Pat Morin · Edition 0.1G

Open Data Structures (in Java)

Pat Morin’s textbook on data structures, with Java implementations, time and space analysis, proofs, examples and exercises. Its fourteen chapters cover lists, hash tables, search trees, heaps, sorting, graphs and external-memory searching.

Read the complete PDFCumulative LaTeXComplete source ZIP

Complete English book: Edition 0.1G, 334 pages. The PDF contains a linked contents page and index. The LaTeX and source ZIP provide the editable text, code and figures.

Before you start

Bring basic programming experience with arrays, loops, methods, classes, references and recursion. The implementations use Java. Chapter 1 introduces asymptotic notation, probability and the computation model.

B10 — Discrete Mathematics supplies preparation in reasoning and proof. B80 — Mathematical Computing supplies programming and reproducible-experiment practice in Python and SageMath; it is not an introductory Java course.

Follow the author’s chapter order; Section 1.7 explains the chapter dependencies. This book supplies a data-structures foundation, not a complete general algorithms course.

Chapters and exercises

  1. Chapter 1

    Introduction

    Exercises

  2. Chapter 2

    Array-Based Lists

    Exercises

  3. Chapter 3

    Linked Lists

    Exercises

  4. Chapter 4

    Skiplists

    Exercises

  5. Chapter 5

    Hash Tables

    Exercises

  6. Chapter 6

    Binary Trees

    Exercises

  7. Chapter 7

    Random Binary Search Trees

    Exercises

  8. Chapter 8

    Scapegoat Trees

    Exercises

  9. Chapter 9

    Red-Black Trees

    Exercises

  10. Chapter 10

    Heaps

    Exercises

  11. Chapter 11

    Sorting Algorithms

    Exercises

  12. Chapter 12

    Graphs

    Exercises

  13. Chapter 13

    Data Structures for Integers

    Exercises

  14. Chapter 14

    External Memory Searching

    Exercises

For educators

Each chapter has discussion and exercises. Combine reading the arguments with implementing operations, testing boundary cases and comparing measured performance with the complexity bounds. The author’s Java code is in the source ZIP. A complete solutions manual is not included.

Author, sources and licence

Mathematical text and accompanying book code: Pat Morin. Licence: Creative Commons Attribution 2.5 Canada. Author’s original book page · LaTeX and code source.

Source assembly, typesetting and programme navigation: OpenAI Codex — GPT-6.1 Sol, Ultra effort.