Open Data Structures - An Introduction

by Pat Morin

Read here Read at LibreTextsPDF

Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Focusing on a mathematically rigorous approach that is fast, practical, and efficient, Morin clearly and briskly presents instruction along with source code.

Description from LibreTexts.

Publisher
Carleton University
Subjects
Engineering, Computer Science
Licence
CC BY, as LibreTexts states it
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Acknowledgments
  6. Licensing
  7. Why This Book?
  8. 1: Introduction
  9. 1.1: The Need for Efficiency
  10. 1.2: Interfaces
  11. 1.3: Mathematical Background
  12. 1.4: The Model of Computation
  13. 1.5: Correctness, Time Complexity, and Space Complexity
  14. 1.6: Code Samples
  15. 1.7: List of Data Structures
  16. 1.8: Discussion and Exercises
  17. 2: Array-Based Lists
  18. 2.1: ArrayStack - Fast Stack Operations Using an Array
  19. 2.2: FastArrayStack - An Optimized ArrayStack
  20. 2.3: ArrayQueue - An Array-Based Queue
  21. 2.4: ArrayDeque - Fast Deque Operations Using an Array
  22. 2.5: DualArrayDeque - Building a Deque from Two Stacks
  23. 2.6: RootishArrayStack - A Space-Efficient Array Stack
  24. 2.7: Discussion and Exercises
  25. 3: Linked Lists
  26. 3.1: SLList - A Singly-Linked List
  27. 3.2: DLList - A Doubly-Linked List
  28. 3.3: SEList - A Space-Efficient Linked List
  29. 3.4: Discussion and Exercises
  30. 4: Skiplists
  31. 4.1: The Basic Structure
  32. 4.2: SkiplistSSet - An Efficient SSet
  33. 4.3: SkiplistList - An Efficient Random-Access List
  34. 4.4: Analysis of Skiplists
  35. 4.5: Discussion and Exercises
  36. 5: Hash Tables
  37. 5.1: ChainedHashTable - Hashing with Chaining
  38. 5.2: LinearHashTable - Linear Probing
  39. 5.3: Hash Codes
  40. 5.4: Discussion and Exercises
  41. 6: Binary Trees
  42. 6.1: BinaryTree - A Basic Binary Tree
  43. 6.2: BinarySearchTree - An Unbalanced Binary Search Tree
  44. 6.3: Discussion and Exercises
  45. 7: Random Binary Search Trees
  46. 7.1: Random Binary Search Trees
  47. 7.2: Treap - A Randomized Binary Search Tree
  48. 7.3: Discussion and Exercises
  49. 8: Scapegoat Trees
  50. 8.1: ScapegoatTree - A Binary Search Tree with Partial Rebuilding
  51. 8.2: Discussion and Exercises
  52. 9: Red-Black Trees
  53. 9.1: 2-4 Trees
  54. 9.2: A Simulated 2-4 Tree
  55. 9.3: Summary
  56. 9.4: Discussion and Exercises
  57. 10: Heaps
  58. 10.1: BinaryHeap - An Implicit Binary Tree
  59. 10.2: MeldableHeap - A Randomized Meldable Heap
  60. 10.3: Discussion and Exercises
  61. 11: Sorting Algorithms
  62. 11.1: Comparison-Based Sorting
  63. 11.2: Counting Sort and Radix Sort
  64. 11.3: Discussion and Exercises
  65. 12: Graphs
  66. 12.1: Representing a Graph by a Matrix
  67. 12.2: A Graph as a Collection of Lists
  68. 12.3: Graph Traversal
  69. 12.4: Discussion and Exercises
  70. 13: Data Structures for Integers
  71. 13.1: BinaryTrie - A digital search tree
  72. 13.2: XFastTrie - Searching in Doubly-Logarithmic Time
  73. 13.3: YFastTrie - A Doubly-Logarithmic Time SSet
  74. 13.4: Discussion and Exercises
  75. 14: External Memory Searching
  76. 14.1: The Block Store
  77. 14.2: B-Trees
  78. 14.3: Discussion and Exercises
  79. Back Matter
  80. Index
  81. Bibliography
  82. Index
  83. Glossary
  84. Detailed Licensing