Table of Contents Last updated Save as PDF Page ID10935 1: Introduction1.1: The Need for Efficiency1.2: Interfaces1.3: Mathematical Background1.4: The Model of Computation1.5: Correctness, Time Complexity, and Space Complexity1.6: Code Samples1.7: List of Data Structures1.8: Discussion and Exercises2: Array-Based Lists2.1: ArrayStack - Fast Stack Operations Using an Array2.2: FastArrayStack - An Optimized ArrayStack2.3: ArrayQueue - An Array-Based Queue2.4: ArrayDeque - Fast Deque Operations Using an Array2.5: DualArrayDeque - Building a Deque from Two Stacks2.6: RootishArrayStack - A Space-Efficient Array Stack2.7: Discussion and Exercises3: Linked Lists3.1: SLList - A Singly-Linked List3.2: DLList - A Doubly-Linked List3.3: SEList - A Space-Efficient Linked List3.4: Discussion and Exercises4: Skiplists4.1: The Basic Structure4.2: SkiplistSSet - An Efficient SSet4.3: SkiplistList - An Efficient Random-Access List4.4: Analysis of Skiplists4.5: Discussion and Exercises5: Hash Tables5.1: ChainedHashTable - Hashing with Chaining5.2: LinearHashTable - Linear Probing5.3: Hash Codes5.4: Discussion and Exercises6: Binary Trees6.1: BinaryTree - A Basic Binary Tree6.2: BinarySearchTree - An Unbalanced Binary Search Tree6.3: Discussion and Exercises7: Random Binary Search Trees7.1: Random Binary Search Trees7.2: Treap - A Randomized Binary Search Tree7.3: Discussion and Exercises8: Scapegoat Trees8.1: ScapegoatTree - A Binary Search Tree with Partial Rebuilding8.2: Discussion and Exercises9: Red-Black Trees9.1: 2-4 Trees9.2: A Simulated 2-4 Tree9.3: Summary9.4: Discussion and Exercises10: Heaps10.1: BinaryHeap - An Implicit Binary Tree10.2: MeldableHeap - A Randomized Meldable Heap10.3: Discussion and Exercises11: Sorting Algorithms11.1: Comparison-Based Sorting11.2: Counting Sort and Radix Sort11.3: Discussion and Exercises12: Graphs12.1: Representing a Graph by a Matrix12.2: A Graph as a Collection of Lists12.3: Graph Traversal12.4: Discussion and Exercises13: Data Structures for Integers13.1: BinaryTrie - A digital search tree13.2: XFastTrie - Searching in Doubly-Logarithmic Time13.3: YFastTrie - A Doubly-Logarithmic Time SSet13.4: Discussion and Exercises14: External Memory Searching14.1: The Block Store14.2: B-Trees14.3: Discussion and ExercisesBack MatterIndex
