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: A Space-Efficient Linked List- 71            3.4 Discussion and Exercises- 82 4. Skiplists- 87            4.1 The Basic Structure- 87            4.2 SkiplistSSet: An Efficient Sset- 90            4.3 SkiplistList: An Efficient Random-Access List- 93            4.4 Analysis of Skiplists- 98            4.5 Discussion and Exercises- 102 5. Hash Tables- 107            5.1 ChainedHashTable: Hashing with Chaining- 107            5.2 LinearHashTable: Linear Probing- 114            5.3 Hash Codes- 122            5.4 Discussion and Exercises- 128 6. Binary Trees- 133            6.1 BinaryTree: A Basic Binary Tree- 135            6.2 BinarySearchTree: An Unbalanced Binary Search Tree- 140            6.3 Discussion and Exercises- 147 7. Random Binary Search Trees- 153            7.1 Random Binary Search Trees- 153            7.2 Treap: A Randomized Binary Search Tree- 159            7.3 Discussion and Exercises- 168 8. Scapegoat Trees- 173            8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding-173            8.2 Discussion and Exercises- 181 9. Red-Black Trees- 185            9.1 2-4 Trees- 186            9.2 RedBlackTree: A Simulated 2-4 Tree- 190            9.3 Summary- 205            9.4 Discussion and Exercises- 206 10. Heaps- 211            10.1 BinaryHeap: An Implicit Binary Tree- 211            10.2 MeldableHeap: A Randomized Meldable Heap- 217            10.3 Discussion and Exercises- 222 11. Sorting Algorithms- 225            11.1 Comparison-Based Sorting- 226            11.2 Counting Sort and Radix Sort- 238            11.3 Discussion and Exercises- 243 12. Graphs- 247            12.1 AdjacencyMatrix: Representing a Graph by a Matrix- 249            12.2 AdjacencyLists: A Graph as a Collection of Lists- 252            12.3 Graph Traversal- 256            12.4 Discussion and Exercises- 261 13. Data Structures for Integers- 265            13.1 BinaryTrie: A digital search tree- 266            13.2 XFastTrie: Searching in Doubly-Logarithmic Time- 272            13.3 YFastTrie: A Doubly-Logarithmic Time SSet- 275            13.4 Discussion and Exercises- 280 14. External Memory Searching- 283            14.1 The Block Store- 285            14.2 B-Trees- 285            14.3 Discussion and Exercises- 304 Bibliography- 309 Index- 317