Skip to main content
Engineering LibreTexts

Table of Contents

  • Page ID
    10935
    • 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: 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: Representing a Graph by a Matrix
      • 12.2: 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
    • Back Matter

      • Index
    • Was this article helpful?