Preface |
|
xi | |
|
1 Why Data Structures Matter |
|
|
1 | (20) |
|
|
2 | (1) |
|
The Array: The Foundational Data Structure |
|
|
3 | (1) |
|
|
4 | (1) |
|
|
5 | (3) |
|
|
8 | (3) |
|
|
11 | (2) |
|
|
13 | (2) |
|
Sets: How a Single Rule Can Affect Efficiency |
|
|
15 | (3) |
|
|
18 | (1) |
|
|
19 | (2) |
|
|
21 | (14) |
|
|
22 | (2) |
|
Searching an Ordered Array |
|
|
24 | (2) |
|
|
26 | (5) |
|
Binary Search vs. Linear Search |
|
|
31 | (3) |
|
|
34 | (1) |
|
|
34 | (1) |
|
|
35 | (12) |
|
Big O: How Many Steps Relative to N Elements? |
|
|
36 | (1) |
|
|
37 | (3) |
|
An Algorithm of the Third Kind |
|
|
40 | (1) |
|
|
41 | (1) |
|
|
42 | (1) |
|
|
43 | (2) |
|
|
45 | (1) |
|
|
45 | (2) |
|
4 Speeding Up Your Code with Big O |
|
|
47 | (16) |
|
|
47 | (1) |
|
|
48 | (5) |
|
The Efficiency of Bubble Sort |
|
|
53 | (3) |
|
|
56 | (2) |
|
|
58 | (2) |
|
|
60 | (1) |
|
|
60 | (3) |
|
5 Optimizing Code with and Without Big O |
|
|
63 | (16) |
|
|
63 | (1) |
|
|
64 | (6) |
|
The Efficiency of Selection Sort |
|
|
70 | (1) |
|
|
71 | (1) |
|
|
72 | (4) |
|
|
76 | (1) |
|
|
76 | (3) |
|
6 Optimizing for Optimistic Scenarios |
|
|
79 | (16) |
|
|
79 | (1) |
|
|
80 | (6) |
|
The Efficiency of Insertion Sort |
|
|
86 | (2) |
|
|
88 | (3) |
|
|
91 | (2) |
|
|
93 | (1) |
|
|
93 | (2) |
|
|
95 | (18) |
|
Mean Average of Even Numbers |
|
|
95 | (2) |
|
|
97 | (2) |
|
|
99 | (1) |
|
|
100 | (1) |
|
|
101 | (1) |
|
|
102 | (1) |
|
|
102 | (1) |
|
|
103 | (4) |
|
|
107 | (2) |
|
|
109 | (1) |
|
|
109 | (4) |
|
8 Blazing Fast Lookup with Hash Tables |
|
|
113 | (20) |
|
|
113 | (1) |
|
Hashing with Hash Functions |
|
|
114 | (1) |
|
Building a Thesaurus for Fun and Profit, but Mainly Profit |
|
|
115 | (2) |
|
|
117 | (2) |
|
|
119 | (3) |
|
Making an Efficient Hash Table |
|
|
122 | (2) |
|
Hash Tables for Organization |
|
|
124 | (1) |
|
|
125 | (5) |
|
|
130 | (1) |
|
|
131 | (2) |
|
9 Crafting Elegant Code with Stacks and Queues |
|
|
133 | (16) |
|
|
133 | (3) |
|
|
136 | (1) |
|
|
137 | (6) |
|
The Importance of Constrained Data Structures |
|
|
143 | (1) |
|
|
144 | (2) |
|
|
146 | (1) |
|
|
147 | (1) |
|
|
148 | (1) |
|
10 Recursively Recurse with Recursion |
|
|
149 | (12) |
|
|
149 | (2) |
|
|
151 | (1) |
|
|
151 | (3) |
|
Recursion in the Eyes of the Computer |
|
|
154 | (2) |
|
|
156 | (3) |
|
|
159 | (1) |
|
|
159 | (2) |
|
11 Learning to Write in Recursive |
|
|
161 | (22) |
|
Recursive Category: Repeatedly Execute |
|
|
161 | (5) |
|
Recursive Category: Calculations |
|
|
166 | (2) |
|
Top-Down Recursion: A New Way of Thinking |
|
|
168 | (5) |
|
|
173 | (4) |
|
|
177 | (4) |
|
|
181 | (1) |
|
|
181 | (2) |
|
|
183 | (16) |
|
Unnecessary Recursive Calls |
|
|
183 | (4) |
|
|
187 | (1) |
|
The Efficiency of Recursion |
|
|
188 | (1) |
|
|
189 | (2) |
|
Dynamic Programming through Memoization |
|
|
191 | (3) |
|
Dynamic Programming through Going Bottom-Up |
|
|
194 | (2) |
|
|
196 | (1) |
|
|
197 | (2) |
|
13 Recursive Algorithms for Speed |
|
|
199 | (26) |
|
|
199 | (6) |
|
|
205 | (6) |
|
The Efficiency of Quicksort |
|
|
211 | (5) |
|
Quicksort in the Worst-Case Scenario |
|
|
216 | (2) |
|
|
218 | (4) |
|
Sorting as a Key to Other Algorithms |
|
|
222 | (1) |
|
|
223 | (1) |
|
|
224 | (1) |
|
14 Node-Based Data Structures |
|
|
225 | (22) |
|
|
225 | (2) |
|
Implementing a Linked List |
|
|
227 | (2) |
|
|
229 | (2) |
|
|
231 | (1) |
|
|
232 | (4) |
|
|
236 | (2) |
|
Efficiency of Linked List Operations |
|
|
238 | (1) |
|
|
239 | (1) |
|
|
240 | (2) |
|
Queues as Doubly Linked Lists |
|
|
242 | (2) |
|
|
244 | (1) |
|
|
244 | (3) |
|
15 Speeding Up All the Things with Binary Search Trees |
|
|
247 | (32) |
|
|
248 | (2) |
|
|
250 | (1) |
|
|
251 | (5) |
|
|
256 | (4) |
|
|
260 | (11) |
|
Binary Search Trees in Action |
|
|
271 | (1) |
|
Binary Search Tree Traversal |
|
|
272 | (4) |
|
|
276 | (1) |
|
|
276 | (3) |
|
16 Keeping Your Priorities Straight with Heaps |
|
|
279 | (26) |
|
|
279 | (2) |
|
|
281 | (3) |
|
|
284 | (1) |
|
|
285 | (2) |
|
Looking for the Last Node |
|
|
287 | (1) |
|
|
288 | (4) |
|
|
292 | (1) |
|
The Problem of the Last Node...Again |
|
|
293 | (2) |
|
|
295 | (7) |
|
|
302 | (1) |
|
|
302 | (1) |
|
|
303 | (2) |
|
17 It Doesn't Hurt to Trie |
|
|
305 | (26) |
|
|
306 | (1) |
|
|
307 | (4) |
|
|
311 | (4) |
|
The Efficiency of Trie Search |
|
|
315 | (1) |
|
|
316 | (4) |
|
|
320 | (6) |
|
|
326 | (1) |
|
Tries with Values: A Better Autocomplete |
|
|
327 | (1) |
|
|
328 | (1) |
|
|
329 | (2) |
|
18 Connecting Everything with Graphs |
|
|
331 | (56) |
|
|
332 | (2) |
|
|
334 | (1) |
|
Object-Oriented Graph Implementation |
|
|
334 | (3) |
|
|
337 | (2) |
|
|
339 | (9) |
|
|
348 | (13) |
|
The Efficiency of Graph Search |
|
|
361 | (3) |
|
|
364 | (3) |
|
|
367 | (17) |
|
|
384 | (1) |
|
|
384 | (3) |
|
19 Dealing with Space Constraints |
|
|
387 | (10) |
|
Big O of Space Complexity |
|
|
387 | (3) |
|
Trade-Offs Between Time and Space |
|
|
390 | (3) |
|
The Hidden Cost of Recursion |
|
|
393 | (2) |
|
|
395 | (1) |
|
|
395 | (2) |
|
20 Techniques for Code Optimization |
|
|
397 | (42) |
|
Prerequisite: Determine Your Current Big O |
|
|
397 | (1) |
|
Start Here: The Best-Imaginable Big O |
|
|
397 | (2) |
|
|
399 | (7) |
|
|
406 | (8) |
|
|
414 | (13) |
|
Change the Data Structure |
|
|
427 | (6) |
|
|
433 | (1) |
|
|
433 | (1) |
|
|
434 | (5) |
|
|
439 | (36) |
|
|
439 | (1) |
|
|
440 | (1) |
|
|
440 | (1) |
|
|
441 | (1) |
|
|
442 | (1) |
|
|
442 | (1) |
|
|
443 | (1) |
|
|
444 | (2) |
|
|
446 | (1) |
|
|
447 | (1) |
|
|
448 | (2) |
|
|
450 | (1) |
|
|
451 | (2) |
|
|
453 | (3) |
|
|
456 | (2) |
|
|
458 | (1) |
|
|
459 | (2) |
|
|
461 | (3) |
|
|
464 | (1) |
|
|
465 | (10) |
Index |
|
475 | |