\(\newcommand{\E}{\mathrm{E}} \DeclareMathOperator{\ddiv}{div} \)

• 1 Introduction
• 1.1 The Need for Efficiency
• 1.2 Interfaces
• 1.3 Mathematical Background
• 1.4 The Model of Computation
• 1.5 Correctness, Time Complexity, and Space Complexity
• 1.6 Code Samples
• 1.7 List of Data Structures
• 1.8 Discussion and Exercises
• 2 Array-Based Lists
• 2.1 ArrayStack: Fast Stack Operations Using an Array
• 2.2 FastArrayStack: An Optimized ArrayStack
• 2.3 ArrayQueue: An Array-Based Queue
• 2.4 ArrayDeque: Fast Deque Operations Using an Array
• 2.5 DualArrayDeque: Building a Deque from Two Stacks
• 2.6 RootishArrayStack: A Space-Efficient Array Stack
• 2.7 Discussion and Exercises
• 3 Linked Lists
• 3.1 SLList: A Singly-Linked List
• 3.2 DLList: A Doubly-Linked List
• 3.3 SEList: A Space-Efficient Linked List
• 3.4 Discussion and Exercises
• 4 Skiplists
• 4.1 The Basic Structure
• 4.2 SkiplistSSet: An Efficient SSet
• 4.3 SkiplistList: An Efficient Random-Access List
• 4.4 Analysis of Skiplists
• 4.5 Discussion and Exercises
• 5 Hash Tables
• 5.1 ChainedHashTable: Hashing with Chaining
• 5.2 LinearHashTable: Linear Probing
• 5.3 Hash Codes
• 5.4 Discussion and Exercises
• 6 Binary Trees
• 6.1 BinaryTree: A Basic Binary Tree
• 6.2 BinarySearchTree: An Unbalanced Binary Search Tree
• 6.3 Discussion and Exercises
• 7 Random Binary Search Trees
• 7.1 Random Binary Search Trees
• 7.2 Treap: A Randomized Binary Search Tree
• 7.3 Discussion and Exercises
• 8 Scapegoat Trees
• 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding
• 8.2 Discussion and Exercises
• 9 Red-Black Trees
• 9.1 2-4 Trees
• 9.2 RedBlackTree: A Simulated 2-4 Tree
• 9.3 Summary
• 9.4 Discussion and Exercises
• 10 Heaps
• 10.1 BinaryHeap: An Implicit Binary Tree
• 10.2 MeldableHeap: A Randomized Meldable Heap
• 10.3 Discussion and Exercises
• 11 Sorting Algorithms
• 11.1 Comparison-Based Sorting
• 11.2 Counting Sort and Radix Sort
• 11.3 Discussion and Exercises
• 12 Graphs
• 12.1 AdjacencyMatrix: Representing a Graph by a Matrix
• 12.2 AdjacencyLists: A Graph as a Collection of Lists
• 12.3 Graph Traversal
• 12.4 Discussion and Exercises
• 13 Data Structures for Integers
• 13.1 BinaryTrie: A digital search tree
• 13.2 XFastTrie: Searching in Doubly-Logarithmic Time
• 13.3 YFastTrie: A Doubly-Logarithmic Time SSet
• 13.4 Discussion and Exercises
• 14 External Memory Searching
• 14.1 The Block Store
• 14.2 B-Trees
• 14.3 Discussion and Exercises