Data Structures and Algorithms in Javascript: Optimizing perfomance and solving programming challenges

Cover....1

Praise for Data Structures and Algorithms in Javascript....3

Title Page....7

Copyright....8

Dedication....9

About the Author....11

About the Technical Reviewer....11

Brief Contents....13

Contents in Detail....15

Preface....23

Acknowledgments....25

Introduction....27

Who Should Read This Book?....28

Whats the Books Approach?....28

Whats in the Book?....28

Part I: The Basics....33

1. Using Javascript....35

Modern JavaScript Features....36

Arrow Functions....36

Classes....37

The Spread Operator....38

The Destructuring Statement....39

Modules....40

Closures and Immediately Invoked Function Expressions....43

JavaScript Development Tools....45

Visual Studio Code....45

Fira Code Font....47

Prettier Formatting....48

JSDoc Documentation....48

ESLint....50

Flow and TypeScript....50

Online Feature Availability Resources....51

Summary....53

2. Functional Programming in Javascript....55

Why Use Functional Programming?....56

JavaScript as a Functional Language....57

Functions as First-Class Objects....57

Declarative-Style Programming....58

Higher-Order Functions....62

Side Effects....64

Impure Functions....65

Summary....67

Questions....67

3. Abstract Data Types....69

The Theory....70

Data Types....70

Abstraction....71

Operations and Mutations....71

Implementing an ADT....72

Implementing ADTs Using Classes....73

Implementing ADTs Using Functions (Mutable Version)....75

Implementing ADTs Using Functions (Immutable Version)....77

Summary....78

Questions....78

4. Analyzing Algorithms....81

Performance....82

Complexity....82

Notations for Complexity....83

Complexity Classes....84

Performance Measurements....86

Analysis of Algorithms in Practice....87

Time and Space Complexity Trade-offs....89

Summary....90

Questions....90

Part II: Algorithms....93

5. Designing Algorithms....95

Recursion....96

The Divide-and-Conquer Strategy....97

The Backtracking Technique....101

Dynamic Programming....104

Calculating Fibonacci Series with Top-Down DP....104

Line Breaking with Top-Down DP....106

Calculating Fibonacci Series with Bottom-Up DP....111

Summing Ranges Recursively with Bottom-Up DP....112

Summing Ranges by Precomputing with Bottom-Up DP....113

Brute-Force Search....114

Detecting Tautologies....114

Solving Cryptarithmetic Puzzles....115

Greedy Algorithms....119

How to Make Change....119

The Traveling Salesman Problem....119

Minimum Spanning Tree....120

Summary....120

Questions....120

6. Sorting....123

The Sorting Problem....124

Internal vs. External Sorting....124

Adaptive Sorting....124

In-Place and Out-of-Place Sorting....125

Online and Offline Sorting....125

Sorting Stability....125

JavaScripts Own Sort Method....127

Sort Performance....128

Sorting with Comparisons....129

Bubbling Up and Down....129

Sorting Strategies for Playing Cards....132

Making Bigger Jumps with Comb and Shell Sort....135

Going for Speed with Quicksort....137

Merging for Performance with Merge Sort....142

Sorting Without Comparisons....144

Bitmap Sort....144

Counting Sort....146

Radix Sort....147

Inefficient Sorting Algorithms....148

Stooge Sort....148

Slow Sort....148

Permutation Sort....149

Bogosort....149

Sleep Sort....149

Summary....149

Questions....150

7. Selecting....153

Selection Without Comparisons....154

Bitmap Selection....154

Counting Selection....155

Selecting with Comparisons....156

The Quickselect Family....157

Quickselect....158

Median of Medians....159

Repeated Step....162

Finding the Median with Lazy Select....164

Summary....166

Questions....166

8. Shuffling and Sampling....169

Choosing Numbers Randomly....170

Shuffling....171

Shuffling by Sorting....171

Shuffling by Coin Tossing....172

Shuffling in Linear Time....174

Sampling....178

Sampling with Repetition....178

Sampling Without Repetition....179

Summary....186

Questions....187

9. Searching....191

Search Definition....191

Searching Unsorted Arrays....192

JavaScripts Methods....192

Linear Search....192

Linear Search with Sentinels....193

Searching Ordered Arrays....195

Jump Search....195

Binary Search....198

Exponential Search....200

Interpolation Search....201

Summary....203

Questions....204

Part III: Data Structures....207

10. Lists....209

Basic Lists....210

Implementing Lists with Arrays....211

Implementing Lists with Dynamic Memory....212

Varieties of Lists....216

Stacks....216

Queues....220

Deques....223

Circular Lists....227

Summary....232

Questions....232

11. Bags, Sets, and Maps....235

Introducing Bags, Sets, and Maps....235

JavaScripts Solutions for Sets....237

Objects as Sets....237

Set Objects....238

Bitmaps....238

Using Lists....239

Ordered Lists....239

Skip Lists....242

Self-Organizing Lists....247

Hashing....250

Hashing with Chaining....251

Hashing with Open Addressing....253

Double Hashing....258

Double Hashing with Prime Lengths....261

Summary....264

Questions....264

12. Binary Trees....267

What Are Trees?....268

General Trees....269

Binary Trees....269

Binary Search Trees....271

Assured Balanced Binary Search Trees....281

AVL Trees....281

Weight-Bounded Balanced Trees....287

Probabilistic Balance Binary Search Trees....293

Randomized Binary Search Trees....294

Splay Trees....302

Summary....310

Questions....311

13. Trees and Forests....315

Defining Trees and Forests....315

Representing Trees with Arrays....316

Representing Trees with Binary Trees....319

Representing Forests....320

Traversing Trees....320

B-trees....323

Defining B-trees....324

Finding a Key in a B-tree....325

Traversing a B-tree....326

Adding a Key to a B-tree....327

Removing a Key from a B-tree....330

Considering Performance for B-trees....335

Red-Black Trees....336

Representing Red-Black Trees....337

Adding a Key to a Red-Black Tree....338

Restoring a Red-Black Tree Structure....339

Removing a Key from a Red-Black Tree....341

Considering Performance for Red-Black Trees....345

Summary....346

Questions....346

14. Heaps....349

Binary Heaps....350

The Structure Property....350

The Heap Property....351

Heap Implementation....352

Priority Queues and Heaps....358

Heapsort....359

Williams Original Heapsort....359

Heapsort Analysis....361

Floyds Heap-Building Enhancement....361

Treaps....364

Creating and Searching a Treap....364

Adding a Key to a Treap....365

Removing a Key from a Treap....368

Considering the Performance of Treaps....371

Ternary and D-ary Heaps....372

Summary....373

Questions....373

15. Extended Heaps....377

Meldable and Addressable Priority Queues....378

Skew Heaps....379

Representing a Skew Heap....380

Merging Two Skew Heaps....380

Adding a Key to a Skew Heap....382

Removing the Top Key from a Skew Heap....382

Considering Performance for Skew Heaps....382

Binomial Heaps....383

Binomial Trees....383

Defining Binomial Heaps....385

Adding a Value to a Binomial Heap....386

Merging Two Binomial Heaps....388

Removing a Value from a Binomial Heap....390

Changing a Value in a Binomial Heap....392

Considering Performance for Binomial Heaps....394

Lazy Binomial Heaps....395

Defining Lazy Binomial Heaps....395

Adding a Value to a Lazy Binomial Heap....396

Removing a Value from a Lazy Binomial Heap....397

Changing a Value in a Lazy Binomial Heap....398

Considering Performance for Lazy Binomial Heaps....399

Fibonacci Heaps....399

Representing a Fibonacci Heap....400

Merging Two Fibonacci Trees....402

Adding a Value to a Fibonacci Heap....403

Removing a Value from a Fibonacci Heap....403

Changing a Value in a Fibonacci Heap....404

Considering Performance for Fibonacci Heaps....407

Pairing Heaps....408

Defining a Pairing Heap....409

Melding Two Pairing Heaps....409

Adding a Value to a Pairing Heap....410

Removing the Top Value from a Pairing Heap....410

Changing a Value in a Pairing Heap....414

Considering Performance for Pairing Heaps....416

Summary....417

Questions....417

16. Digital Search Trees....419

The Classic Version of Tries....420

Storing Extra Data in a Trie....422

Searching a Trie....422

Adding a Key to a Trie....426

Removing a Key from a Trie....429

Considering Performance for Tries....433

An Enhanced Version of Tries....433

Defining an Object-Based Trie....434

Searching an Object-Based Trie....434

Adding a Key to an Object-Based Trie....436

Removing a Key from an Object-Based Trie....437

Considering Performance for Object-Based Tries....438

Radix Trees....438

Defining a Radix Tree....439

Searching a Radix Tree....439

Adding a Key to a Radix Tree....442

Removing a Key from a Radix Tree....444

Considering Performance for Radix Trees....446

Ternary Search Tries....446

Defining Ternary Tries....447

Storing Extra Data in a Ternary Trie....448

Searching a Ternary Trie....448

Adding a Key to a Ternary Trie....449

Removing a Key from a Ternary Trie....451

Considering Performance for Ternary Tries....455

Summary....456

Questions....456

17. Graphs....457

What Are Graphs?....457

Representing Graphs....460

Adjacency Matrix Representation for Graphs....460

Adjacency List Representation for Graphs....461

Adjacency Set Representation for Graphs....462

Finding the Shortest Paths....462

Floyd-Warshalls All Paths Algorithm....462

Bellman-Ford Algorithm....466

Dijkstras Algorithm....470

Sorting a Graph....476

Kahns Algorithm....477

Tarjans Algorithm....480

Detecting Cycles....484

Detecting Connectivity....485

Detecting Connectivity with Sets....486

Detecting Connectivity with Searches....488

Finding a Minimum Spanning Tree....490

Prims Algorithm....491

Kruskals Algorithm....494

Summary....498

Questions....498

18. Immutability and Functional Data Structures....501

Functional Data Structures....502

Arrays (and Hash Tables....502

Functional Lists....502

Functional Trees....510

Summary....517

Questions....517

Answer Key....519

Bibliography....577

Index....581

Back Cover....595

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.