Classic Data Structures

1. Introduction and Overview -- Definitions -- Concept of Data Structures -- Overview of Data Structures -- Implementation of Data Structures -- Organization of the Book -- 2. Arrays -- Definition -- Terminology -- One-Dimensional Array -- Memory Allocation for an Array -- Operations on Arrays -- Application of Arrays -- 4 Multidimensional Arrays -- Two-dimensional Arrays -- Sparse Matrices -- Three-dimensional and H-dimensional Arrays -- Pointer Arrays -- Problems to Ponder -- References -- 3. Linked Lists -- Definition -- Single Linked List -- Representation of a Linked List in Memory -- Operations on a Single Linked List -- Circular Linked List -- Double Linked Lists -- Operations on a Double Linked List -- Circular Double Linked List -- Operations on Circular Double Linked List -- Applications of Linked Lists --Sparse Matrix Manipulation -- Polynomial Representation -- Dynamic Storage Management -- Memory Representation -- Fixed Block Storage -- Variable Block Storage -- Boundary Tag System -- Deallocation Strategy -- Buddy System -- Binary Buddy System -- Comparison between Fibonacci and Binary Buddy System -- Comparison of Dynamic Storage Allocation Systems -- Compaction -- Problems to Ponder -- References -- 4. Stacks -- Introduction -- Definition -- Representation of a Stack -- Array Representation of Stacks -- Linked List Representation of Stacks -- Operations on Stacks -- Applications of Stacks -- Evaluation of Arithmetic Expressions -- Code Generation for Stack Machines -- Implementation of Recursion -- Factorial Calculation -- Quick Sort -- Tower of Hanoi Problem -- Activation Record Management -- Problems to Ponder -- References -- 5. Queues -- Introduction -- Definition -- 5.3 Representation of Queues -- Representation of a Queue using an Array -- Representation of a Queue using a Linked List -- Various Queue Structures -- Circular Queue-- Deque -- Priority Queue -- Applications of Queues -- Simulation -- CPU Scheduling in a Multiprogramming Environment -- Round Robin Algorithm -- Problems to Ponder -- References -- 6. Tables -- Rectangular Tables -- Jagged Tables -- Inverted Tables -- Hash Tables -- Hashing Techniques -- Collision Resolution Techniques -- Closed Hashing -- Open Hashing -- Comparison of Collision Resolution Techniques -- Problems to Ponder -- References -- 7. Trees -- Basic Terminologies -- Definition and Concepts -- A Binary Trees -- Properties of a Binary Tree -- Representations of Binary Tree -- Linear Representation of a Binary Tree -- Linked Representation of a Binary Tree -- Physical Implementation of a Binary Tree in Memory -- Operations on a Binary Tree -- Insertion -- Deletion --- Traversals -- Merging together Two Binary Trees -- Types of Binary Trees -- Expression Tree -- Binary Search Tree -- Heap Trees -- Threaded Binary Trees -- Height Balanced Binary Tree -- Red-black Tree -- Splay Tree -- Weighted Binary Tree -- Decision Trees --Trees and Forests -- A Representation of Trees -- Trees -- Tree Indexing -- Operations on a B Tree -- Lower and Upper Bounds of a B Tree -- Tree Indexing -- Trie Tree Indexing -- Trie Structure -- Operations on Trie -- Applications of Tree Indexing -- Problems to Ponder -- References -- 8. Graphs -- Introduction -- Graph Terminologies -- Representation of Graphs -- Set Representation -- Linked Representation -- Matrix Representation -- Operations on Graphs -- Operations on Linked List Representation of Graphs -- Operations on Matrix Representation of Graphs -- Application of Graph Structures -- Shortest Path Problem -- Topological Sorting -- Minimum Spanning Trees -- Connectivity in a Graph -- Euler's and Hamiltonian Circuits -- BDD and Its Applications -- Conversion of Decision Tree into BDD -- Applications of BDD -- Problems to Ponder -- References -- 9. Sets -- Definition and Terminologies -- Representation of Sets -- Linked List Representation of Set -- Hash Table Representation of Sets -- Bit Vector Representation of Sets -- Tree Representation of Sets -- Operations of Sets -- Operations on List Representation of Set -- Operations on Hash Table Representation of Set -- Operations on Bit Vector Representation of Set -- Operation on Tree Representation of Set -- Applications of Sets -- Spelling Checker -- Information System using Bit Strings -- Client-Server Environment -- Problems to Ponder -- References -- 10. Sorting -- Basic Terminologies -- Sorting Techniques -- Sorting by Insertion -- Straight Insertion Sort -- List Insertion Sort -- Binary Insertion Sort -- Two-Way Insertion Sort -- Summary of "Sorting by Insertion" Family -- Sorting by Selection -- Straight Selection Sort -- Tree Selection Sort -- Heap Sort -- Summary of "Sorting by Selection" Family -- Sorting by Exchange -- Bubble Sort -- Refinements in the Bubble Sort -- Shell Sort -- Quick Sort -- Summary of "Sorting by Exchange" Family -- Sorting by Distribution -- Radix Sort -- Bucket Sort -- Counting Sort -- Summary of 'Sorting by Distribution' Family -- Sorting by Merging -- Simple Merging -- Binary Merge -- Merge Sort --Internal Merge Sort -- Two-way Merge Sort -- Summary of 'Sorting by Merge' Family -- External Merge Sort -- Balanced Two-way Merge Sort -- Multi-way Merge Sort -- Poly-phase Merge Sort -- Oscillating Sort -- Optimum Sorting Algorithms -- Lower Bounds for Sorting by Comparison of Keys Only -- Lower Bound for Sorting based on Merging with Key Comparisons -- Lower Bound for Sorting based on Selection with Key -- Comparisons -- Summary of all Sorting Algorithms -- Problems to Ponder -- References -- 11. Searching -- Basic Terminologies -- Linear Search Techniques -- Linear Search with Array -- Linear Search with Linked List -- Linear Search with Ordered List -- Binary Search -- Fibonacci Search -- Interpolation Search -- Summary of Linear Search Algorithms -- Non-linear Search Techniques -- Binary Tree Searching -- Binary Search Tree Searching -- Searching in Other Variations of Binary Search Tree -- Graph Searching -- External Searching -- Problems to Ponder --References