O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Learning JavaScript Data Structures and Algorithms - Third Edition

Book Description

Create classic data structures and algorithms such as depth-first search and breadth-first search, learn recursion, as well as create and use a heap data structure using JavaScript

About This Book
  • Implement common data structures and the associated algorithms along with the context in which they are used
  • Master existing JavaScript data structures such as arrays, sets, and maps, and learn how to implement new ones such as stacks, linked lists, trees, and graphs in ES 8
  • Develop abstract data types to make JavaScript a more flexible and powerful programming language
Who This Book Is For

If you're a JavaScript developer who wants to dive deep into JavaScript and write complex programs using JavaScript data structures and algorithms, this book is for you.

What You Will Learn
  • Declare, initialize, add, and remove items from arrays, stacks, and queues
  • Create and use linked lists, doubly linked lists, and circular linked lists
  • Store unique elements with hash tables, dictionaries, and sets
  • Explore the use of binary trees and binary search trees
  • Sort data structures using algorithms such as bubble sort, selection sort, insertion sort, merge sort, and quick sort
  • Search elements in data structures using sequential sort and binary search
In Detail

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.

Style and approach

Easy to follow guide which will cover the most used data structures and sorting/searching algorithms known in the computer science world along with examples to help the readers understand each chapter thoroughly.

Downloading the example code for this book You can download the example code files for all Packt books you have purchased from your account at http://www.PacktPub.com. If you purchased this book elsewhere, you can visit http://www.PacktPub.com/support and register to have the files e-mailed directly to you.

Table of Contents

  1. Title Page
  2. Copyright and Credits
    1. Learning JavaScript Data Structures and Algorithms  Third Edition
  3. Dedication
  4. Packt Upsell
    1. Why subscribe?
    2. PacktPub.com
  5. Contributors
    1. About the author
    2. About the reviewers
    3. Packt is searching for authors like you
  6. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
      1. Download the example code files
      2. Conventions used
    4. Get in touch
      1. Reviews
  7. JavaScript – A Quick Overview
    1. JavaScript data structure and algorithms
    2. Setting up the environment
      1. The minimum setup to work with JavaScript
      2. Using web servers
      3. Node.js http-server
    3. JavaScript basics
      1. Variables
        1. Scope variable
      2. Operators
      3. Truthy and falsy
      4. Functions of the equals operators (== and ===)
      5. Control structures
        1. Conditional statements
        2. Loops
      6. Functions
      7. Object-oriented programming in JavaScript
    4. Debugging and tools
      1. Debugging with VSCode
    5. Summary
  8. ECMAScript and TypeScript Overview
    1. ECMAScript or JavaScript?
      1. ES6, ES2015, ES7, ES2016, ES8, ES2017, and ES.Next
        1. The compatibility table
      2. Using Babel.js
    2. ECMAScript 2015+ functionalities
      1. let and const instead of var
        1. Variables scope with let and const
      2. Template literals
      3. Arrow functions
      4. Default parameter values for functions
      5. Declaring the spread and rest operators
      6. Enhanced object properties
      7. Object-oriented programming with classes
        1. Inheritance
        2. Working with getters and setters
      8. Exponentiation operator
      9. Modules
        1. Running ES2015 modules in the browser and with Node.js
          1. Using native ES2015 imports in Node.js
        2. Running ES2015 modules in the browser
        3. ES2015+ backward compatibility
    3. Introducing TypeScript
      1. Type inference
      2. Interfaces
        1. Generics
      3. Other TypeScript functionalities
      4. TypeScript compile-time checking in JavaScript files
    4. Summary
  9. Arrays
    1. Why should we use arrays?
    2. Creating and initializing arrays
      1. Accessing elements and iterating an array
    3. Adding elements
      1. Inserting an element at the end of the array
        1. Using the push method
      2. Inserting an element in the first position
        1. Using the unshift method
    4. Removing elements
      1. Removing an element from the end of the array
      2. Removing an element from the first position
        1. Using the shift method
    5. Adding and removing elements from a specific position
    6. Two-dimensional and multi-dimensional arrays
      1. Iterating the elements of two-dimensional arrays
      2. Multi-dimensional arrays
    7. References for JavaScript array methods
      1. Joining multiple arrays
      2. Iterator functions
        1. Iterating using the every method
        2. Iterating using the some method
        3. Iterating using forEach
        4. Using map and filter
        5. Using the reduce method
      3. ECMAScript 6 and new array functionalities
        1. Iterating using the for...of loop
        2. Using the @@iterator object
        3. Array entries, keys, and values
        4. Using the from method
        5. Using the Array.of method
        6. Using the fill method
        7. Using the copyWithin method
      4. Sorting elements
        1. Custom sorting
        2. Sorting strings
      5. Searching
        1. ECMAScript 2015 - the find and findIndex methods
        2. ECMAScript 2016 - using the includes method
      6. Outputting the array into a string
    8. The TypedArray class
    9. Arrays in TypeScript
    10. Summary
  10. Stacks
    1. Creating a JavaScript data structure and algorithm library
    2. The stack data structure
      1. Creating an array-based Stack class
      2. Pushing elements to the stack
      3. Popping elements from the stack
      4. Peeking the element from the top of the stack
      5. Verifying whether the stack is empty
      6. Clearing the elements of the stack
      7. Using the Stack class
    3. Creating a JavaScript object-based Stack class
      1. Pushing elements to the stack
      2. Verifying whether the stack is empty and its size
      3. Popping elements from the stack
      4. Peeking the top of the stack and clearing it
      5. Creating the toString method
    4. Protecting the internal elements of the data structure
      1. The underscore naming convention
      2. ES2015 classes with scoped symbols
      3. ES2015 classes with WeakMap
      4. ECMAScript class field proposal
    5. Solving problems using stacks
      1. Converting decimal numbers to binary
        1. The base converter algorithm
    6. Summary
  11. Queues and Deques
    1. The queue data structure
      1. Creating the Queue class
        1. Enqueuing elements to the queue
        2. Dequeuing elements from the queue
        3. Peeking the element from the front of the queue
        4. Verifying whether the queue is empty and its size
        5. Clearing the queue
        6. Creating the toString method
      2. Using the Queue class
    2. The deque data structure
      1. Creating the Deque class
        1. Adding elements to the front of the deque
      2. Using the Deque class
    3. Solving problems using queues and deques
      1. The circular queue – Hot Potato
      2. Palindrome checker
      3. JavaScript task queues
    4. Summary
  12. Linked Lists
    1. The linked list data structure
      1. Creating the LinkedList class
        1. Pushing elements to the end of the linked list
        2. Removing elements from the linked list from a specific position
        3. Looping through the list until we get to the desired position
          1. Refactoring the remove method
        4. Inserting an element at any position
        5. The indexOf method: returning the position of an element
        6. Removing an element from the linked list
        7. The isEmpty, size, and getHead methods
        8. The toString method
    2. Doubly linked lists
      1. Inserting a new element at any position
      2. Removing elements from any position
    3. Circular linked lists
      1. Inserting a new element at any position
      2. Removing elements from any position
    4. Sorted linked lists
      1. Inserting elements in order
    5. Creating the StackLinkedList class
    6. Summary
  13. Sets
    1. Structuring a dataset
    2. Creating a Set class
      1. The has(element) method
      2. The add method
      3. The delete and clear methods
      4. The size method
      5. The values method
      6. Using the Set class
    3. Set operations
      1. Set union
      2. Set intersection
        1. Improving the intersection method
      3. Set difference
      4. Subset
    4. ECMAScript 2015 – the Set class
      1. ES2015 Set class operations
        1. Simulating the union operation
        2. Simulating the intersection operation
        3. Simulating the difference operation
        4. Using the spread operator
    5. Multisets or bags
    6. Summary
  14. Dictionaries and Hashes
    1. The dictionary data structure
      1. Creating the Dictionary class
        1. Verifying whether a key exists in the dictionary
        2. Setting a key and value in the dictionary and the ValuePair class
        3. Removing a value from the dictionary
        4. Retrieving a value from the dictionary
        5. The keys, values, and valuePairs methods
        6. Iterating each ValuePair of the dictionary with forEach
        7. The clear, size, isEmpty, and toString methods
      2. Using the Dictionary class
    2. The hash table
      1. Creating a HashTable class
        1. Creating a hash function
        2. Putting a key and a value in the hash table
        3. Retrieving a value from the hash table
        4. Removing a value from the hash table
      2. Using the HashTable class
      3. Hash table versus hash set
      4. Handling collisions between hash tables
        1. Separate chaining
          1. The put method
          2. The get method
          3. The remove method
        2. Linear probing
          1. The put method
          2. The get method
          3. The remove method
      5. Creating better hash functions
    3. The ES2015 Map class
    4. The ES2015 WeakMap and WeakSet classes
    5. Summary
  15. Recursion
    1. Understanding recursion
    2. Calculating the factorial of a number
      1. Iterative factorial
      2. Recursive factorial
        1. The call stack
        2. JavaScript limitation on the call stack size
    3. The Fibonacci sequence
      1. Iterative Fibonacci
      2. Recursive Fibonacci
      3. Fibonacci with memoization
    4. Why use recursion? Is it faster?
    5. Summary
  16. Trees
    1. The tree data structure
    2. Tree terminology
    3. The binary and binary search trees
      1. Creating the Node and BinarySearchTree classes
      2. Inserting a key into the BST
    4. Tree traversal
      1. In-order traversal
      2. Pre-order traversal
      3. Post-order traversal
    5. Searching for values in a tree
      1. Searching for minimum and maximum values
      2. Searching for a specific value
      3. Removing a node
        1. Removing a leaf node
        2. Removing a node with a left or right child
        3. Removing a node with two children
    6. Self-balancing trees
      1. Adelson-Velskii and Landi’s tree (AVL tree)
        1. Height of a node and the balancing factor
        2. Balancing operations– AVL rotations
          1. Left-left case: single rotation to the right
          2. Right-right case: single rotation to the left
          3. Left-right case: double rotation to the right
          4. Right-left case – double rotation to the left
        3. Inserting a node in the AVL tree
        4. Removing a node from the AVL tree
      2. Red-Black tree
        1. Inserting a node in the Red-Black tree
          1. Verifying the Red-Black tree properties after insertion
          2. Red-Black tree rotations
    7. Summary
  17. Binary Heap and Heap Sort
    1. The binary heap data structure
      1. Creating the MinHeap class
        1. Binary tree array representation
        2. Inserting a value into the heap
          1. The sift up operation
        3. Finding the minimum or maximum value from the heap
        4. Extracting the minimum or maximum value from the heap
          1. The sift down operation (heapify)
      2. Creating the MaxHeap class
    2. The heap sort algorithm
    3. Summary
  18. Graphs
    1. Graph terminology
      1. Directed and undirected graphs
    2. Representing a graph
      1. The adjacency matrix
      2. The adjacency list
      3. The incidence matrix
    3. Creating the Graph class
    4. Graph traversals
      1. Breadth-first search (BFS)
        1. Finding the shortest paths using BFS
        2. Further study on the shortest paths algorithms
      2. Depth-first search (DFS)
        1. Exploring the DFS algorithm
        2. Topological sorting using DFS
    5. Shortest path algorithms
      1. Dijkstra's algorithm
      2. The Floyd-Warshall algorithm
    6. Minimum spanning tree (MST)
      1. Prim's algorithm
      2. Kruskal's algorithm
    7. Summary
  19. Sorting and Searching Algorithms
    1. Sorting algorithms
      1. The bubble sort
        1. The improved bubble sort
      2. The selection sort
      3. The insertion sort
      4. The merge sort
      5. The quick sort
        1. The partition process
        2. The quick sort in action
      6. The counting sort
      7. The bucket sort
      8. The radix sort
    2. Searching algorithms
      1. The sequential search
      2. The binary search
      3. The interpolation search
    3. Shuffle algorithms
      1. The Fisher-Yates shuffle
    4. Summary
  20. Algorithm Designs and Techniques
    1. Divide and conquer
      1. Binary search
    2. Dynamic programming
      1. The minimum coin change problem
      2. The knapsack problem
      3. The longest common subsequence
      4. Matrix chain multiplication
    3. Greedy algorithms
      1. The min-coin change problem
      2. The fractional knapsack problem
    4. Backtracking algorithms
      1. Rat in a Maze
      2. Sudoku Solver
    5. Introduction to functional programming
      1. Functional versus imperative programming
      2. ES2015+ and functional programming
      3. The JavaScript functional toolbox – map, filter, and reduce
      4. JavaScript functional libraries and data structures
    6. Summary
  21. Algorithm Complexity
    1. Big O notation
      1. Understanding big O notation
        1. O(1)
        2. O(n)
        3. O(n2)
      2. Comparing complexities
        1. Data structures
        2. Graphs
        3. Sorting Algorithms
        4. Searching Algorithms
      3. Introduction to the NP-completeness theory
        1. Impossible problems and heuristic algorithms
    2. Having fun with algorithms
    3. Summary
  22. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think