book

Data Structures and Algorithms in JavaScript

Name: Data Structures and Algorithms in JavaScript
Author: Federico Kereki
ISBN: 9781718502628

by Federico Kereki

January 2025

Intermediate to advanced

592 pages

15h 18m

English

No Starch Press

Read now

Unlock full access

Praise for Data Structures and Algorithms in Javascript
Title Page
Copyright
Dedication
About the Author and Technical Reviewer
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 FeaturesArrow FunctionsClassesThe Spread OperatorThe Destructuring StatementModulesClosures and Immediately Invoked Function ExpressionsJavaScript Development ToolsVisual Studio CodeFira Code FontPrettier FormattingJSDoc DocumentationESLintFlow and TypeScriptOnline Feature Availability ResourcesSummary

2. Functional Programming in Javascript
Why Use Functional Programming?JavaScript as a Functional LanguageFunctions as First-Class ObjectsDeclarative-Style ProgrammingHigher-Order FunctionsSide EffectsImpure FunctionsSummaryQuestions
3. Abstract Data Types
The TheoryData TypesAbstractionOperations and MutationsImplementing an ADTImplementing ADTs Using ClassesImplementing ADTs Using Functions (Mutable Version)Implementing ADTs Using Functions (Immutable Version)SummaryQuestions
4. Analyzing Algorithms
PerformanceComplexityNotations for ComplexityComplexity ClassesPerformance MeasurementsAnalysis of Algorithms in PracticeTime and Space Complexity Trade-offsSummaryQuestions
Part II: Algorithms
5. Designing Algorithms
RecursionThe Divide-and-Conquer StrategyThe Backtracking TechniqueDynamic ProgrammingCalculating Fibonacci Series with Top-Down DPLine Breaking with Top-Down DPCalculating Fibonacci Series with Bottom-Up DPSumming Ranges Recursively with Bottom-Up DPSumming Ranges by Precomputing with Bottom-Up DPBrute-Force SearchDetecting TautologiesSolving Cryptarithmetic PuzzlesGreedy AlgorithmsHow to Make ChangeThe Traveling Salesman ProblemMinimum Spanning TreeSummaryQuestions
6. Sorting
The Sorting ProblemInternal vs. External SortingAdaptive SortingIn-Place and Out-of-Place SortingOnline and Offline SortingSorting StabilityJavaScript’s Own Sort MethodSort PerformanceSorting with ComparisonsBubbling Up and DownSorting Strategies for Playing CardsMaking Bigger Jumps with Comb and Shell SortGoing for Speed with QuicksortMerging for Performance with Merge SortSorting Without ComparisonsBitmap SortCounting SortRadix SortInefficient Sorting AlgorithmsStooge SortSlow SortPermutation SortBogosortSleep SortSummaryQuestions
7. Selecting
Selection Without ComparisonsBitmap SelectionCounting SelectionSelecting with ComparisonsThe Quickselect FamilyQuickselectMedian of MediansRepeated StepFinding the Median with Lazy SelectSummaryQuestions
8. Shuffling and Sampling
Choosing Numbers RandomlyShufflingShuffling by SortingShuffling by Coin TossingShuffling in Linear TimeSamplingSampling with RepetitionSampling Without RepetitionSummaryQuestions
9. Searching
Search DefinitionSearching Unsorted ArraysJavaScript’s MethodsLinear SearchLinear Search with SentinelsSearching Ordered ArraysJump SearchBinary SearchExponential SearchInterpolation SearchSummaryQuestions
Part III: Data Structures
10. Lists
Basic ListsImplementing Lists with ArraysImplementing Lists with Dynamic MemoryVarieties of ListsStacksQueuesDequesCircular ListsSummaryQuestions
11. Bags, Sets, and Maps
Introducing Bags, Sets, and MapsJavaScript’s Solutions for SetsObjects as SetsSet ObjectsBitmapsUsing ListsOrdered ListsSkip ListsSelf-Organizing ListsHashingHashing with ChainingHashing with Open AddressingDouble HashingDouble Hashing with Prime LengthsSummaryQuestions
12. Binary Trees
What Are Trees?General TreesBinary TreesBinary Search TreesAssured Balanced Binary Search TreesAVL TreesWeight-Bounded Balanced TreesProbabilistic Balance Binary Search TreesRandomized Binary Search TreesSplay TreesSummaryQuestions
13. Trees and Forests
Defining Trees and ForestsRepresenting Trees with ArraysRepresenting Trees with Binary TreesRepresenting ForestsTraversing TreesB-treesDefining B-treesFinding a Key in a B-treeTraversing a B-treeAdding a Key to a B-treeRemoving a Key from a B-treeConsidering Performance for B-treesRed-Black TreesRepresenting Red-Black TreesAdding a Key to a Red-Black TreeRestoring a Red-Black Tree StructureRemoving a Key from a Red-Black TreeConsidering Performance for Red-Black TreesSummaryQuestions
14. Heaps
Binary HeapsThe Structure PropertyThe Heap PropertyHeap ImplementationPriority Queues and HeapsHeapsortWilliams’ Original HeapsortHeapsort AnalysisFloyd’s Heap-Building EnhancementTreapsCreating and Searching a TreapAdding a Key to a TreapRemoving a Key from a TreapConsidering the Performance of TreapsTernary and D-ary HeapsSummaryQuestions
15. Extended Heaps
Meldable and Addressable Priority QueuesSkew HeapsRepresenting a Skew HeapMerging Two Skew HeapsAdding a Key to a Skew HeapRemoving the Top Key from a Skew HeapConsidering Performance for Skew HeapsBinomial HeapsBinomial TreesDefining Binomial HeapsAdding a Value to a Binomial HeapMerging Two Binomial HeapsRemoving a Value from a Binomial HeapChanging a Value in a Binomial HeapConsidering Performance for Binomial HeapsLazy Binomial HeapsDefining Lazy Binomial HeapsAdding a Value to a Lazy Binomial HeapRemoving a Value from a Lazy Binomial HeapChanging a Value in a Lazy Binomial HeapConsidering Performance for Lazy Binomial HeapsFibonacci HeapsRepresenting a Fibonacci HeapMerging Two Fibonacci TreesAdding a Value to a Fibonacci HeapRemoving a Value from a Fibonacci HeapChanging a Value in a Fibonacci HeapConsidering Performance for Fibonacci HeapsPairing HeapsDefining a Pairing HeapMelding Two Pairing HeapsAdding a Value to a Pairing HeapRemoving the Top Value from a Pairing HeapChanging a Value in a Pairing HeapConsidering Performance for Pairing HeapsSummaryQuestions
16. Digital Search Trees
The Classic Version of TriesStoring Extra Data in a TrieSearching a TrieAdding a Key to a TrieRemoving a Key from a TrieConsidering Performance for TriesAn Enhanced Version of TriesDefining an Object-Based TrieSearching an Object-Based TrieAdding a Key to an Object-Based TrieRemoving a Key from an Object-Based TrieConsidering Performance for Object-Based TriesRadix TreesDefining a Radix TreeSearching a Radix TreeAdding a Key to a Radix TreeRemoving a Key from a Radix TreeConsidering Performance for Radix TreesTernary Search TriesDefining Ternary TriesStoring Extra Data in a Ternary TrieSearching a Ternary TrieAdding a Key to a Ternary TrieRemoving a Key from a Ternary TrieConsidering Performance for Ternary TriesSummaryQuestions
17. Graphs
What Are Graphs?Representing GraphsAdjacency Matrix Representation for GraphsAdjacency List Representation for GraphsAdjacency Set Representation for GraphsFinding the Shortest PathsFloyd-Warshall’s “All Paths” AlgorithmBellman-Ford AlgorithmDijkstra’s AlgorithmSorting a GraphKahn’s AlgorithmTarjan’s AlgorithmDetecting CyclesDetecting ConnectivityDetecting Connectivity with SetsDetecting Connectivity with SearchesFinding a Minimum Spanning TreePrim’s AlgorithmKruskal’s AlgorithmSummaryQuestions
18. Immutability and Functional Data Structures
Functional Data StructuresArrays (and Hash Tables)Functional ListsFunctional TreesSummaryQuestions
Answer Key
Bibliography
Index

Content preview from Data Structures and Algorithms in JavaScript

INTRODUCTION

This book deals with two basic concepts in computer science: data structures and algorithms. It follows a structure similar to university curricula and adds examples taken from coding challenges and interview questions, using them to discuss the relative advantages and disadvantages of specific algorithms and data structures.

All examples are fully coded in JavaScript, with particular attention given to modern language features that simplify coding. Performance is also considered, from both a theoretical point of view (order of algorithms) and a practical one (scaffolding, measuring). Each chapter ends with a series of questions ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Publisher Resources

ISBN: 9798341620001Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures and Algorithms in JavaScript

by Federico Kereki

INTRODUCTION

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.