Description
Book SynopsisKirupa Chinnathambi has spent most of his life teaching others to love web development as much as he does. He founded KIRUPA, one of the Web's most popular free web development education resources, serving 210,000+ registered members. Now a product manager at Google, he has authored several books, including Learning React (2017). He holds a B.S. in computer science from MIT.
Table of ContentsPart 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
