Book Image

Learning JavaScript Data Structures and Algorithms - Third Edition

Book Image

Learning JavaScript Data Structures and Algorithms - Third Edition

Overview of this book

A data structure is a particular way of organizing data in a computer to utilize resources efficiently. Data structures and algorithms are the base of every solution to any programming problem. With this book, you will learn to write complex and powerful code using the latest ES 2017 features. Learning JavaScript Data Structures and Algorithms begins by covering the basics of JavaScript and introduces you to ECMAScript 2017, before gradually moving on to the most important data structures such as arrays, queues, stacks, and linked lists. You will gain in-depth knowledge of how hash tables and set data structures function as well as how trees and hash maps can be used to search files in an HD or represent a database. This book serves as a route to take you deeper into JavaScript. You’ll also get a greater understanding of why and how graphs, one of the most complex data structures, are largely used in GPS navigation systems in social networks. Toward the end of the book, you’ll discover how all the theories presented in this book can be applied to solve real-world problems while working on your own computer networks and Facebook searches.

Related Content you might be interested in

Current Title:

Small book image
Learning JavaScript Data Structures and Algorithms - Third Edition
Apr, 2018 | 426 pages
Small book image
PHP 7 Data Structures and Algorithms
Mizanur Rahman
May, 2017 | 340 pages
Small book image
Beginning Java Data Structures and Algorithms
James Cutajar
Jul, 2018 | 202 pages
Small book image
C# Data Structures and Algorithms
Marcin Jamro
Feb, 2024 | 372 pages
Table of Contents (22 chapters)
Title Page
Title Page
Dedication
Dedication
Packt Upsell
Packt Upsell
Contributors
Contributors
Preface
Preface
Free Chapter
1
JavaScript – A Quick Overview
JavaScript – A Quick Overview
JavaScript data structure and algorithms
Setting up the environment
JavaScript basics
Debugging and tools
Summary
2
ECMAScript and TypeScript Overview
ECMAScript and TypeScript Overview
ECMAScript or JavaScript?
ECMAScript 2015+ functionalities
Introducing TypeScript
Summary
3
Arrays
Arrays
Why should we use arrays?
Creating and initializing arrays
Adding elements
Removing elements
Adding and removing elements from a specific position
Two-dimensional and multi-dimensional arrays
References for JavaScript array methods
The TypedArray class
Arrays in TypeScript
Summary
4
Stacks
Stacks
Creating a JavaScript data structure and algorithm library
The stack data structure
Creating a JavaScript object-based Stack class
Protecting the internal elements of the data structure
Solving problems using stacks
Summary
5
Queues and Deques
Queues and Deques
The queue data structure
The deque data structure
Solving problems using queues and deques
Summary
6
Linked Lists
Linked Lists
The linked list data structure
Doubly linked lists
Circular linked lists
Sorted linked lists
Creating the StackLinkedList class
Summary
7
Sets
Sets
Structuring a dataset
Creating a Set class
Set operations
ECMAScript 2015 – the Set class
Multisets or bags
Summary
8
Dictionaries and Hashes
Dictionaries and Hashes
The dictionary data structure
The hash table
The ES2015 Map class
The ES2015 WeakMap and WeakSet classes
Summary
9
Recursion
Recursion
Understanding recursion
Calculating the factorial of a number
The Fibonacci sequence
Why use recursion? Is it faster?
Summary
10
Trees
Trees
The tree data structure
Tree terminology
The binary and binary search trees
Tree traversal
Searching for values in a tree
Self-balancing trees
Summary
11
Binary Heap and Heap Sort
Binary Heap and Heap Sort
The binary heap data structure
The heap sort algorithm
Summary
12
Graphs
Graphs
Graph terminology
Representing a graph
Creating the Graph class
Graph traversals
Shortest path algorithms
Minimum spanning tree (MST)
Summary
13
Sorting and Searching Algorithms
Sorting and Searching Algorithms
Sorting algorithms
Searching algorithms
Shuffle algorithms
Summary
14
Algorithm Designs and Techniques
Algorithm Designs and Techniques
Divide and conquer
Dynamic programming
Greedy algorithms
Backtracking algorithms
Introduction to functional programming
Summary
15
Algorithm Complexity
Algorithm Complexity
Big O notation
Having fun with algorithms
Summary
Other Books You May Enjoy
Other Books You May Enjoy
Leave a review - let other readers know what you think
Index
Index

Dynamic programming

Dynamic programming (DP) is an optimization technique used to solve complex problems by breaking them into smaller subproblems.

Note

Note that the dynamic programming approach is different from the divide and conquer approach. While the divide and conquer approach breaks the problem into independent subproblems and then combines the solutions, dynamic programming breaks the problem into dependent subproblems.

An example of a dynamic programming algorithm is the Fibonacci problem we solved in Chapter 9, Recursion. We broke the Fibonacci problem into smaller problems.

There are three important steps we need to follow when solving problems with DP:

  1. Define the subproblems.
  2. Implement the recurrence that solves the subproblems (in this step, we need to follow the steps for recursion that we discussed in the previous section).
  3. Recognize and solve the base cases.

There are some famous problems that can be solved with dynamic programming:

  • The knapsack problem: In this problem, given a...
Previous Section
End of Section 3
Next Section