Open Data Structures
Free

Open Data Structures

By Pat Morin
Free
Book Description
Table of Contents
  • Front Matter
  • Contents
  • Acknowledgments
  • Why This Book?
  • 1. Introduction
    • 1.1 The Need for Efficiency
    • 1.2 Interfaces
      • 1.2.1 The Queue, Stack, and Deque Interfaces
      • 1.2.2 The List Interface: Linear Sequences
      • 1.2.3 The USet Interface: Unordered Sets
      • 1.2.4 The SSet Interface: Sorted Sets
    • 1.3 Mathematical Background
      • 1.3.1 Exponentials and Logarithms
      • 1.3.2 Factorials
      • 1.3.3 Asymptotic Notation
      • 1.3.4 Randomization and Probability
    • 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
      • The Basics
      • Growing and Shrinking
      • Summary
    • 2.2 FastArrayStack: An Optimized ArrayStack
    • 2.3 ArrayQueue: An Array-Based Queue
      • 2.3.1 Summary
    • 2.4 ArrayDeque: Fast Deque Operations Using an Array
      • 2.4.1 Summary
    • 2.5 DualArrayDeque: Building a Deque from Two Stacks
      • 2.5.1 Balancing
      • 2.5.2 Summary
    • 2.6 RootishArrayStack: A Space-Efficient Array Stack
      • 2.6.1 Analysis of Growing and Shrinking
      • 2.6.2 Space Usage
      • 2.6.3 Summary
      • 2.6.4 Computing Square Roots
    • 2.7 Discussion and Exercises
  • 3. Linked Lists
    • 3.1 SLList: A Singly-Linked List
      • 3.1.1 Queue Operations
      • 3.1.2 Summary
    • 3.2 DLList: A Doubly-Linked List
      • 3.2.1 Adding and Removing
      • 3.2.2 Summary
    • 3.3 SEList: A Space-Efficient Linked List
      • 3.3.1 Space Requirements
      • 3.3.2 Finding Elements
      • 3.3.3 Adding an Element
      • 3.3.4 Removing an Element
      • 3.3.5 Amortized Analysis of Spreading and Gathering
      • 3.3.6 Summary
    • 3.4 Discussion and Exercises
  • 4. Skiplists
    • 4.1 The Basic Structure
    • 4.2 SkiplistSSet: An Efficient SSet
      • 4.2.1 Summary
    • 4.3 SkiplistList: An Efficient Random-Access List
      • 4.3.1 Summary
    • 4.4 Analysis of Skiplists
    • 4.5 Discussion and Exercises
  • 5. Hash Tables
    • 5.1 ChainedHashTable: Hashing with Chaining
      • 5.1.1 Multiplicative Hashing
      • 5.1.2 Summary
    • 5.2 LinearHashTable: Linear Probing
      • 5.2.1 Analysis of Linear Probing
      • 5.2.2 Summary
      • 5.2.3 Tabulation Hashing
    • 5.3 Hash Codes
      • 5.3.1 Hash Codes for Primitive Data Types
      • 5.3.2 Hash Codes for Compound Objects
      • 5.3.3 Hash Codes for Arrays and Strings
    • 5.4 Discussion and Exercises
  • 6. Binary Trees
    • 6.1 BinaryTree: A Basic Binary Tree
      • 6.1.1 Recursive Algorithms
      • 6.1.2 Traversing Binary Trees
    • 6.2 BinarySearchTree: An Unbalanced Binary Search Tree
      • 6.2.1 Searching
      • 6.2.2 Addition
      • 6.2.3 Removal
      • 6.2.4 Summary
    • 6.3 Discussion and Exercises
  • 7. Random Binary Search Trees
    • 7.1 Random Binary Search Trees
      • 7.1.1 Proof of Lemma 7.1
      • 7.1.2 Summary
    • 7.2 Treap: A Randomized Binary Search Tree
      • 7.2.1 Summary
    • 7.3 Discussion and Exercises
  • 8. Scapegoat Trees
    • 8.1 ScapegoatTree: A Binary Search Tree with Partial Rebuilding
      • 8.1.1 Analysis of Correctness and Running-Time
      • 8.1.2 Summary
    • 8.2 Discussion and Exercises
  • 9. Red-Black Trees
    • 9.1 2-4 Trees
      • 9.1.1 Adding a Leaf
      • 9.1.2 Removing a Leaf
    • 9.2 RedBlackTree: A Simulated 2-4 Tree
      • 9.2.1 Red-Black Trees and 2-4 Trees
      • 9.2.2 Left-Leaning Red-Black Trees
      • 9.2.3 Addition
      • 9.2.4 Removal
    • 9.3 Summary
    • 9.4 Discussion and Exercises
  • 10. Heaps
    • 10.1 BinaryHeap: An Implicit Binary Tree
      • 10.1.1 Summary
    • 10.2 MeldableHeap: A Randomized Meldable Heap
      • 10.2.1 Analysis of merge(varh1,varh2)
      • 10.2.2 Summary
    • 10.3 Discussion and Exercises
  • 11. Sorting Algorithms
    • 11.1 Comparison-Based Sorting
      • 11.1.1 Merge-Sort
      • 11.1.2 Quicksort
      • 11.1.3 Heap-sort
      • 11.1.4 A Lower-Bound for Comparison-Based Sorting
    • 11.2 Counting Sort and Radix Sort
      • 11.2.1 Counting Sort
      • 11.2.2 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.3.1 Breadth-First Search
      • 12.3.3 Depth-First Search
    • 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.2.1 Searching
      • 14.2.2 Addition
      • 14.2.3 Removal
      • 14.2.4 Amortized Analysis of B-Trees
    • 14.3 Discussion and Exercises
  • Bibliography
  • Index
    No review for this book yet, be the first to review.
      No comment for this book yet, be the first to comment
      You May Also Like