Part I: Data Structures
Chapter 1. Introduction to Data Structures .................................................................. 1
Right Tool for the Right Job .................................................................................... 2
Back to Data Structures ........................................................................................... 5
Conclusion ................................................................................................................. 6
Chapter 2. Big-O Notation and Complexity Analysis ................................................... 7
It's Example Time ...................................................................................................... 8
It's Big-O Notation Time! .......................................................................................11
Conclusion ...............................................................................................................15
Chapter 3. Arrays ....................................................................................................... 17
What Is an Array? ....................................................................................................18
Array Implementation / Use Cases .......................................................................24
Arrays and Memory ................................................................................................26
Performance Considerations .................................................................................30
Conclusion ...............................................................................................................32
Chapter 4. Linked Lists ............................................................................................... 35
Meet the Linked List ...............................................................................................36
Linked List: Time and Space Complexity .............................................................40
Linked List Variations ..............................................................................................41
Implementation .......................................................................................................44
Conclusion ...............................................................................................................52
Chapter 5. Stacks ........................................................................................................ 53
Meet the Stack ........................................................................................................54
A JavaScript Implementation ................................................................................56
Stacks: Time and Space Complexity ....................................................................58
Conclusion ...............................................................................................................59
Chapter 6. Queues ..................................................................................................... 61
Meet the Queue .....................................................................................................62
A JavaScript Implementation ................................................................................64
Queues: Time and Space Complexity ..................................................................66
Conclusion ...............................................................................................................67
Chapter 7. Trees ......................................................................................................... 69
Trees 101 .................................................................................................................70
Height and Depth ...................................................................................................75
Conclusion ...............................................................................................................77
Chapter 8. Binary Trees .............................................................................................. 79
Meet the Binary Tree ..............................................................................................80
A Simple Binary Tree Implementation ..................................................................86
Conclusion ...............................................................................................................89
Chapter 9. Binary Search Trees ................................................................................... 91
It's Just a Data Structure ........................................................................................93
Implementing a Binary Search Tree ....................................................................103
Performance and Memory Characteristics .........................................................110
Conclusion .............................................................................................................112
Chapter 10. Heaps ...................................................................................................... 113
Meet the Heap ......................................................................................................114
Heap Implementation ..........................................................................................126
Performance Characteristics ................................................................................132
Conclusion .............................................................................................................134
Chapter 11. Hashtable (aka Hashmap or Dictionary) .................................................. 137
A Very Efficient Robot ..........................................................................................138
From Robots to Hashing Functions ....................................................................142
From Hashing Functions to Hashtables .............................................................145
JavaScript Implementation/Usage ......................................................................148
Dealing with Collisions .........................................................................................150
Performance and Memory ...................................................................................151
Conclusion .............................................................................................................153
Chapter 12. Trie (aka Prefix Tree) ............................................................................... 155
What Is a Trie? ......................................................................................................156
Diving Deeper into Tries ......................................................................................167
Many More Examples Abound! ..........................................................................172
Implementation Time ...........................................................................................173
Performance ..........................................................................................................179
Conclusion .............................................................................................................181
Chapter 13. Graphs .................................................................................................... 183
What Is a Graph? ..................................................................................................184
Graph Implementation .........................................................................................190
Conclusion .............................................................................................................196
Part II: Algorithms
Chapter 14. Introduction to Recursion ....................................................................... 199
Our Giant Cookie Problem ..................................................................................200
Recursion in Programming ..................................................................................202
Conclusion .............................................................................................................206
Chapter 15. Fibonacci and Going Beyond Recursion ................................................. 207
Recursively Solving the Fibonacci Sequence ....................................................209
Recursion with Memoization ...............................................................................213
Taking an Iteration-Based Approach ..................................................................215
Going Deeper on the Speed ..............................................................................217
Conclusion .............................................................................................................218
Chapter 16. Towers of Hanoi ...................................................................................... 221
How Towers of Hanoi Is Played ..........................................................................222
The Single Disk Case ...........................................................................................223
It's Two Disk Time .................................................................................................224
Three Disks ............................................................................................................225
The Algorithm .......................................................................................................228
The Code Solution ...............................................................................................229
Check Out the Recursiveness! ............................................................................231
It's Math Time ........................................................................................................232
Conclusion .............................................................................................................234
Chapter 17. Search Algorithms and Linear Search ..................................................... 235
Linear Search .........................................................................................................236
Conclusion .............................................................................................................241
Chapter 18. Faster Searching with Binary Search ....................................................... 243
Binary Search in Action ........................................................................................243
The JavaScript Implementation ..........................................................................250
Runtime Performance ...........................................................................................254
Conclusion .............................................................................................................257
Chapter 19. Binary Tree Traversal ............................................................................... 259
Breadth-First Traversal ..........................................................................................260
Depth-First Traversal ............................................................................................265
Implementing Our Traversal Approaches ..........................................................270
Performance of Our Traversal Approaches ........................................................278
Conclusion .............................................................................................................279
Chapter 20. Depth-First Search (DFS) and Breadth-First Search (BFS) ....................... 281
A Tale of Two Exploration Approaches ..............................................................282
It's Example Time ..................................................................................................285
When to Use DFS? When to Use BFS? ..............................................................298
A JavaScript Implementation ..............................................................................300
Performance Details .............................................................................................307
Conclusion .............................................................................................................308
Chapter 21. Quicksort ................................................................................................ 309
A Look at How Quicksort Works .........................................................................310
Another Simple Look ...........................................................................................314
It's Implementation Time .....................................................................................319
Performance Characteristics ................................................................................322
Conclusion .............................................................................................................323
Chapter 22. Bubblesort .............................................................................................. 325
How Bubblesort Works ........................................................................................326
Walkthrough ..........................................................................................................329
The Code ...............................................................................................................333
Conclusion .............................................................................................................333
Chapter 23. Insertion Sort .......................................................................................... 335
How Insertion Sort Works ....................................................................................336
One More Example ..............................................................................................347
Algorithm Overview and Implementation .........................................................349
Performance Analysis ...........................................................................................351
Conclusion .............................................................................................................353
Chapter 24. Selection Sort ......................................................................................... 355
Selection Sort Walkthrough .................................................................................356
Algorithm Deep Dive ...........................................................................................364
The JavaScript Implementation ..........................................................................366
Conclusion .............................................................................................................369
Chapter 25. Mergesort ............................................................................................... 371
How Mergesort Works .........................................................................................372
Mergesort: The Algorithm Details ......................................................................379
Looking at the Code ............................................................................................380
Conclusion .............................................................................................................381
Conclusion .................................................................................................................383
Index ............................................................................................................................ 387
