Open Data Structures: An Introduction

Offered as an introduction to the field of data structures andalgorithms, Open Data Structures covers the implementation and analysisof data structures for sequences (lists), queues, priority queues,unordered dictionaries, ordered dictionaries, and graphs. Focusing on amathematically rigorous approach that is fast, practical, andefficient, Morin clearly and briskly presents instruction along withsource code. Analyzed and implemented in Java, the data structures presented inthe book include stacks, queues, deques, and lists implemented asarrays and linked-lists; space-efficient implementations of lists; skiplists; hash tables and hash codes; binary search trees includingtreaps, scapegoat trees, and red-black trees; integer searchingstructures including binary tries, x-fast tries, and y-fast tries;heaps, including implicit binary heaps and randomized meldable heaps;and graphs, including adjacency matrix and adjacency listrepresentations; and B-trees. A modern treatment of an essential computer science topic, Open DataStructures is a measured balance between classical topics andstate-of-the art structures that will serve the needs of allundergraduate students or self-directed learners.