Phu Xuan University Library
|
PXU E-LIB
Sign in
Open Data Structures - An Introduction

External

Open Data Structures - An Introduction

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.

Computer ScienceEngineering
Author
Pat Morin
Publisher
Carleton University
Source
LibreTexts
License
CC BY
Language
EN
Category
Information Technology
Read online Download PDF (open licence)
Contents· 71 sections
  1. 01: Introduction
  2. 1.01: The Need for Efficiency
  3. 1.02: Interfaces
  4. 1.03: Mathematical Background
  5. 1.04: The Model of Computation
  6. 1.05: Correctness Time Complexity and Space Complexity
  7. 1.06: Code Samples
  8. 1.07: List of Data Structures
  9. 1.08: Discussion and Exercises
  10. 02: Array-Based Lists
  11. 2.01: ArrayStack - Fast Stack Operations Using an Array
  12. 2.02: FastArrayStack - An Optimized ArrayStack
  13. 2.03: ArrayQueue - An Array-Based Queue
  14. 2.04: ArrayDeque - Fast Deque Operations Using an Array
  15. 2.05: DualArrayDeque - Building a Deque from Two Stacks
  16. 2.06: RootishArrayStack - A Space-Efficient Array Stack
  17. 2.07: Discussion and Exercises
  18. 03: Linked Lists
  19. 3.01: SLList - A Singly-Linked List
  20. 3.02: DLList - A Doubly-Linked List
  21. 3.03: SEList - A Space-Efficient Linked List
  22. 3.04: Discussion and Exercises
  23. 04: Skiplists
  24. 4.01: The Basic Structure
  25. 4.02: SkiplistSSet - An Efficient SSet
  26. 4.03: SkiplistList - An Efficient Random-Access List
  27. 4.04: Analysis of Skiplists
  28. 4.05: Discussion and Exercises
  29. 05: Hash Tables
  30. 5.01: ChainedHashTable - Hashing with Chaining
  31. 5.02: LinearHashTable - Linear Probing
  32. 5.03: Hash Codes
  33. 5.04: Discussion and Exercises
  34. 06: Binary Trees
  35. 6.01: BinaryTree - A Basic Binary Tree
  36. 6.02: BinarySearchTree - An Unbalanced Binary Search Tree
  37. 6.03: Discussion and Exercises
  38. 07: Random Binary Search Trees
  39. 7.01: Random Binary Search Trees
  40. 7.02: Treap - A Randomized Binary Search Tree
  41. 7.03: Discussion and Exercises
  42. 08: Scapegoat Trees
  43. 8.01: ScapegoatTree - A Binary Search Tree with Partial Rebuilding
  44. 8.02: Discussion and Exercises
  45. 09: Red-Black Trees
  46. 9.01: 2-4 Trees
  47. 9.02: A Simulated 2-4 Tree
  48. 9.03: Summary
  49. 9.04: Discussion and Exercises
  50. 10: Heaps
  51. 10.01: BinaryHeap - An Implicit Binary Tree
  52. 10.02: MeldableHeap - A Randomized Meldable Heap
  53. 10.03: Discussion and Exercises
  54. 11: Sorting Algorithms
  55. 11.01: Comparison-Based Sorting
  56. 11.02: Counting Sort and Radix Sort
  57. 11.03: Discussion and Exercises
  58. 12: Graphs
  59. 12.01: Representing a Graph by a Matrix
  60. 12.02: A Graph as a Collection of Lists
  61. 12.03: Graph Traversal
  62. 12.04: Discussion and Exercises
  63. 13: Data Structures for Integers
  64. 13.01: BinaryTrie - A digital search tree
  65. 13.02: XFastTrie - Searching in Doubly-Logarithmic Time
  66. 13.03: YFastTrie - A Doubly-Logarithmic Time SSet
  67. 13.04: Discussion and Exercises
  68. 14: External Memory Searching
  69. 14.01: The Block Store
  70. 14.02: B-Trees
  71. 14.03: Discussion and Exercises