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

            3.2 DLList: A Doubly-Linked List- 67

            3.3 SEList: