Open Data Structures

An open content textbook

About »
*Open Data Structures* covers the implementation
and analysis of data structures for sequences (lists),
queues, priority queues, unordered dictionaries,
ordered dictionaries, and graphs.

Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search trees including treaps, scapegoat trees, and red-black trees; integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps and randomized meldable heaps; graphs, including adjacency matrix and ajacency list representations; and B-trees.

The data structures in this book are all fast, practical, and have provably good running times. All data structures are rigorously analyzed and implemented in Java and C++. The Java implementations implement the corresponding interfaces in the Java Collections Framework.

The book and accompanying source code are free (*libre*
and *gratis*) and are released under a Creative
Commons Attribution License. Users are free
to copy, distribute, use, and adapt the text
and source code, even commercially. The book's
LaTeX sources, Java/C++/Python
sources, and build scripts are available through github.

Open Data Structures *v slovenščini*
Slovenian translation project (ongoing)

Archives
Older versions of the text and code

Feedback
Send feedback to the author

Related projects