You are previewing Learning JavaScript Data Structures and Algorithms - Second Edition.
O'Reilly logo
Learning JavaScript Data Structures and Algorithms - Second Edition

Book Description

Hone your skills by learning classic data structures and algorithms in JavaScript

About This Book

  • Understand common data structures and the associated algorithms, as well as the context in which they are used.

  • Master existing JavaScript data structures such as array, set and map and learn how to implement new ones such as stacks, linked lists, trees and graphs.

  • All concepts are explained in an easy way, followed by examples.

  • Who This Book Is For

    If you are a student of Computer Science or are at the start of your technology career and want to explore JavaScript’s optimum ability, this book is for you. You need a basic knowledge of JavaScript and programming logic to start having fun with algorithms.

    What You Will Learn

  • Declare, initialize, add, and remove items from arrays, stacks, and queues

  • Get the knack of using algorithms such as DFS (Depth-first Search) and BFS (Breadth-First Search) for the most complex data structures

  • Harness the power of creating linked lists, doubly linked lists, and circular linked lists

  • Store unique elements with hash tables, dictionaries, and sets

  • Use binary trees and binary search trees

  • Sort data structures using a range of algorithms such as bubble sort, insertion sort, and quick sort

  • In Detail

    This book begins by covering basics of the JavaScript language and introducing ECMAScript 7, before gradually moving on to the current implementations of ECMAScript 6. You will gain an in-depth knowledge of how hash tables and set data structure functions, as well as how trees and hash maps can be used to search files in a HD or represent a database. This book is an accessible route deeper into JavaScript. Graphs being one of the most complex data structures you’ll encounter, we’ll also give you a better understanding of why and how graphs are largely used in GPS navigation systems in social networks.

    Toward the end of the book, you’ll discover how all the theories presented by this book can be applied in real-world solutions while working on your own computer networks and Facebook searches.

    Style and approach

    This book gets straight to the point, providing you with examples of how a data structure or algorithm can be used and giving you real-world applications of the algorithm in JavaScript. With real-world use cases associated with each data structure, the book explains which data structure should be used to achieve the desired results in the real world.

    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 code file.

    Table of Contents

    1. Learning JavaScript Data Structures and Algorithms - Second Edition
      1. Learning JavaScript Data Structures and Algorithms - Second Edition
      2. Credits
      3. About the Author
      4. About the Reviewer
      5. www.PacktPub.com
        1. eBooks, discount offers, and more
          1. Why subscribe?
      6. Preface
        1. What this book covers
        2. What you need for this book
        3. Who this book is for
        4. Conventions
        5. Reader feedback
        6. Customer support
          1. Downloading the example code
          2. Downloading the color images of this book 
          3. Errata
          4. Piracy
          5. Questions
      7. 1. 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 (XAMPP)
          3. It's all about JavaScript (Node.js)
        3. JavaScript basics
          1. Variables
            1. Variable scope
          2. Operators
          3. Truthy and falsy
          4. Functions of the equals operators (== and ===)
        4. Control structures
          1. Conditional statements
          2. Loops
        5. Functions
        6. Object-oriented programming in Javascript
        7. Debugging and tools
        8. Introducing ECMAScript
          1. ECMAScript 6 and ECMAScript 7
          2. The compatibility table
            1. Using Babel.js
        9. ECMAScript 6 functionalities
          1. Declaring variables with let instead of var
            1. Variables scope with let
          2. Constants
          3. Template literals
          4. Arrow functions
          5. Default parameter values for functions
          6. Declaring the spread and rest operators
            1. Enhanced object properties
          7. Object-oriented programming with classes
            1. Inheritance
            2. Working with getters and setters
            3. Other functionalities
        10. ECMAScript 7 functionalities
          1. ES6 and ES7 backward compatibility
        11. Summary
      8. 2. Arrays
        1. Why should we use arrays?
        2. Creating and initializing arrays
          1. Accessing elements and iterating an array
        3. Adding elements
          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 first position
            1. Using the shift method
        5. Adding and removing elements from a specific position
        6. Two-dimensional and multidimensional 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 forEach with arrow functions
            2. Iterating using the for...of loop
            3. Using the new ES6 iterator (@@iterator)
              1. Array entries, keys, and values
            4. Using the from method
            5. Using Array.of
            6. Using the fill method
            7. Using the copyWithin method
          4. Sorting elements
            1. Custom sorting
            2. Sorting strings
          5. Searching
            1. ECMAScript 6 - the find and findIndex methods
            2. ECMAScript 7 - using the includes method
          6. Outputting the array into a string
        8. The TypedArray class
        9. Summary
      9. 3. Stacks
        1. The stack data structure
          1. Creating a stack
          2. Pushing elements to the stack
          3. Popping elements from the stack
          4. Peeking the element from the top of the stack
          5. Verifying if the stack is empty
          6. Clearing and printing the elements of the stack
            1. Using the Stack class
        2. EcmaScript 6 and the Stack class
          1. Declaring the Stack class using ES6 syntax
            1. ES6 classes with scoped Symbols
            2. ES6 classes with WeakMap
        3. Solving problems using stacks
          1. Decimal to binary
            1. The base converter algorithm
        4. Summary
      10. 4. Queues
        1. The queue data structure
        2. Creating a queue
          1. Enqueue elements to the queue
          2. Dequeue elements from the queue
          3. Peeking the element from the front of the queue
          4. Verifying if the queue is empty
          5. Printing the elements of the queue
            1. Using the Queue class
        3. The Queue class using ECMAScript 6 syntax
        4. The priority queue
        5. The circular queue - Hot Potato
        6. JavaScript task queues
        7. Summary
      11. 5. Linked Lists
        1. The linked list data structure
        2. Creating a linked list
          1. Appending elements to the end of the linked list
          2. Removing elements from the linked list
          3. Inserting an element at any position
          4. Implementing other methods
            1. The toString method
            2. The indexOf method
            3. The isEmpty, size, and getHead methods
        3. Doubly linked lists
          1. Inserting a new element at any position
          2. Removing elements from any position
        4. Circular linked lists
        5. Summary
      12. 6. Sets
        1. Structuring a dataset
        2. Creating a set
          1. The has (value) 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
          3. Set difference
          4. Subset
        4. ES6 – the Set class
          1. ES6 Set class operations
            1. Simulating the union operation
            2. Simulating the intersection operation
            3. Simulating the difference operation
        5. Summary
      13. 7. Dictionaries and Hashes
        1. Dictionaries
          1. Creating a dictionary
            1. The has and set methods
            2. The delete method
            3. The get and values methods
            4. The clear, size, keys, and getItems methods
          2. Using the Dictionary class
        2. The hash table
          1. Creating a 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 ES6 Map class
        4. The ES6 WeakMap and WeakSet classes
        5. Summary
      14. 8. Trees
        1. The tree data structure
        2. Tree terminology
        3. The binary and binary search trees
          1. Creating the BinarySearchTree class
          2. Inserting a key into a tree
        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. Inserting a node in the AVL tree
              1. Calculating the balance factor
              2. AVL rotations
            2. Completing the insertNode method
          2. More about binary trees
        7. Summary
      15. 9. 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
      16. 10. Sorting and Searching Algorithms
        1. The 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 heap sort
          7. The counting, bucket, and radix sorts (the distribution sorts)
        2. Searching algorithms
          1. The sequential search
          2. The binary search
        3. Summary
      17. 11. Patterns of Algorithm
        1. Recursion
          1. JavaScript limitation on the call stack size
          2. The Fibonacci sequence
        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. 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
        5. Summary
      18. 12. 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