Learning JavaScript Data Structures and Algorithms - Second Edition

Table of Contents

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

Learning JavaScript Data Structures and Algorithms - Second Edition

Learning JavaScript Data Structures and Algorithms - Second Edition

Copyright © 2016 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

First published: October 2014

Second edition: June 2016

Production reference: 1160616

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham 

B3 2PB, UK.

ISBN 978-1-78528-549-3

www.packtpub.com

Credits

About the Author

Loiane Groner has over 10 years of experience in developing enterprise applications. She has worked at multinational companies, such as IBM, and nowadays she works as Software Development Manager at a financial institution, where she manages overseas solutions. Her areas of expertise include Java, Sencha technologies (Ext JS), and hybrid mobile development with PhoneGap and Ionic.

She is passionate about technology, and she has dedicated herself to spreading knowledge in the software development community through her blog http://loiane.com, as guest speaker in IT conferences, and also as guest professor in university extension courses.

While at university, she worked as teacher's assistant for 2 years for the Algorithms, Data Structures, and Computing Theory classes. She represented her university at the ACM International Collegiate Programming Contest – Brazilian Finals (South America Regionals) and also worked as Student Delegate of SBC (Brazilian Computing Society). She won a merit award in her Senior year for being one of top three students with better GPAs in the Computer Science department and has also graduated with honors.

Loiane is also the author of the books Ext JS 4 First Look, Mastering Ext JS, Mastering Ext JS - Second Edition, Sencha Architect App Development, Learning JavaScript Data Structures and Algorithms, and JavaScript Regular Expression, all of them published by Packt Publishing.

If you want to keep in touch, you can find Loiane on Facebook (https://www.facebook.com/loianegroner), Twitter (@loiane), and also on Github (https://github.com/loiane).

I would like to thank my parents for giving me education, guidance, and advice through all these years, and helping me to be a better human being and professional. A very special thanks to my husband for being patient and supportive and giving me encouragement to keep doing what I love. I would like to thank Packt for the amazing opportunity to write books about topics I really love! Thanks to all the people involved in the process of creating, reviewing, and publishing the books!

I also would like to thank the readers of this book and other books I have written for the support and feedback. Your feedback is very valuable to me to improve as an author and as a professional. Thank you very much!

About the Reviewer

Tessa B. Silver has a background in print design and traditional illustration. She has evolved, over the years, into web and interactive development, in which she focuses on usability and interface design as well as visualizing data primarily with JavaScript, HTML5, and CSS.

In addition to freelance consulting and technical writing via hyper³media LLC (pronounced hyper-cube-media), Tessa is currently a frontend mobile app and web developer for Capella University. She can be found and contacted via Twitter at @tessaract and on her personal site, http://tessaract.info.

Tessa has authored five other Packt Publishing titles, including WordPress Theme Design and WordPress 3.0 jQuery. She's currently working on Mastering Reactive JavaScript Programming with Bacon.js and RxJS for Packt.

I send a huge thank you to the Packt team who have made this title possible. Special thanks to Loiane Groner for authoring such a wonderful book, revealing the logic and secrets of data structures and algorithms for the rest of us to (finally!) fully comprehend. I'd also like to thank Smeet Thakkar for being the title's Aquisition Editor, and last, I'd like to send out an additional big-time thank you to Bijal Patel for the truly thankless, backbreaking work and diligence that it takes to keep to a schedule.

www.PacktPub.com

eBooks, discount offers, and more

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at [email protected] for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters and receive exclusive discounts and offers on Packt books and eBooks.

https://www2.packtpub.com/books/subscription/packtlib

Do you need instant solutions to your IT questions? PacktLib is Packt's online digital book library. Here, you can search, access, and read Packt's entire library of books.

Why subscribe?

Fully searchable across every book published by Packt

Copy and paste, print, and bookmark content

On demand and accessible via a web browser

Preface

JavaScript is one of the most popular programming language nowadays. It is known as the Internet language due the fact that browsers understand JavaScript natively without installing any plugins in them. JavaScript has grown so much that is no longer just a frontend language; it is also present now on the server (NodeJS) and database as well (MongoDB).

Learning data structures is very important for any technology professional. Working as a developer means that you are able to solve problems with the help of programming languages, and data structures are an indispensible piece of the solutions that we need to create to solve these problems. Choosing the wrong data structure can also impact on performance of the program we write. That is why is important to get to know different data structures and how to apply them properly.

Algorithms are the state of art of Computer Science. There are so many ways of solving the same problem, and some approaches are better than others. This is why it is also very important to know the most famous algorithms.

This book was written for beginners who want to learn data structures and algorithms, and also for those that are already familiar with data structures and algorithms but want to learn it using JavaScript.

Happy coding!

What this book covers

Chapter 1, JavaScript—A Quick Overview, covers the basics of JavaScript needed prior to learning data structures and algorithms. It also covers the setup of the development environment that we need for this book.

Chapter 2, Arrays, explains how to use the most basic and most used data structure, which are arrays. This chapter demonstrates how to declare, initialize, add, and remove elements from an array. It also covers how to use native JavaScript Array methods.

Chapter 3, Stacks, introduces the stack data structure, demonstrating how to create a stack and add and remove elements. It also demonstrates how to use stack to solve some computer science problems.

Chapter 4, Queues, covers the queue data structure, demonstrating how to create a queue and add and remove elements. It also demonstrates how to use queues to solve some computer science problems, and explains the major differences between queues and stacks.

Chapter 5, Linked Lists, explains how to create the linked list data structure from scratch using objects and the pointer concept. Besides covering how to declare, create, add, and remove elements, it also covers the various types of linked lists, such as doubly-linked lists and circular-linked lists.

Chapter 6, Sets, introduces the set data structure and how you can use it to store nonrepeated elements. It also explains the different types of set operations and how to implement and use them.

Chapter 7, Dictionaries and Hashes, explains the dictionary and hash data structures and the differences between them. This chapter covers how to declare, create, and use both data structures. It also explains how to handle collisions in hash, and the techniques to create better hash functions.

Chapter 8, Trees, covers the tree data structure and its terminology, focusing on Binary Search Tree data its methods to search, traverse, add, and remove nodes. It also introduces the next steps to dive into the world of trees, mentioning the tree algorithms that we should learn next.

Chapter 9, Graphs, introduces the amazing world of graphs and their application in real-world problems. This chapter covers the most common graph terminology, different ways of representing a graph, and how to traverse graphs using the Breadth-First-Search and Depth-First-Search algorithms and their applications.

Chapter 10 , Sorting and Searching Algorithms , explores the most used sorting algorithms, such as the Bubble sort (and its improved version), Selection sort, Insertion sort, Merge sort, and Quick sort. It also covers searching algorithms, such as the sequential and binary search.

Chapter 11 , Patterns of Algorithm , introduces some algorithm techniques and some of the most famous algorithms. It covers the recursion concept and some advanced algorithm techniques, such as dynamic programming and greedy algorithms.

Chapter 12 , Algorithm Complexity , introduces the Big-O notation and its concepts along with a cheat sheet of the complexity of the algorithms implemented in this book. It covers an introduction to NP-Completeness problems and heuristic solutions. Finally it explains how to take your algorithm knowledge to the next level.

What you need for this book

You can set up three different development environments for this book. You do not need to have all the three environments; you can select one or give all of them a try!

For the first option, you need a browser. We recommended one of the following:

Chrome (https://www.google.com/chrome/browser/)

Firefox (https://www.mozilla.org/en-US/firefox/new/)

The second option is setting up a local webserver:

A browser listed in the first option

A webserver. If you do not have any installed in your computer, you can install XAMMP from https://www.apachefriends.org

The third option is a 100% JavaScript environment!

A browser listed in the first option

NodeJS (http://nodejs.org/)

After installing NodeJS, install the http-server package:

        npm install http-server –g

You can find more detailed instructions in the first chapter as well.

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.

Conventions

In this book, you will find a number of text styles that distinguish between different kinds of information. Here are some examples of these styles and an explanation of their meaning.

Code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles are shown as follows: Using the isEmpty method, we can simply verify whether the length of the internal array is 0.

A block of code is set as follows:

function Stack() {

  //properties and methods go here

}

When we wish to draw your attention to a particular part of a code block, the relevant lines or items are set in bold:

class Stack {   constructor () {     this.items = []; //{1}   }

  push(element){

    this.items.push(element);

  }

  //other methods

}

Any command-line input or output is written as follows:

stack.push(5); stack.push(8);

New terms and important words are shown in bold. Words that you see on the screen, for example, in menus or dialog boxes, appear in the text like this: When you open Firebug (simply click on its icon), you will see the Console tab, and you will be able to write all your JavaScript code in its command-line area.

Note

Warnings or important notes appear in a box like this.

Tip

Tips and tricks appear like this.

Reader feedback

Feedback from our readers is always welcome. Let us know what you think about this book—what you liked or disliked. Reader feedback is important for us as it helps us develop titles that you will really get the most out of.

To send us general feedback, simply e-mail [email protected], and mention the book's title in the subject of your message.

If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, see our author guide at www.packtpub.com/authors.

Customer support

Now that you are the proud owner of a Packt book, we have a number of things to help you to get the most from your purchase.

Downloading the example code

You can download the example code files for this book 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.

You can download the code files by following these steps:

Log in or register to our website using your e-mail address and password.

Hover the mouse pointer on the SUPPORT tab at the top.

Click on Code Downloads & Errata.

Enter the name of the book in the Search box.

Select the book for which you're looking to download the code files.

Choose from the drop-down menu where you purchased this book from.

Click on Code Download.

You can also download the code files by clicking on the Code Files button on the book's webpage at the Packt Publishing website. This page can be accessed by entering the book's name in the Search box. Please note that you need to be logged in to your Packt account.

Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:

WinRAR / 7-Zip for Windows

Zipeg / iZip / UnRarX for Mac

7-Zip / PeaZip for Linux

The code bundle for the book is also hosted on GitHub at https://github.com/loiane/javascript-datastructures-algorithms. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

Downloading the color images of this book 

We also provide you with a PDF file that has color images of the screenshots/diagrams used in this book. The color images will help you better understand the changes in the output. You can download this file from https://www.packtpub.com/sites/default/files/downloads/LearningJavaScriptDataStructuresandAlgorithmsSecondEdition_ColorImages.pdf.