Pat Morin is Professor in the School of ComputerScience at Carleton University as well as founder and managing editorof the open access Journal of Computational Geometry. He is the authorof numerous conference papers and journal publications on the topics ofcomputational geometry, algorithms, and data structures.

• Acknowledgments- xiWhy This Book?- xiii1. Introduction- 11.1 The Need for Efficiency- 21.2 Interfaces- 41.3 Mathematical Background- 91.4 The Model of Computation- 181.5 Correctness, Time Complexity, and Space Complexity- 191.6 Code Samples- 221.7 List of Data Structures- 221.8 Discussion and Exercises- 262. Array-Based Lists- 292.1 ArrayStack: Fast Stack Operations Using an Array- 302.2 FastArrayStack: An Optimized ArrayStack- 352.3 ArrayQueue: An Array-Based Queue- 362.4 ArrayDeque: Fast Deque Operations Using an Array- 402.5 DualArrayDeque: Building a Deque from Two Stacks- 432.6 RootishArrayStack: A Space-Efficient Array Stack- 492.7 Discussion and Exercises- 593. Linked Lists- 633.1 SLList: A Singly-Linked List- 633.2 DLList: A Doubly-Linked List- 673.3 SEList: A Space-Efficient Linked List- 713.4 Discussion and Exercises- 824. Skiplists- 874.1 The Basic Structure- 874.2 SkiplistSSet: An Efficient Sset- 904.3 SkiplistList: An Efficient Random-Access List- 934.4 Analysis of Skiplists- 984.5 Discussion and Exercises- 1025. Hash Tables- 1075.1 ChainedHashTable: Hashing with Chaining- 1075.2 LinearHashTable: Linear Probing- 1145.3 Hash Codes- 1225.4 Discussion and Exercises- 1286. Binary Trees- 1336.1 BinaryTree: A Basic Binary Tree- 1356.2 BinarySearchTree: An Unbalanced Binary Search Tree- 1406.3 Discussion and Exercises- 1477. Random Binary Search Trees- 1537.1 Random Binary Search Trees- 1537.2 Treap: A Randomized Binary Search Tree- 1597.3 Discussion and Exercises- 1688. Scapegoat Trees- 1738.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding-1738.2 Discussion and Exercises- 1819. Red-Black Trees- 1859.1 2-4 Trees- 1869.2 RedBlackTree: A Simulated 2-4 Tree- 1909.3 Summary- 2059.4 Discussion and Exercises- 20610. Heaps- 21110.1 BinaryHeap: An Implicit Binary Tree- 21110.2 MeldableHeap: A Randomized Meldable Heap- 21710.3 Discussion and Exercises- 22211. Sorting Algorithms- 22511.1 Comparison-Based Sorting- 22611.2 Counting Sort and Radix Sort- 23811.3 Discussion and Exercises- 24312. Graphs- 24712.1 AdjacencyMatrix: Representing a Graph by a Matrix- 24912.2 AdjacencyLists: A Graph as a Collection of Lists- 25212.3 Graph Traversal- 25612.4 Discussion and Exercises- 26113. Data Structures for Integers- 26513.1 BinaryTrie: A digital search tree- 26613.2 XFastTrie: Searching in Doubly-Logarithmic Time- 27213.3 YFastTrie: A Doubly-Logarithmic Time SSet- 27513.4 Discussion and Exercises- 28014. External Memory Searching- 28314.1 The Block Store- 28514.2 B-Trees- 28514.3 Discussion and Exercises- 304Bibliography- 309Index- 317