Sammie Bae
JavaScript Data Structures and AlgorithmsAn Introduction to Understanding and Implementing Core Data Structure and Algorithm Fundamentals
Sammie Bae
Hamilton, ON, Canada
ISBN 978-1-4842-3987-2e-ISBN 978-1-4842-3988-9
https://doi.org/10.1007/978-1-4842-3988-9
Library of Congress Control Number: 2019930417
© Sammie Bae 2019
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.
Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein.
Distributed to the book trade worldwide by Springer Science+Business Media New York, 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer-sbm.com, or visit www.springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation.

This book is dedicated to Dr. Hamid R. Tizhoosh for inspiring me in my studies and to my mother, Min Kyoung Seo, for her kindness and support.

Introduction

The motivation for writing this book was the lack of resources available about data structures and algorithms written in JavaScript. This was strange to me because today many of the job opportunities for software development require knowledge of JavaScript; it is the only language that can be used to write the entire stack, including the front-end, mobile (native and hybrid) platforms, and back-end. It is crucial for JavaScript developers to understand how data structures work and how to design algorithms to build applications.

Therefore, this book aims to teach data structure and algorithm concepts from computer science for JavaScript rather than for the more typical Java or C++. Because JavaScript follows the prototypal inheritance pattern, unlike Java and C++ (which follow the inheritance pattern), there are some changes in writing data structures in JavaScript. The classical inheritance pattern allows inheritance by creating a blueprint-like form that objects follow during inheritance. However, the prototypal inheritance pattern means copying the objects and changing their properties.

This book first covers fundamental mathematics for Big-O analysis and then lays out the basic JavaScript foundations, such as primitive objects and types. Then, this book covers implementations and algorithms for fundamental data structures such as linked lists, stacks, trees, heaps, and graphs. Finally, more advanced topics such as efficient string search algorithms, caching algorithms, and dynamic programming problems are explored in great detail.

Acknowledgments

Thank you, Phil Nash, for the valuable feedback that helped me improve the technical content of this book with clear explanations and concise code.

Special thanks to the Apress team. This includes James Markham, Nancy Chen, Jade Scard, and Chris Nelson. Finally, I want to thank Steve Anglin for reaching out to me to publish with Apress.

Table of Contents

Chapter 1:​ Big-O Notation 1
Big-O Notation Primer 1
Common Examples 2
Rules of Big-O Notation 4
Coefficient Rule:​ “Get Rid of Constants” 5
Sum Rule:​ “Add Big-Os Up” 6
Product Rule:​ “Multiply Big-Os” 7
Polynomial Rule:​ “Big-O to the Power of k” 8
Summary 8
Exercises 9
Answers 11
Chapter 2:​ JavaScript:​ Unique Parts 13
JavaScript Scope 13
Global Declaration:​ Global Scope 13
Declaration with var:​ Functional Scope 13
Declaration with let:​ Block Scope 15
Equality and Types 16
Variable Types 16
Truthy/​Falsey Check 17
=​=​=​ vs =​=​ 18
Objects 18
Summary 20
Chapter 3:​ JavaScript Numbers 21
Number System 21
JavaScript Number Object 23
Integer Rounding 23
Number.​EPSILON 24
Maximums 24
Minimums 25
Size Summary 26
Number Algorithms 26
Prime Factorization 28
Random Number Generator 29
Exercises 29
Summary 34
Chapter 4:​ JavaScript Strings 35
JavaScript String Primitive 35
String Access 35
String Comparison 36
String Search 36
String Decomposition 38
String Replace 38
Regular Expressions 38
Basic Regex 39
Commonly Used Regexes 39
Encoding 41
Base64 Encoding 42
String Shortening 43
Encryption 45
RSA Encryption 46
Summary 50
Chapter 5:​ JavaScript Arrays 53
Introducing Arrays 53
Insertion 53
Deletion 54
Access 54
Iteration 54
for (Variables; Condition; Modification) 55
for ( in ) 56
for ( of ) 56
forEach( ) 56
Helper Functions 57
.​slice(begin,end) 57
.​splice(begin,size,element1,element2…) 58
.​concat() 59
.​length Property 59
Spread Operator 60
Exercises 60
JavaScript Functional Array Methods 67
Map 67
Filter 68
Reduce 68
Multidimensional​ Arrays 68
Exercises 71
Summary 81
Chapter 6:​ JavaScript Objects 83
JavaScript Object Property 83
Prototypal Inheritance 84
Constructor and Variables 85
Summary 86
Exercises 87
Chapter 7:​ JavaScript Memory Management 89
Memory Leaks 89
Reference to an Object 89
Leaking DOM 90
Global window Object 91
Limiting Object References 92
The delete Operator 92
Summary 93
Exercises 93
Chapter 8:​ Recursion 99
Introducing Recursion 99
Rules of Recursion 100
Base Case 100
Divide-and-Conquer Method 101
Classic Example:​ Fibonacci Sequence 101
Fibonacci Sequence:​ Tail Recursion 102
Pascal’s Triangle 103
Big-O for Recursion 105
Recurrence Relations 105
Master Theorem 106
Recursive Call Stack Memory 107
Summary 109
Exercises 109
Chapter 9:​ Sets 117
Introducing Sets 117
Set Operations 117
Insertion 118
Deletion 118
Contains 118
Other Utility Functions 119
Intersection 119
isSuperSet 119
Union 120
Difference 120
Summary 121
Exercises 122
Chapter 10:​ Searching and Sorting 125
Searching 125
Linear Search 125
Binary Search 127
Sorting 129
Bubble Sort 129
Selection Sort 131
Insertion Sort 132
Quicksort 134
Quickselect 137
Mergesort 138
Count Sort 140
JavaScript’s Built-in Sort 141
Summary 142
Exercises 143
Chapter 11:​ Hash Tables 151
Introducing Hash Tables 151
Hashing Techniques 152
Prime Number Hashing 152
Probing 154
Rehashing/​Double-Hashing 155
Hash Table Implementation 156
Using Linear Probing 156
Using Quadratic Probing 158
Using Double-Hashing with Linear Probing 160
Summary 161
Chapter 12:​ Stacks and Queues 163
Stacks 163
Peek 165
Insertion 165
Deletion 166
Access 166
Search 167
Queues 167
Peek 169
Insertion 169
Deletion 169
Access 170
Search 171
Summary 171
Exercises 172
Chapter 13:​ Linked Lists 179
Singly Linked Lists 179
Insertion 180
Deletion by Value 181
Deletion at the Head 182
Search 183
Doubly Linked Lists 184
Insertion at the Head 185
Insertion at the Tail 185
Deletion at the Head 186
Deletion at the Tail 187
Search 188
Summary 189
Exercises 190
Chapter 14:​ Caching 193
Understanding Caching 193
Least Frequently Used Caching 194
Least Recently Used Caching 199
Summary 203
Chapter 15:​ Trees 205
General Tree Structure 205
Binary Trees 206
Tree Traversal 207
Pre-order Traversal 207
In-Order Traversal 209
Post-order Traversal 211
Level-Order Traversal 212
Tree Traversal Summary 214
Binary Search Trees 214
Insertion 216
Deletion 218
Search 220
AVL Trees 221
Single Rotation 221
Double Rotation 225
Balancing the Tree 228
Insertion 229
Putting It All Together:​ AVL Tree Example 231
Summary 234
Exercises 234
Chapter 16:​ Heaps 245
Understanding Heaps 245
Max-Heap 246
Min-Heap 247
Binary Heap Array Index Structure 248
Percolation:​ Bubbling Up and Down 250
Implementing Percolation 253
Max-Heap Example 254
Min-Heap Complete Implementation 258
Max-Heap Complete Implementation 259
Heap Sort 261
Ascending-Order Sort (Min-Heap) 261
Descending-Order Sort (Max-Heap) 264
Summary 267
Exercises 268
Chapter 17:​ Graphs 273
Graph Basics 273
Undirected Graphs 277
Adding Edges and Vertices 279
Removing Edges and Vertices 280
Directed Graphs 282
Graph Traversal 285
Breadth-First Search 286
Depth-First Search 289
Weighted Graphs and Shortest Path 293
Graphs with Weighted Edges 293
Dijkstra’s Algorithm:​ Shortest Path 294
Topological Sort 298
Summary 300
Chapter 18:​ Advanced Strings 303
Trie (Prefix Tree) 303
Boyer–Moore String Search 307
Knuth–Morris–Pratt String Search 311
Rabin–Karp Search 316
The Rabin Fingerprint 316
Applications in Real Life 319
Summary 320
Chapter 19:​ Dynamic Programming 321
Motivations for Dynamic Programming 321
Rules of Dynamic Programming 323
Overlapping Subproblems 323
Optimal Substructure 323
Example:​ Ways to Cover Steps 323
Classical Dynamic Programming Examples 325
The Knapsack Problem 325
Longest Common Subsequence 328
Coin Change 330
Edit (Levenshtein) Distance 334
Summary 338
Chapter 20:​ Bit Manipulation 339
Bitwise Operators 339
AND 340
OR 340
XOR 341
NOT 341
Left Shift 342
Right Shift 342
Zero-Fill Right Shift 343
Number Operations 343
Addition 343
Subtraction 344
Multiplication 345
Division 347
Summary 349
Index 351

About the Author and About the Technical Reviewer

About the Author

Sammie Bae
../images/465726_1_En_BookFrontmatter_Figb_HTML.jpg

is a data engineer at Yelp and previously worked for the data platform engineering team at NVIDIA. He developed a deep interest in JavaScript during an internship at SMART Technologies (acquired by Foxconn), where he developed Node.js-based JavaScript APIs for serial port communication between electronic board drivers and a web application. Despite how relevant JavaScript is to the modern software engineering industry, currently no books besides this one teach algorithms and data structures using JavaScript. Sammie understands how difficult these computer science concepts are and aims to provide clear and concise explanations in this book.

 

About the Technical Reviewer

Phil Nash
../images/465726_1_En_BookFrontmatter_Figc_HTML.jpg

is a developer evangelist for Twilio, serving developer communities in London and all over the world. He is a Ruby, JavaScript, and Swift developer; Google Developers Expert; blogger; speaker; and occasional brewer. He can be found hanging out at meetups and conferences, playing with new technologies and APIs, or writing open source code.