Data Structures and Algorithms in JavaScript

Not the Same Old JavaScript. Think you know JavaScript? Think again. This isn’t your typical coding book—it’s a deep dive into the powerful world of data structures and algorithms that will transform the way you approach problem solving in JavaScript. Whether you’re a frontend developer tackling complex applications, a backend engineer building scalable systems, or a programmer preparing for technical interviews, this book will revolutionize the way you code. Key features include: Modern JavaScript techniques: Use the latest language features and functional programming principles for cleaner, more efficient code. Performance-focused approach: Analyze and optimize algorithms using Big O notation. Essential algorithms explained: Implement and fine-tune core algorithms like quicksort, merge sort, digital search, and binary search. Algorithm design strategies: Solve challenging problems with techniques like recursion, dynamic programming, backtracking, and brute-force search. Advanced data structures: Explore complex structures such as binary search trees, heaps, and graphs. Each chapter is carefully crafted with clear, no-nonsense explanations of complex concepts, real-world coding examples, and challenging questions (with answers at the end) to reinforce your understanding. Ready to break free from ordinary JavaScript? Whether your aim is to build cutting-edge web applications, optimize critical systems, or land your dream job, this book equips you with the advanced JavaScript knowledge that sets true experts apart. Cover Praise for Data Structures and Algorithms in Javascript Title Page Copyright Dedication About the Author About the Technical Reviewer Brief Contents Contents in Detail Preface Acknowledgments Introduction Who Should Read This Book? What’s the Book’s Approach? What’s in the Book? Part I: The Basics 1. Using Javascript Modern JavaScript Features Arrow Functions Classes The Spread Operator The Destructuring Statement Modules Closures and Immediately Invoked Function Expressions JavaScript Development Tools Visual Studio Code Fira Code Font Prettier Formatting JSDoc Documentation ESLint Flow and TypeScript Online Feature Availability Resources Summary 2. Functional Programming in Javascript Why Use Functional Programming? JavaScript as a Functional Language Functions as First-Class Objects Declarative-Style Programming Higher-Order Functions Side Effects Impure Functions Summary Questions 3. Abstract Data Types The Theory Data Types Abstraction Operations and Mutations Implementing an ADT Implementing ADTs Using Classes Implementing ADTs Using Functions (Mutable Version) Implementing ADTs Using Functions (Immutable Version) Summary Questions 4. Analyzing Algorithms Performance Complexity Notations for Complexity Complexity Classes Performance Measurements Analysis of Algorithms in Practice Time and Space Complexity Trade-offs Summary Questions Part II: Algorithms 5. Designing Algorithms Recursion The Divide-and-Conquer Strategy The Backtracking Technique Dynamic Programming Calculating Fibonacci Series with Top-Down DP Line Breaking with Top-Down DP Calculating Fibonacci Series with Bottom-Up DP Summing Ranges Recursively with Bottom-Up DP Summing Ranges by Precomputing with Bottom-Up DP Brute-Force Search Detecting Tautologies Solving Cryptarithmetic Puzzles Greedy Algorithms How to Make Change The Traveling Salesman Problem Minimum Spanning Tree Summary Questions 6. Sorting The Sorting Problem Internal vs. External Sorting Adaptive Sorting In-Place and Out-of-Place Sorting Online and Offline Sorting Sorting Stability JavaScript’s Own Sort Method Sort Performance Sorting with Comparisons Bubbling Up and Down Sorting Strategies for Playing Cards Making Bigger Jumps with Comb and Shell Sort Going for Speed with Quicksort Merging for Performance with Merge Sort Sorting Without Comparisons Bitmap Sort Counting Sort Radix Sort Inefficient Sorting Algorithms Stooge Sort Slow Sort Permutation Sort Bogosort Sleep Sort Summary Questions 7. Selecting Selection Without Comparisons Bitmap Selection Counting Selection Selecting with Comparisons The Quickselect Family Quickselect Median of Medians Repeated Step Finding the Median with Lazy Select Summary Questions 8. Shuffling and Sampling Choosing Numbers Randomly Shuffling Shuffling by Sorting Shuffling by Coin Tossing Shuffling in Linear Time Sampling Sampling with Repetition Sampling Without Repetition Summary Questions 9. Searching Search Definition Searching Unsorted Arrays JavaScript’s Methods Linear Search Linear Search with Sentinels Searching Ordered Arrays Jump Search Binary Search Exponential Search Interpolation Search Summary Questions Part III: Data Structures 10. Lists Basic Lists Implementing Lists with Arrays Implementing Lists with Dynamic Memory Varieties of Lists Stacks Queues Deques Circular Lists Summary Questions 11. Bags, Sets, and Maps Introducing Bags, Sets, and Maps JavaScript’s Solutions for Sets Objects as Sets Set Objects Bitmaps Using Lists Ordered Lists Skip Lists Self-Organizing Lists Hashing Hashing with Chaining Hashing with Open Addressing Double Hashing Double Hashing with Prime Lengths Summary Questions 12. Binary Trees What Are Trees? General Trees Binary Trees Binary Search Trees Assured Balanced Binary Search Trees AVL Trees Weight-Bounded Balanced Trees Probabilistic Balance Binary Search Trees Randomized Binary Search Trees Splay Trees Summary Questions 13. Trees and Forests Defining Trees and Forests Representing Trees with Arrays Representing Trees with Binary Trees Representing Forests Traversing Trees B-trees Defining B-trees Finding a Key in a B-tree Traversing a B-tree Adding a Key to a B-tree Removing a Key from a B-tree Considering Performance for B-trees Red-Black Trees Representing Red-Black Trees Adding a Key to a Red-Black Tree Restoring a Red-Black Tree Structure Removing a Key from a Red-Black Tree Considering Performance for Red-Black Trees Summary Questions 14. Heaps Binary Heaps The Structure Property The Heap Property Heap Implementation Priority Queues and Heaps Heapsort Williams’ Original Heapsort Heapsort Analysis Floyd’s Heap-Building Enhancement Treaps Creating and Searching a Treap Adding a Key to a Treap Removing a Key from a Treap Considering the Performance of Treaps Ternary and D-ary Heaps Summary Questions 15. Extended Heaps Meldable and Addressable Priority Queues Skew Heaps Representing a Skew Heap Merging Two Skew Heaps Adding a Key to a Skew Heap Removing the Top Key from a Skew Heap Considering Performance for Skew Heaps Binomial Heaps Binomial Trees Defining Binomial Heaps Adding a Value to a Binomial Heap Merging Two Binomial Heaps Removing a Value from a Binomial Heap Changing a Value in a Binomial Heap Considering Performance for Binomial Heaps Lazy Binomial Heaps Defining Lazy Binomial Heaps Adding a Value to a Lazy Binomial Heap Removing a Value from a Lazy Binomial Heap Changing a Value in a Lazy Binomial Heap Considering Performance for Lazy Binomial Heaps Fibonacci Heaps Representing a Fibonacci Heap Merging Two Fibonacci Trees Adding a Value to a Fibonacci Heap Removing a Value from a Fibonacci Heap Changing a Value in a Fibonacci Heap Considering Performance for Fibonacci Heaps Pairing Heaps Defining a Pairing Heap Melding Two Pairing Heaps Adding a Value to a Pairing Heap Removing the Top Value from a Pairing Heap Changing a Value in a Pairing Heap Considering Performance for Pairing Heaps Summary Questions 16. Digital Search Trees The Classic Version of Tries Storing Extra Data in a Trie Searching a Trie Adding a Key to a Trie Removing a Key from a Trie Considering Performance for Tries An Enhanced Version of Tries Defining an Object-Based Trie Searching an Object-Based Trie Adding a Key to an Object-Based Trie Removing a Key from an Object-Based Trie Considering Performance for Object-Based Tries Radix Trees Defining a Radix Tree Searching a Radix Tree Adding a Key to a Radix Tree Removing a Key from a Radix Tree Considering Performance for Radix Trees Ternary Search Tries Defining Ternary Tries Storing Extra Data in a Ternary Trie Searching a Ternary Trie Adding a Key to a Ternary Trie Removing a Key from a Ternary Trie Considering Performance for Ternary Tries Summary Questions 17. Graphs What Are Graphs? Representing Graphs Adjacency Matrix Representation for Graphs Adjacency List Representation for Graphs Adjacency Set Representation for Graphs Finding the Shortest Paths Floyd-Warshall’s “All Paths” Algorithm Bellman-Ford Algorithm Dijkstra’s Algorithm Sorting a Graph Kahn’s Algorithm Tarjan’s Algorithm Detecting Cycles Detecting Connectivity Detecting Connectivity with Sets Detecting Connectivity with Searches Finding a Minimum Spanning Tree Prim’s Algorithm Kruskal’s Algorithm Summary Questions 18. Immutability and Functional Data Structures Functional Data Structures Arrays (and Hash Tables Functional Lists Functional Trees Summary Questions Answer Key Bibliography Index Back Cover This book addresses one of the most glaring gaps in JavaScript developers’ knowledge base—basic computer science concepts, like data structures and algorithms, for solving complex problems.For JavaScript developers, this book is a one-stop-shop for learning the algorithms and data structures that solve and optimize complex problems—covering everything from functional programming and abstract data types, to sorting and searching, lists, bags, binary trees, forests, heaps, and graphs. The author’s use of examples taken from coding challenges and programming interviews enables you to explore the real-world advantages of specific algorithms and data structures.Written and illustrated to be a developer’s go-to reference manual for immediate on-the-job applications, performance—both from a theoretical point of view and a practical standpoint—is emphasized alongside every algorithm or data structure introduced. In addition to demonstrating best practices throughout the text, each chapter ends with a series of questions and examples that clarify the preceding concepts. The book utilizes the latest version of JavaScript (ECMAScript) and its more modern features wherever appropriate. This book addresses one of the most glaring gaps in JavaScript developers knowledge basebasic computer science concepts, like data structures and algorithms, for solving complex problems. For JavaScript developers, this book is a one-stop-shop for learning the algorithms and data structures that solve and optimize complex problemscovering everything from functional programming and abstract data types, to sorting and searching, lists, bags, binary trees, forests, heaps, and graphs. The authors use of examples taken from coding challenges and programming interviews enables you to explore the real-world advantages of specific algorithms and data structures.Written and illustrated to be a developers go-to reference manual for immediate on-the-job applications, performanceboth from a theoretical point of view and a practical standpointis emphasized alongside every algorithm or data structure introduced. In addition to demonstrating best practices throughout the text, each chapter ends with a series of questions and examples that clarify the preceding concepts. The book utilizes the latest version of JavaScript (ECMAScript) and its more modern features wherever appropriate.