Introduction to Data Structures and Algorithms With Modern JavaScript

Basic Data Structures

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

1. Linked Lists

LinkedList is the dynamic data structure, as we can add or remove elements at ease, and it can even grow as needed. Just like arrays, linked lists store elements sequentially, but don’t store the elements contiguously like an array.

// linkedlist class
class LinkedList {
    constructor()
    {
        this.head = null;
        this.size = 0;
    }
}

The above example shows a Linked List class with a constructor and a list of methods to be implemented. Linked List class has two properties: i.e. head and size, where the head stores the first node of a List, and size indicates the number of nodes in a list.

Functions to be implemented in the Linked List

1. add(element) – It adds an element at the end of the list.

// adds an element at the end
// of list
add(element)
{
    // creates a new node
    var node = new Node(element);

    // to store current node
    var current;

    // if list is Empty add the
    // element and make it head
    if (this.head == null)
        this.head = node;
    else {
        current = this.head;

        // iterate to the end of the
        // list
        while (current.next) {
            current = current.next;
        }

        // add node
        current.next = node;
    }
    this.size++;
}

In the order to add an element at the end of the list we consider the following :

• If the list is empty then add an element and it will be head

• If the list is not empty then iterate to the end of the list and add an element at the end of the list

2. insertAt(element, index) – It inserts an element at the given index in a list.

// insert element at the position index
// of the list
insertAt(element, index)
{
    if (index < 0 || index > this.size)
        return console.log("Please enter a valid index.");
    else {
        // creates a new node
        var node = new Node(element);
        var curr, prev;

        curr = this.head;

        // add the element to the
        // first index
        if (index == 0) {
            node.next = this.head;
            this.head = node;
        } else {
            curr = this.head;
            var it = 0;

            // iterate over the list to find
            // the position to insert
            while (it < index) {
                it++;
                prev = curr;
                curr = curr.next;
            }

            // adding an element
            node.next = curr;
            prev.next = node;
        }
        this.size++;
    }
}

In order to add an element at the given index of the list we consider three conditions as follows:

• if the index is zero we add an element at the front of the list and make it head

• If the index is the last position of the list we append the element at the end of the list

• if the index is between 0 or size – 1 we iterate over to the index and add an element at that index

3. removeFrom(index) – It removes and returns an element from the list from the specified index

// removes an element from the
// specified location
removeFrom(index)
{
    if (index < 0 || index >= this.size)
        return console.log("Please Enter a valid index");
    else {
        var curr, prev, it = 0;
        curr = this.head;
        prev = curr;

        // deleting first element
        if (index === 0) {
            this.head = curr.next;
        } else {
            // iterate over the list to the
            // position to removce an element
            while (it < index) {
                it++;
                prev = curr;
                curr = curr.next;
            }

            // remove the element
            prev.next = curr.next;
        }
        this.size--;

        // return the remove element
        return curr.element;
    }
}

In order to remove an element from the list we consider three conditions:

• If the index is 0 then we remove the head and make the next node head of the list

• If the index is size – 1 then we remove the last element from the list and make prev the last element

• If it’s in between 0 to size – 1 we remove the element by using prev and the current node

4. removeElement(element) – This method removes element from the list. It returns the removed element, or if it’s not found it returns -1.

// removes a given element from the
// list
removeElement(element)
{
    var current = this.head;
    var prev = null;

    // iterate over the list
    while (current != null) {
        // comparing element with current
        // element if found then remove the
        // and return true
        if (current.element === element) {
            if (prev == null) {
                this.head = current.next;
            } else {
                prev.next = current.next;
            }
            this.size--;
            return current.element;
        }
        prev = current;
        current = current.next;
    }
    return -1;
}

The above method is just a modification of removeFrom(index), as it searches for an element and removes it, rather than removing it from a specified location

Helper Methods
1. indexOf(element) – it returns the index of a given element if the element is in the list.

// finds the index of element
indexOf(element)
{
    var count = 0;
    var current = this.head;

    // iterate over the list
    while (current != null) {
        // compare each element of the list
        // with given element
        if (current.element === element)
            return count;
        count++;
        current = current.next;
    }

    // not found
    return -1;
}

2. isEmpty() – it returns true if the list is empty.

// checks the list for empty
isEmpty()
{
    return this.size == 0;
}

3. size_of_list() – It returns the size of list

// gives the size of the list
size_of_list()
{
    console.log(this.size);
}

*4. printList() – It prints the contents of the list. *

// prints the list items
printList()
{
    var curr = this.head;
    var str = "";
    while (curr) {
        str += curr.element + " ";
        curr = curr.next;
    }
    console.log(str);
}

2. Arrays

The Array object, as with arrays in other programming languages, enables storing a collection of multiple items under a single variable name, and has members for performing common array operations.

Create an Array

// 'fruits' array created using array literal notation.
const fruits = ['Apple', 'Banana'];
console.log(fruits.length);
// 2

// 'fruits' array created using the Array() constructor.
const fruits = new Array('Apple', 'Banana');
console.log(fruits.length);
// 2

// 'fruits' array created using String.prototype.split().
const fruits = 'Apple, Banana'.split(', ');
console.log(fruits.length);
// 2

Create an array from string

const fruits = ['Apple', 'Banana'];
const fruitsString = fruits.join(', ');
console.log(fruitsString);
// "Apple, Banana"

Access an array item by its index

const fruits = ['Apple', 'Banana'];

// The index of an array's first element is always 0.
fruits[0]; // Apple

// The index of an array's second element is always 1.
fruits[1]; // Banana

// The index of an array's last element is always one
// less than the length of the array.
fruits[fruits.length - 1]; // Banana

// Using a index number larger than the array's length
// returns 'undefined'.
fruits[99]; // undefined

Find the index of an item in an array

const fruits = ['Apple', 'Banana'];
console.log(fruits.indexOf('Banana'));
// 1

Check if an array contains a certain item

const fruits = ['Apple', 'Banana'];

fruits.includes('Banana'); // true
fruits.includes('Cherry'); // false

// If indexOf() doesn't return -1, the array contains the given item.
fruits.indexOf('Banana') !== -1; // true
fruits.indexOf('Cherry') !== -1; // false

Append an item to an array

const fruits = ['Apple', 'Banana'];
const newLength = fruits.push('Orange');
console.log(fruits);
// ["Apple", "Banana", "Orange"]
console.log(newLength);
// 3

Remove the last item from an array

const fruits = ['Apple', 'Banana', 'Orange'];
const removedItem = fruits.pop();
console.log(fruits);
// ["Apple", "Banana"]
console.log(removedItem);
// Orange

3. Stacks

linear data structure in which addition or removal of element follows a particular order i.e. LIFO(Last in First Out) AND FILO(First in Last Out).
Stacks are basically arrays where the only thing you can do, more or less, is to push and pop.

Array Declaration

var House = [ ]; // method 1 
var House = new Array(); // method 2 


// Initializing while declaring
var house = ["1BHK", "2BHK", "3BHK", "4BHK"];

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

4. Queues

Queues are, the first item added to the queue will be the first one taken out of the queue(FIFO). When adding an item into the queue that operation is called enqueuing and when we take out an item from the queue the operation is called dequeuing.

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

5. Trees

Trees are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, nodes contain both elements of data and pointers marking its relation to immediate nodes.

Each tree has a “root” node, off of which all other nodes branch. The root contains references to all elements directly below it, which are known as its “child nodes”. This continues, with each child node, branching off into more child nodes.

Nodes with linked child nodes are called internal nodes while those without child nodes are external nodes. A common type of tree is the “binary search tree” which is used to easily search stored data.

These search operations are highly efficient, as its search duration is dependent not on the number of nodes but on the number of levels down the tree.

This type of tree is defined by four strict rules:

a) The left subtree contains only nodes with elements lesser than the root.
b) The right subtree contains only nodes with elements greater than the root.
c) Left and right subtrees must also be a binary search tree. They must follow the above rules with the “root” of their tree.
d) There can be no duplicate nodes, i.e. no two nodes can have the same value.

6. Graphs

Graphs are a relation-based data structure helpful for storing web-like relationships. Each node, or vertex, as they’re called in graphs, has a title (A, B, C, etc.), a value contained within, and a list of links (called edges) it has with other vertices.

7. Hash Tables (Map)

Hash tables are a complex data structure capable of storing large amounts of information and retrieving specific elements efficiently. This data structure relies on the concept of key/value pairs, where the “key” is a searched string and the “value” is the data paired with that key.

Each searched key is converted from its string form into a numerical value, called a hash, using a predefined hash function. This hash then points to a storage bucket – a smaller subgroup within the table. It then searches the bucket for the originally entered key and returns the value associated with that key.