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

Hands-On Data Structures and Algorithms with JavaScript

Book Description

Increase your productivity by implementing complex data structures and algorithms using JavaScript

About This Book

  • A step by step guide, which will provide you with a thorough discussion on the analysis and design of fundamental JavaScript data structures
  • Get a better understanding of advanced concepts such as space and time complexity to optimize your code
  • Focus more on solving the business problem and less on the technical challenges involved

Who This Book Is For

If you are a JavaScript developer looking for practical examples to implement data structures and algorithms in your web applications, then this book is for you. Familiarity with data structures and algorithms will be helpful to get the most out of this book.

What You Will Learn

  • Build custom Back buttons embedded within your application
  • Build part of a basic JavaScript syntax parser and evaluator for an online IDE
  • Build a custom activity user tracker for your application
  • Generate accurate recommendations for credit card approval using Decision Trees
  • Simplify complex problems using a graphs
  • Increase the performance of an application using micro-optimizations

In Detail

Data structures and algorithms are the fundamental building blocks of computer programming. They are critical to any problem, provide a complete solution, and act like reusable code. Using appropriate data structures and having a good understanding of algorithm analysis are key in JavaScript to solving crises and ensuring your application is less prone to errors.

Do you want to build applications that are high-performing and fast? Are you looking for complete solutions to implement complex data structures and algorithms in a practical way? If either of these questions rings a bell, then this book is for you!

You'll start by building stacks and understanding performance and memory implications. You will learn how to pick the right type of queue for the application. You will then use sets, maps, trees, and graphs to simplify complex applications. You will learn to implement different types of sorting algorithm before gradually calculating and analyzing space and time complexity. Finally, you'll increase the performance of your application using micro optimizations and memory management.

By the end of the book you will have gained the skills and expertise necessary to create and employ various data structures in a way that is demanded by your project or use case.

Style and approach

Step-by-step topics will help you get started with solutions for implementing classic data structures and algorithms. Learn by doing with hands-on code snippets that give you practical experience of the subject.

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. 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. Download the color images
      3. Conventions used
    4. Get in touch
      1. Reviews
  2. Building Stacks for Application State Management
    1. Prerequisites
    2. Terminology
    3. API
    4. Don't we have arrays for this?
    5. Creating a stack
      1. Implementing stack methods
      2. Testing the stack
      3. Using the stack
    6. Use cases
      1. Creating an Angular application
        1. Installing Angular CLI
        2. Creating an app using the CLI
        3. Creating a stack
      2. Creating a custom back button for a web application
        1. Setting up the application and its routing
        2. Detecting application state changes
        3. Laying out the UI
        4. Navigating between states
        5. Final application logic
      3. Building part of a basic JavaScript syntax parser and evaluator
        1. Building a basic web worker
        2. Laying out the UI
        3. Basic web worker communication
        4. Enabling web worker communications
        5. Transforming input to machine-understandable expression
        6. Converting infix to postfix expressions
        7. Evaluating postfix expressions
    7. Summary
  3. Creating Queues for In-Order Executions
    1. Types of queue
    2. Implementing APIs
    3. Creating a queue
      1. A simple queue
        1. Testing the queue
      2. Priority Queue
        1. Testing a priority queue
    4. Use cases for queues
      1. Creating a Node.js application
      2. Starting the Node.js server
      3. Creating a chat endpoint
      4. Implementing logging using priority queues
    5. Comparing performance
      1. Running benchmark tests
    6. Summary
  4. Using Sets and Maps for Faster Applications
    1. Exploring the origin of sets and maps
    2. Analyzing set and map types
      1. How weak is WeakMap?
        1. Memory management
      2. API differences
    3. Sets versus WeakSets
      1. Understanding WeakSets
      2. The API difference
    4. Use cases
      1. Creating an Angular application
      2. Creating custom keyboard shortcuts for your application
        1. Creating an Angular application
        2. Creating states with keymap
      3. Activity tracking and analytics for web applications
        1. Creating the Angular application
    5. Performance comparison
      1. Sets and Arrays
      2. Maps and Objects
    6. Summary
  5. Using Trees for Faster Lookup and Modifications
    1. Creating an Angular application
    2. Creating a typeahead lookup
      1. Creating a trie tree
      2. Implementing the add() method
        1. The friends' example
      3. Implementing the search() method
      4. Retaining remainders at nodes
      5. The final form
    3. Creating a credit card approval predictor
      1. ID3 algorithm
        1. Calculating target entropy
        2. Calculating branch entropy
        3. The final information gain per branch
      2. Coding the ID3 algorithm
        1. Generating training dataset
        2. Generating the decision tree
        3. Predicting outcome of sample inputs
        4. Visualization of the tree and output
      3. Summary
  6. Simplify Complex Applications Using Graphs
    1. Types of graphs
    2. Use cases
      1. Creating a Node.js web server
      2. Creating a reference generator for a job portal
        1. Creating a bidirectional graph
        2. Generating a pseudocode  for the shortest path generation 
        3. Implementing the shortest path generation
        4. Creating a web server
        5. Running the reference generator
      3. Creating a friend recommendation system for social media
        1. Understanding PageRank algorithm
        2. Understanding Personalized PageRank (PPR) Algorithm
        3. Pseudocode for personalized PageRank
        4. Creating a web server
        5. Implementing Personalized PageRank
        6. Results and analysis
      4. Summary
  7. Exploring Types of Algorithms
    1. Creating a Node.js application
    2. Use cases
      1. Using recursion to serialize data
        1. Pseudocode
        2. Serializing data
      2. Using Dijkstra to determine the shortest path
        1. Pseudo code
        2. Implementing Dijkstra's algorithm
      3. Using BFS to determine relationships
        1. Pseudo code
        2. Implementing BFS
      4. Using dynamic programming to build a financial planner
        1. Pseudo code
        2. Implementing the dynamic programming algorithm
      5. Using a greedy algorithm to build a travel itinerary
        1. Understanding spanning trees
        2. Pseudo code
        3. Implementing a minimum spanning tree using a greedy algorithm
      6. Using branch and bound algorithm to create a custom shopping list
        1. Understanding branch and bound algorithm
        2. Implementing branch and bound algorithm
      7. When not to use brute-force algorithm
        1. Brute-force Fibonacci generator
        2. Recursive Fibonacci generator
        3. Memoized Fibonacci generator
    3. Summary
  8. Sorting and Its Applications
    1. Types of sorting algorithms
    2. Use cases of different sorting algorithms
      1. Creating an Express server
      2. Mocking library books data
      3. Insertionsort API
        1. What is Insertionsort
        2. Pseudo code
        3. Implementing Insertionsort API
      4. Mergesort API
        1. What is Mergesort
        2. Pseudo code
        3. Implementing Mergesort API
      5. Quicksort API
        1. What is Quicksort
        2. Pseudo code
        3. Implementing the Quicksort API
          1. Lomuto Partition Scheme
          2. Hoare Partition Scheme
      6. Performance comparison
      7. Summary
  9. Big O Notation, Space, and Time Complexity
    1. Terminology
      1. Asymptotic Notations
        1. Big-O notation
        2. Omega notation
        3. Theta Notation
        4. Recap
    2. Examples of time complexity
      1. Constant time
      2. Logarithmic time
      3. Linear time
      4. Quadratic time
      5. Polynomial time
        1. Polynomial time complexity classes
      6. Recursion and additive complexity
    3. Space complexity and Auxiliary space 
      1. Examples of Space complexity
        1. Constant space
        2. Linear space
      2. Summary
  10. Micro-Optimizations and Memory Management
    1. Best practices
      1. Best practices for HTML
        1. Declaring the correct DOCTYPE
        2. Adding the correct meta-information to the page
        3. Dropping unnecessary attributes
        4. Making your app mobile ready
        5. Loading style sheets in the <head>
        6. Avoiding inline styles
        7. Using semantic markup
        8. Using Accessible Rich Internet Applications (ARIA) attributes
        9. Loading scripts at the end
      2. CSS best practices
        1. Avoiding inline styles
        2. Do not use !important
        3. Arranging styles within a class alphabetically
        4. Defining the media queries in an ascending order
      3. Best practices for JavaScript
        1. Avoiding polluting the global scope
        2. Using 'use strict'
        3. Strict checking (== vs ===)
        4. Using ternary operators and Boolean || or &&
        5. Modularization of code
        6. Avoiding pyramid of doom
        7. Keeping DOM access to a minimum
        8. Validating all data
        9. Do not reinvent the wheel
    2. HTML optimizations
      1. DOM structuring
      2. Prefetching and preloading resources
        1. <link rel=prefetch >
        2. <link rel=preload >
      3. Layout and layering of HTML
        1. The HTML layout 
        2. HTML layers
    3. CSS optimizations
      1. Coding practices
        1. Using smaller values for common ENUM
        2. Using shorthand properties
        3. Avoiding complex CSS selectors
      2. Understanding the browser
        1. Avoiding repaint and reflow
        2. Critical rendering path (CRP)
    4. JavaScript optimizations
      1. Truthy/falsy comparisons
      2. Looping optimizations
      3. The conditional function call
      4. Image and font optimizations
      5. Garbage collection in JavaScript
        1. Mark and sweep algorithm
        2. Garbage collection and V8
      6. Avoiding memory leaks 
        1. Assigning variables to global scope
        2. Removing DOM elements and references
        3. Closures edge case
    5. Summary
    6. What's next?
  11. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think