Open Data Structures
Free

Open Data Structures

By Pat Morin
Free
Book Description
Table of Contents
  • Acknowledgments
  • Why This Book?
  • Introduction
    • The Need for Efficiency
    • Interfaces
      • The Queue, Stack, and Deque Interfaces
      • The List Interface: Linear Sequences
      • The USet Interface: Unordered Sets
      • The SSet Interface: Sorted Sets
    • Mathematical Background
      • Exponentials and Logarithms
      • Factorials
      • Asymptotic Notation
      • Randomization and Probability
    • The Model of Computation
    • Correctness, Time Complexity, and Space Complexity
    • Code Samples
    • List of Data Structures
    • Discussion and Exercises
  • Array-Based Lists
    • ArrayStack: Fast Stack Operations Using an Array
      • The Basics
      • Growing and Shrinking
      • Summary
    • FastArrayStack: An Optimized ArrayStack
    • ArrayQueue: An Array-Based Queue
      • Summary
    • ArrayDeque: Fast Deque Operations Using an Array
      • Summary
    • DualArrayDeque: Building a Deque from Two Stacks
      • Balancing
      • Summary
    • RootishArrayStack: A Space-Efficient Array Stack
      • Analysis of Growing and Shrinking
      • Space Usage
      • Summary
      • Computing Square Roots
    • Discussion and Exercises
  • Linked Lists
    • SLList: A Singly-Linked List
      • Queue Operations
      • Summary
    • DLList: A Doubly-Linked List
      • Adding and Removing
      • Summary
    • SEList: A Space-Efficient Linked List
      • Space Requirements
      • Finding Elements
      • Adding an Element
      • Removing an Element
      • Amortized Analysis of Spreading and Gathering
      • Summary
    • Discussion and Exercises
  • Skiplists
    • The Basic Structure
    • SkiplistSSet: An Efficient SSet
      • Summary
    • SkiplistList: An Efficient Random-Access List
      • Summary
    • Analysis of Skiplists
    • Discussion and Exercises
  • Hash Tables
    • ChainedHashTable: Hashing with Chaining
      • Multiplicative Hashing
      • Summary
    • LinearHashTable: Linear Probing
      • Analysis of Linear Probing
      • Summary
      • Tabulation Hashing
    • Hash Codes
      • Hash Codes for Primitive Data Types
      • Hash Codes for Compound Objects
      • Hash Codes for Arrays and Strings
    • Discussion and Exercises
  • Binary Trees
    • BinaryTree: A Basic Binary Tree
      • Recursive Algorithms
      • Traversing Binary Trees
    • BinarySearchTree: An Unbalanced Binary Search Tree
      • Searching
      • Addition
      • Removal
      • Summary
    • Discussion and Exercises
  • Random Binary Search Trees
    • Random Binary Search Trees
      • Proof of Lemma 7.1
      • Summary
    • Treap: A Randomized Binary Search Tree
      • Summary
    • Discussion and Exercises
  • Scapegoat Trees
    • ScapegoatTree: A Binary Search Tree with Partial Rebuilding
      • Analysis of Correctness and Running-Time
      • Summary
    • Discussion and Exercises
  • Red-Black Trees
    • 2-4 Trees
      • Adding a Leaf
      • Removing a Leaf
    • RedBlackTree: A Simulated 2-4 Tree
      • Red-Black Trees and 2-4 Trees
      • Left-Leaning Red-Black Trees
      • Addition
      • Removal
    • Summary
    • Discussion and Exercises
  • Heaps
    • BinaryHeap: An Implicit Binary Tree
      • Summary
    • MeldableHeap: A Randomized Meldable Heap
      • Analysis of merge(varh1,varh2)
      • Summary
    • Discussion and Exercises
  • Sorting Algorithms
    • Comparison-Based Sorting
      • Merge-Sort
      • Quicksort
      • Heap-sort
      • A Lower-Bound for Comparison-Based Sorting
    • Counting Sort and Radix Sort
      • Counting Sort
      • Radix-Sort
    • Discussion and Exercises
  • Graphs
    • AdjacencyMatrix: Representing a Graph by a Matrix
    • AdjacencyLists: A Graph as a Collection of Lists
    • Graph Traversal
      • Breadth-First Search
      • Depth-First Search
    • Discussion and Exercises
  • Data Structures for Integers
    • BinaryTrie: A digital search tree
    • XFastTrie: Searching in Doubly-Logarithmic Time
    • YFastTrie: A Doubly-Logarithmic Time SSet
    • Discussion and Exercises
  • External Memory Searching
    • The Block Store
    • B-Trees
      • Searching
      • Addition
      • Removal
      • Amortized Analysis of B-Trees
    • 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
      Also Available On
      App store smallGoogle play small
      Categories
      Curated Lists
      • Pattern Recognition and Machine Learning (Information Science and Statistics)
        by Christopher M. Bishop
        Data mining
        by I. H. Witten
        The Elements of Statistical Learning: Data Mining, Inference, and Prediction
        by Various
        See more...
      • CK-12 Chemistry
        by Various
        Concept Development Studies in Chemistry
        by John Hutchinson
        An Introduction to Chemistry - Atoms First
        by Mark Bishop
        See more...
      • Microsoft Word - How to Use Advanced Algebra II.doc
        by Jonathan Emmons
        Advanced Algebra II: Activities and Homework
        by Kenny Felder
        de2de
        by
        See more...
      • The Sun Who Lost His Way
        by
        Tania is a Detective
        by Kanika G
        Firenze_s-Light
        by
        See more...
      • Java 3D Programming
        by Daniel Selman
        The Java EE 6 Tutorial
        by Oracle Corporation
        JavaKid811
        by
        See more...