Open Data Structures: An Introduction [Paperback]

Offered as an introduction to the field of data structures and algorithms,Open Data Structurescovers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Focusing on a mathematically rigorous approach that is fast, practical, and efficient, Morin clearly and briskly presents instruction along with source code.

Acknowledgments- xi

Why This Book?- xiii

1. Introduction- 1

            1.1 The Need for Efficiency- 2

            1.2 Interfaces- 4

            1.3 Mathematical Background- 9

            1.4 The Model of Computation- 18

            1.5 Correctness, Time Complexity, and Space Complexity- 19

            1.6 Code Samples- 22

            1.7 List of Data Structures- 22

            1.8 Discussion and Exercises- 26

2. Array-Based Lists- 29

            2.1 ArrayStack: Fast Stack Operations Using an Array- 30

2.2 FastArrayStack: An Optimized ArrayStack- 35

2.3 ArrayQueue: An Array-Based Queue- 36

2.4 ArrayDeque: Fast Deque Operations Using an Array- 40

2.5 DualArrayDeque: Building a Deque from Two Stacks- 43

2.6 RootishArrayStack: A Space-Efficient Array Stack- 49

2.7 Discussion and Exercises- 59

3. Linked Lists- 63

            3.1 SLList: A Singly-Linked List- 63

l“Î