Learning JavaScript Data Structures and Algorithms

Loiane Groner

• Publisher: Packt Publishing
• Year: 2014
• ISBN:
  9781783554874
• Edition: 1
• Topic: Informatique
• Subtopic: Sciences générales de l'informatique

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.

This book begins by covering the basics of the JavaScript language and then moves on to discuss the most important data structures such as array, queue, stack, and linked list. You will also gain an in-depth knowledge of how hash tables and set data structure function. After this, you will be taught what trees are, and how to use the binary tree and the binary search tree.

In subsequent chapters, you will learn about graphs, DFS, and BFS. Finally, we will round off by learning how to differentiate between various searching and sorting algorithms such as sequential search, binary search, quick sort, bubble sort, and so on, and how to implement them. Towards the end of the book, you will also be introduced to dynamic programming.

Learning JavaScript Data Structures and Algorithms

---

Table of Contents

Learning JavaScript Data Structures and Algorithms

Credits

About the Author

Acknowledgments

About the Reviewers

www.PacktPub.com

Support files, eBooks, discount offers, and more

Why subscribe?

Free access for Packt account holders

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

Setting up the environment

The browser is enough

Using web servers (XAMPP)

It's all about JavaScript (Node.js)

JavaScript basics

Variables

Variable scope

Operators

Truthy and falsy

The equals operators (== and ===)

Control structures

Conditional statements

Loops

Functions

Object-oriented programming

Debugging and tools

Summary

2. Arrays

Why should we use arrays?

Creating and initializing arrays

Adding and removing elements

Two-dimensional and multi-dimensional arrays

References for JavaScript array methods

Joining multiple arrays

Iterator functions

Searching and sorting

Custom sorting

Sorting strings

Searching

Outputting the array into a string

Summary

3. Stacks

Creating a stack

The complete Stack class

Using the Stack class

Decimal to binary

Summary

4. Queues

Creating a queue

The complete Queue class

Using the Queue class

The priority queue

The circular queue – Hot Potato

Summary

5. Linked Lists

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

Creating a set

The has (value) method

The add method

The remove and clear methods

The size method

The values method

Using the Set class

Set operations

Set union

Set intersection

Set difference

Subset

Summary

7. Dictionaries and Hashes

Dictionaries

Creating a dictionary

The has and set methods

The remove 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

Summary

8. Trees

Trees terminology

Binary tree and binary search tree

Creating the BinarySearchTree class

Inserting a key in 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

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 studies on the shortest paths algorithms

Depth-first search (DFS)

Exploring the DFS algorithm

Topological sorting using DFS

Summary

10. Sorting and Searching Algorithms

Sorting algorithms

Bubble sort

Improved bubble sort

Selection sort

Insertion sort

Merge sort

Quick sort

The partition process

Quick sort in action

Searching algorithms

Sequential search

Binary search

Summary

Index

Learning JavaScript Data Structures and Algorithms

Copyright © 2014 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

Production reference: 1201014

Published by Packt Publis...