ODS Python - Open Data Structures
Open Data Structures (in pseudocode)
Edition 0.1G¦Â
Pat Morin
Contents
Acknowledgments
ix
Why This Book?
xi
1 Introduction
1.1 The Need for Efficiency . . . . . . . . . . . . . . . . . .
1.2 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 The Queue, Stack, and Deque Interfaces . . . .
1.2.2 The List Interface: Linear Sequences . . . . . .
1.2.3 The USet Interface: Unordered Sets . . . . . . .
1.2.4 The SSet Interface: Sorted Sets . . . . . . . . . .
1.3 Mathematical Background . . . . . . . . . . . . . . . .
1.3.1 Exponentials and Logarithms . . . . . . . . . .
1.3.2 Factorials . . . . . . . . . . . . . . . . . . . . . .
1.3.3 Asymptotic Notation . . . . . . . . . . . . . . .
1.3.4 Randomization and Probability . . . . . . . . .
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.1.1 The Basics . . . . . . . . . . . . . . . . . . .
2.1.2 Growing and Shrinking . . . . . . . . . . . .
2.1.3 Summary . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
4
5
6
8
8
9
10
11
12
15
18
19
21
23
23
.
.
.
.
31
32
32
35
37
Contents
2.2 FastArrayStack: An Optimized ArrayStack . . . . . .
2.3 ArrayQueue: An Array-Based Queue . . . . . . . . .
2.3.1 Summary . . . . . . . . . . . . . . . . . . . . .
2.4 ArrayDeque: Fast Deque Operations Using an Array
2.4.1 Summary . . . . . . . . . . . . . . . . . . . . .
2.5 DualArrayDeque: Building a Deque from Two Stacks
2.5.1 Balancing . . . . . . . . . . . . . . . . . . . . .
2.5.2 Summary . . . . . . . . . . . . . . . . . . . . .
2.6 RootishArrayStack: A Space-Efficient Array Stack . .
2.6.1 Analysis of Growing and Shrinking . . . . . .
2.6.2 Space Usage . . . . . . . . . . . . . . . . . . .
2.6.3 Summary . . . . . . . . . . . . . . . . . . . . .
2.7 Discussion and Exercises . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
38
41
42
44
44
48
50
50
55
55
56
57
3 Linked Lists
3.1 SLList: A Singly-Linked List . . . . . . . . . . . . . . . .
3.1.1 Queue Operations . . . . . . . . . . . . . . . . . .
3.1.2 Summary . . . . . . . . . . . . . . . . . . . . . . .
3.2 DLList: A Doubly-Linked List . . . . . . . . . . . . . . .
3.2.1 Adding and Removing . . . . . . . . . . . . . . .
3.2.2 Summary . . . . . . . . . . . . . . . . . . . . . . .
3.3 SEList: A Space-Efficient Linked List . . . . . . . . . . .
3.3.1 Space Requirements . . . . . . . . . . . . . . . .
3.3.2 Finding Elements . . . . . . . . . . . . . . . . . .
3.3.3 Adding an Element . . . . . . . . . . . . . . . . .
3.3.4 Removing an Element . . . . . . . . . . . . . . .
3.3.5 Amortized Analysis of Spreading and Gathering
3.3.6 Summary . . . . . . . . . . . . . . . . . . . . . . .
3.4 Discussion and Exercises . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
61
61
63
64
64
66
68
68
69
69
71
73
75
77
78
.
.
.
.
.
83
83
85
88
89
93
4 Skiplists
4.1 The Basic Structure . . . . . . . . . . . . . . .
4.2 SkiplistSSet: An Efficient SSet . . . . . . . . .
4.2.1 Summary . . . . . . . . . . . . . . . . .
4.3 SkiplistList: An Efficient Random-Access List
4.3.1 Summary . . . . . . . . . . . . . . . . .
iv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.4 Analysis of Skiplists . . . . . . . . . . . . . . . . . . . . . . . 93
4.5 Discussion and Exercises . . . . . . . . . . . . . . . . . . . . 97
5 Hash Tables
5.1 ChainedHashTable: Hashing with Chaining
5.1.1 Multiplicative Hashing . . . . . . . .
5.1.2 Summary . . . . . . . . . . . . . . . .
5.2 LinearHashTable: Linear Probing . . . . . .
5.2.1 Analysis of Linear Probing . . . . . .
5.2.2 Summary . . . . . . . . . . . . . . . .
5.2.3 Tabulation Hashing . . . . . . . . . .
5.3 Hash Codes . . . . . . . . . . . . . . . . . . .
5.3.1 Hash Codes for Primitive Data Types
5.3.2 Hash Codes for Compound Objects .
5.3.3 Hash Codes for Arrays and Strings .
5.4 Discussion and Exercises . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Binary Trees
6.1 BinaryTree: A Basic Binary Tree . . . . . . . . . . . . .
6.1.1 Recursive Algorithms . . . . . . . . . . . . . . .
6.1.2 Traversing Binary Trees . . . . . . . . . . . . . .
6.2 BinarySearchTree: An Unbalanced Binary Search Tree
6.2.1 Searching . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Addition . . . . . . . . . . . . . . . . . . . . . .
6.2.3 Removal . . . . . . . . . . . . . . . . . . . . . .
6.2.4 Summary . . . . . . . . . . . . . . . . . . . . . .
6.3 Discussion and Exercises . . . . . . . . . . . . . . . . .
7 Random Binary Search Trees
7.1 Random Binary Search Trees . . . . . . . .
7.1.1 Proof of Lemma 7.1 . . . . . . . . .
7.1.2 Summary . . . . . . . . . . . . . . .
7.2 Treap: A Randomized Binary Search Tree .
7.2.1 Summary . . . . . . . . . . . . . . .
7.3 Discussion and Exercises . . . . . . . . . .
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
101
101
104
108
108
112
115
115
117
117
117
119
122
.
.
.
.
.
.
.
.
.
127
129
129
130
133
133
135
137
139
140
.
.
.
.
.
.
145
145
148
150
151
158
160
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- lab manual python programming lab 6cs4 23
- ods python open data structures
- fifth starting out with edition programming logic design
- numpy tutorialspoint
- preeti arora
- fundamentals of python
- python for data science cheat sheet lists also see numpy
- cheat sheet numpy python copy
- numpy user guide
- cheat sheet pandas python datacamp