Learning JavaScript Data Structures and Algorithms - Second Edition电子书

Learning JavaScript Data Structures and Algorithms - Second Edition

Learning JavaScript Data Structures and Algorithms - Second Edition

Credits

About the Author

About the Reviewer

www.PacktPub.com

eBooks, discount offers, and more

Why subscribe?

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Downloading the color images of this book

Errata

Piracy

Questions

1. JavaScript—A Quick Overview

JavaScript data structure and algorithms

Setting up the environment

The minimum setup to work with JavaScript

Using web servers (XAMPP)

It's all about JavaScript (Node.js)

JavaScript basics

Variables

Variable scope

Operators

Truthy and falsy

Functions of the equals operators (== and ===)

Control structures

Conditional statements

Loops

Functions

Object-oriented programming in Javascript

Debugging and tools

Introducing ECMAScript

ECMAScript 6 and ECMAScript 7

The compatibility table

Using Babel.js

ECMAScript 6 functionalities

Declaring variables with let instead of var

Variables scope with let

Constants

Template literals

Arrow functions

Default parameter values for functions

Declaring the spread and rest operators

Enhanced object properties

Object-oriented programming with classes

Inheritance

Working with getters and setters

Other functionalities

ECMAScript 7 functionalities

ES6 and ES7 backward compatibility

Summary

2. Arrays

Why should we use arrays?

Creating and initializing arrays

Accessing elements and iterating an array

Adding elements

Using the push method

Inserting an element in the first position

Using the unshift method

Removing elements

Removing an element from first position

Using the shift method

Adding and removing elements from a specific position

Two-dimensional and multidimensional arrays

Iterating the elements of two-dimensional arrays

Multi-dimensional arrays

References for JavaScript array methods

Joining multiple arrays

Iterator functions

Iterating using the every method

Iterating using the some method

Iterating using forEach

Using map and filter

Using the reduce method

ECMAScript 6 and new Array functionalities

Iterating using forEach with arrow functions

Iterating using the for...of loop

Using the new ES6 iterator (@@iterator)

Array entries, keys, and values

Using the from method

Using Array.of

Using the fill method

Using the copyWithin method

Sorting elements

Custom sorting

Sorting strings

Searching

ECMAScript 6 - the find and findIndex methods

ECMAScript 7 - using the includes method

Outputting the array into a string

The TypedArray class

Summary

3. Stacks

The stack data structure

Creating a stack

Pushing elements to the stack

Popping elements from the stack

Peeking the element from the top of the stack

Verifying if the stack is empty

Clearing and printing the elements of the stack

Using the Stack class

EcmaScript 6 and the Stack class

Declaring the Stack class using ES6 syntax

ES6 classes with scoped Symbols

ES6 classes with WeakMap

Solving problems using stacks

Decimal to binary

The base converter algorithm

Summary

4. Queues

The queue data structure

Creating a queue

Enqueue elements to the queue

Dequeue elements from the queue

Peeking the element from the front of the queue

Verifying if the queue is empty

Printing the elements of the queue

Using the Queue class

The Queue class using ECMAScript 6 syntax

The priority queue

The circular queue - Hot Potato

JavaScript task queues

Summary

5. Linked Lists

The linked list data structure

Creating a linked list

Appending elements to the end of the linked list

Removing elements from the linked list

Inserting an element at any position

Implementing other methods

The toString method

The indexOf method

The isEmpty, size, and getHead methods

Doubly linked lists

Inserting a new element at any position

Removing elements from any position

Circular linked lists

Summary

6. Sets

Structuring a dataset

Creating a set

The has (value) method

The add method

The delete and clear methods

The size method

The values method

Using the Set class

Set operations

Set union

Set intersection

Set difference

Subset

ES6 – the Set class

ES6 Set class operations

Simulating the union operation

Simulating the intersection operation

Simulating the difference operation

Summary

7. Dictionaries and Hashes

Dictionaries

Creating a dictionary

The has and set methods

The delete method

The get and values methods

The clear, size, keys, and getItems methods

Using the Dictionary class

The hash table

Creating a hash table

Using the HashTable class

Hash table versus hash set

Handling collisions between hash tables

Separate chaining

The put method

The get method

The remove method

Linear probing

The put method

The get method

The remove method

Creating better hash functions

The ES6 Map class

The ES6 WeakMap and WeakSet classes

Summary

8. Trees

The tree data structure

Tree terminology

The binary and binary search trees

Creating the BinarySearchTree class

Inserting a key into a tree

Tree traversal

In-order traversal

Pre-order traversal

Post-order traversal

Searching for values in a tree

Searching for minimum and maximum values

Searching for a specific value

Removing a node

Removing a leaf node

Removing a node with a left or right child

Removing a node with two children

Self-balancing trees

Adelson-Velskii and Landi's tree (AVL tree)

Inserting a node in the AVL tree

Calculating the balance factor

AVL rotations

Completing the insertNode method

More about binary trees

Summary

9. Graphs

Graph terminology

Directed and undirected graphs

Representing a graph

The adjacency matrix

The adjacency list

The incidence matrix

Creating the Graph class

Graph traversals

Breadth-first search (BFS)

Finding the shortest paths using BFS

Further study on the shortest paths algorithms

Depth-first search (DFS)

Exploring the DFS algorithm

Topological sorting using DFS

Shortest path algorithms

Dijkstra's algorithm

The Floyd-Warshall algorithm

Minimum spanning tree (MST)

Prim's algorithm

Kruskal's algorithm

Summary

10. Sorting and Searching Algorithms

The sorting algorithms

The bubble sort

The improved bubble sort

The selection sort

The insertion sort

The merge sort

The quick sort

The partition process

The quick sort in action

The heap sort

The counting, bucket, and radix sorts (the distribution sorts)

Searching algorithms

The sequential search

The binary search

Summary

11. Patterns of Algorithm

Recursion

JavaScript limitation on the call stack size

The Fibonacci sequence

Dynamic programming

The minimum coin change problem

The knapsack problem

The longest common subsequence

Matrix chain multiplication

Greedy algorithms

The min-coin change problem

The fractional knapsack problem

Introduction to functional programming

Functional versus imperative programming

ES2015 and functional programming

The JavaScript functional toolbox - map, filter, and reduce

JavaScript functional libraries and data structures

Summary

12. Algorithm Complexity

Big-O notation

Understanding big-O notation

O(1)

O(n)

O(n2)

Comparing complexities

Data Structures

Graphs

Sorting Algorithms

Searching Algorithms

Introduction to the NP-Completeness theory

Impossible problems and heuristic algorithms

Having fun with algorithms

Summary