DEV Community: Ivy-Walobwa

Set Algorithms

Ivy-Walobwa — Fri, 24 Apr 2020 17:39:34 +0000

A set is a collection of any type of comparable data. Data in a set can occur only once.
Example;

{..., -3, -1, 1, 3, ...} is a set of odd numbers

Basic Set Implementations

new Set() - create a new set
Set.prototype.has() - returns true if element is present in Set object
Set.prototype.add() - adds a new item to set object
Set.prototype.delete() - removes specified item from set object

1.Union Algorithm
This is a set algorithm that compares two sets and returns a third set that contains all of the unique items in both sets.

 function union(setA, setB) {
    let result = new Set(setA); // new set containing items in setA
    for (let elem of setB) {
        // add items from setB to the new set
        // an element can't be added twice
        result.add(elem); 
    }
    return result;
}

let setA = new Set([1, 2, 3]);
let setB = new Set([3, 4, 5]);
console.log(union(setA, setB));
// >> Set { 1, 2, 3, 4, 5 }

2.Intersection Algorithm
Compares two sets and returns a third set that contains all of the matching members of both sets.

function intersection(setA, setB) {
    let result = new Set(); // new empty set
    for (let elem of setA) {
        if (setB.has(elem)){ // if matching elements found
            result.add(elem); // add to new set
        }
    }
    return result;
}

let setA = new Set([1, 2, 3]);
let setB = new Set([2, 3, 4]);
console.log(intersection(setA, setB));
// >> Set { 2, 3 }

3.Set Difference Algorithm
Takes two sets, A and B, and return all the items of A that are not members of B.

function setDifference(setA, setB) {
    let result = new Set(setA); 
    for (let item of setB) {
        result.delete(item); // delete items in A that exist in B
    }
    return result;
}

let setA = new Set([2, 3, 4]);
let setB = new Set([3, 4, 5]);
console.log(setDifference(setA, setB));
// >> Set { 2 }

4.Symmetric Difference Algorithm
Takes two sets and returns a third set that contains all of the members of both sets that are not in the other

function symmetricDifference(setA, setB) {
    let difference = new Set(setA);
    for (let elem of setB) {
        if (difference.has(elem)) {
            difference.delete(elem); // if item in B exists in A, remove
        } else {
            difference.add(elem) // else add to new set
        }
    }
    return difference;
}

let setA = new Set([1, 2, 3]);
let setB = new Set([2, 3, 4]);
console.log(symmetricDifference(setA, setB));
// >> Set { 1, 4 }

Symmetric Difference can also be described as the set difference of the intersection and union of the input sets

function symmetricDifference(setA, setB) {
    let intersectionResult = intersection(setA, setB)
    let unionResult = union(setA, setB);
    return setDifference(unionResult, intersectionResult,)
}
let setA = new Set([1, 2, 3]);
let setB = new Set([2, 3, 4]);
console.log(symmetricDifference(setA, setB));
// >> Set { 1, 4 }

Reference

I did it, you can too!!!

Ivy-Walobwa — Wed, 22 Apr 2020 19:27:04 +0000

Today I just did my first presentation ever on Angular.

I was tensed. My voice was shaking. I was sweating. But I went on. I didn't stop.
Guess what guys, I made it to the end of my presentation and I got to cover all I had planned and even more.
This so far is my greatest achievement this year.🎉🎉💃💃

Sorting Algorithms

Ivy-Walobwa — Tue, 21 Apr 2020 22:19:28 +0000

Sorting involves arranging data in a collection based on a comparison algorithm.

There are two general families of sorting algorithms;
1.Linear Sorting - treat the problem of sorting as a single large operation
2.Divide and Conquer - partition data to be sorted into smaller sets that can
be independently sorted.

The performance of sorting algorithms can be measured in terms of:
1.Comparisons - number of times two values of an input array are compared for relative equality.
2.Swaps - number of times two values stored in the input are swapped.

I am going to show you the implementation of 5 sorting algorithms in JavaScript:

Bubble sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

I found this site really helpful in visualizing these algorithms.

Bubble Sort

This is the simplest.
It works by repeatedly swapping values if they are the wrong position. Higher values are generally to the right and lower values are to the left.

Pseudocode

set swap counter to a truthy value
Repeat until the swap counter is a falsy value
Reset swap counter to a falsy value
    Look at each adjacent pair
        If two adjacent elements are not in order
        Swap them and set swap counter to truthy value

Code

function bubbleSort(arr) {
    let swapCounter = 1;

    while (swapCounter) {
        swapCounter = 0;
        for (let i = 0; i < arr.length - 1; i++){
            if (arr[i] > arr[i + 1]) {
                const swapElement = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = swapElement;
                swapCounter = 1;
            }
        }
    }

    return arr;
}

let arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)) 
// >> [11, 12, 22, 25,34, 64, 90]

Performance
Worst case - O(n^2)
Best case - O(n^2)

Selection Sort

It works by finding the smallest unsorted element and add it to the array in the first unsorted location

Pseudocode

Repeat until no sorted element remains:
    Search the unsorted part of the data to find the smallest value
    Swap the smallest value with the first element of unsorted part

Code

function selectionSort(arr){
    for (let i = 0; i < arr.length; i++){
        for (let j = i + 1; j < arr.length; j++){
            if (arr[j] < arr[i]) {
                const swapElement = arr[i];
                arr[i] = arr[j];
                arr[j] = swapElement;
            }
        }
    }

    return arr;
}



let arr = [4, 2, 5, 1, 3];
console.log(selectionSort(arr))
// >> [1, 2, 3, 4, 5]

Performance
Worst case - O(n^2)
Best case - O(n)

Insertion Sort

This algorithm sorts items are they are encoumtered

Pseudocode

Call the first element of the array 'sorted'
Repeat until all the elements are sorted :
    Look at the next unsorted element . Insert into the 'sorted' position by
    shifting the required number of elements

Code

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++){
        let unsorted = arr[i];
        let idx = i - 1;

        while (idx >= 0 && unsorted < arr[idx]) {
            arr[idx + 1] = arr[idx];
            idx -= 1;
        }
        arr[idx + 1] = unsorted;
    }
    return arr;
}

let arr = [4, 2, 5, 1, 3];
console.log(insertionSort(arr)) 
// >> [1, 2, 3, 4, 5]

Perfomance
Worst case - O(n^2)
Best case - O(n)

Merge Sort

Works by recursively splitting an array into two, sorting them and then combining these arrays in a sorted order

Pseudocode

Sort the left half of the array (Assuming n > 1)
Sort the right half of the array (Assuming n > 1)
Merge the two halves together

Code

function mergeSort(arr) {
    let length = arr.length

    // if  n is not > 1 
    // list is considered sorted
    if (length === 1) {
        return arr;
    }

    let midIdx = Math.ceil(length / 2);
    let leftHalf = arr.slice(0, midIdx);
    let rightHalf = arr.slice(midIdx, length);

    leftHalf = mergeSort(leftHalf);
    rightHalf = mergeSort(rightHalf);

    return merge(leftHalf, rightHalf)
}

// merge both halfs 
function merge(leftHalf, rightHalf) {
    const sorted = []
    while (leftHalf.length > 0 && rightHalf.length > 0) {
        const leftItem = leftHalf[0]
        const rightItem = rightHalf[0]

        if (leftItem > rightItem) {
            sorted.push(rightItem)
            rightHalf.shift()
        } else {
            sorted.push(leftItem);
            leftHalf.shift()
        }
    }

    // if left half is not empty
    while (leftHalf.length !== 0) {
        sorted.push(leftHalf[0])
        leftHalf.shift()
    }

    // if right half is not empty
    while (rightHalf.length !== 0) {
        sorted.push(rightHalf[0])
        rightHalf.shift()
    }

    return sorted;
}

let arr = [4, 2, 5, 1, 3];
console.log(mergeSort(arr)) 
// >> [1, 2, 3, 4, 5]

Performance
Worst case - O(nlogn)
Best case - O(nlogn)

Quick Sort

Pseudocode

Repeat until sorted
    Pick a pivot value and partition array
    Put all value smaller than pivot to the left and larger values to the right
    Perform pivot and partition on the left and the right partition

Code

function swap(arr, leftIndex, rightIndex) {
    const temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;
}

function partition(arr, left, right) {
    let pivot = arr[Math.floor((right + left) / 2)], //middle element
        i = left, //left pointer
        j = right; //right pointer
    while (i <= j) {
        // while left pointer is less than pivot
        // move pointer to the right
        while (arr[i] < pivot) {
            i++;
        }
        // while righ pointer is greater than pivot
        // move pointer to the left
        while (arr[j] > pivot) {
            j--;
        }

        // if left pointer is less than or equal to right pointe
        // swap elements
        // increment left pointer n decrement right pointer
        if (i <= j) {
            swap(arr, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i; // index of left pointer
}

function quickSort(arr, left, right) {
    let index;
    if (arr.length > 1) {
        index = partition(arr, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(arr, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(arr, index, right);
        }
    }
    return arr;
}


let arr = [4, 2, 5, 1, 3];
console.log(quickSort(arr, 0, arr.length - 1));
// >> [1, 2, 3, 4, 5]

Perfomance
Worst Case - O(n^2)
Best Case - O(nlogn)

Note: Bubble sort, insertion sort and selection sort are linear sorting algorithms while merge sort and quick sort are divide and conquer algorithms.

Happy coding 😉

Hash Tables

Ivy-Walobwa — Fri, 17 Apr 2020 19:04:53 +0000

Hash Tables store data in associative arrays. Data is stored in key/value pairs.
Each key is unique and is mapped to an index where an element can be inserted or removed from array.

Hashing
Hashing involves deriving a fixed size result from an input.
Method of hashing should be;
1.Stable - same input generates same output every time
2.Uniform - hash value should be uniformly distributed through available space
3.Efficient - cost of generating a hash must be balanced with application needs.
4.Secure - cost of finding data that produces a given hash is prohibitive.

Hashing a String
Hashing algorithms are pretty hard to design, pick an existing one right for the job.
The hashing algorithm I picked involves converting a string into an integer and generating indices for the table.

Handling Collisions
Collisions occur when two distinct keys have the same hash values.

Two common strategies can be used to handle collisions;
1.Open Addressing - here the new item is moved to the next index in table

while (array[index] !== null)
    index++
array[index] = item

2.Chaining - here the items are stored in linked list

array[index].addToList(item)

Implementation
I will be handling collision using chaining

1.Create Node class and hash table class

class Node {
    constructor(key, data) {
        this.key = key;
        this.data = data;
        this.next = null;
        this.previous = null;
    }
}

class HashTable{
    constructor() {
        this.buckets = [];
        this.maxBucketCount = 100;
    }
 // add methods   
}

Our hash table creates the bucket which we'll store our key/value pairs. We also set the maximum count to 100. The higher the bucket size, the less number of collisions.

2.Add methods to hash table class

Hashing

 hashCode(val) {
        let i;
        let hashCode = 0;
        let character;

        // If value to be hashed is already an integer, return it.
        if (val.length === 0 || val.length === undefined) {
            return val;
        }

        for (i = 0; i < val.length; i++) {
            character = val.charCodeAt(i);
            hashCode = ((hashCode << 5) - hashCode) + character;
            hashCode = hashCode & hashCode;
        }

        return hashCode % this.maxBucketCount;
    };

The return value is the index in bucket.

Add

 // add key/data pair to bucket
    add(key, data) {
        let newNode = new Node(key, data);
        let hashCode = this.hashCode(key); // get hashcode of key

        // if no element exists at hashcode of key, add to table
        if (this.buckets[hashCode] === undefined) {
            this.buckets[hashCode] = newNode;
            return;
        } 

        // if an element exists at hashcode of key, but keys are same
        // update key with given data
        if (this.buckets[hashCode].key === key) {
            this.buckets[hashCode].data = data;
            return;
        }

        // if an element exists at hashcode of key, but keys are different
        // collision has occured
        // store in linked list
        let current = this.buckets[hashCode];
        while (current.next !== null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.previous = current
    }

Remove

remove(key) {
        let hashCode = this.hashCode(key); // get hashcode of key
        let first = this.buckets[hashCode] //select key/data pair at index

        if (first !== undefined) {
            // if it exists and no has linked list at index
            // (A)
            if (first.next === null) {
                this.buckets[hashCode] = undefined; // remove item
                return;
            } else {
                while (first !== null && first.next !== null && first.key !== key) {
                    first = first.next;
                }
                // if removed is first node in list
                // (A) - B - C - D
                if (first.previous === null && first.next !==null) {
                    while (first.next !== null) {
                        first.key = first.next.key;
                        first.data = first.next.data;
                        first.next.previous.data = first.data
                        first.next.previous.key = first.key
                        first = first.next;
                    }
                }

                // if removed is last node in list
                // A - B - (C)
                if (first.previous !== null && first.next === null) {
                    first.previous.next = null
                    first = null
                    return;
                }

                // if removed is middle node
                // A - (B) - C
                if (first.previous !== null && first.next !== null) {
                    first.previous.next = first.next;
                    first.next.previous = first.previous;
                    first = null;
                    return;
                }
                return;
            }
        }
        return undefined;
    }

We get the index of the array, and remove item from linked list. We also update the previous and next values of the removed node accordingly.

Find

 find(key) {
        let hashCode = this.hashCode(key);
        let current = this.buckets[hashCode];
        if (current !== undefined) {
             // if it's the first item in list
            if (current.next === null && current.key === key) {
                return current.data;
            } else {
                while (current != null && current.next != null && current.key !== key) {
                    current = current.next;
                }
                if (current.key === key) {
                    return current.data;
                }
                return undefined;
            }

        }
        return undefined;

    }

Check out my repository here.

Binary Trees

Ivy-Walobwa — Wed, 15 Apr 2020 08:33:56 +0000

A binary tree is a sorted hierarchy of data.

It consists of;
1.A root node
2.0-2 children

The structure is such that the smallest values are on the left child node while the largest values on the right child node.

Implementations

Create the node class and binary tree class

class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree{
    constructor() {
        this.root = null;
    }
//add methods
}

Our node contains the data, left and right child. Our binary tree has a root node which is set to null.

2.Add methods to class

(i).Adding Data
We add data to the binary tree using a recursive algorithm.
case 1 -> empty tree: new node becomes the root node
case 2 -> smaller value: recursively added to the left
case 3 -> larger value: recursively added to the right
equal value -> treat as a larger value

add(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        }
        else {
            this._addTo(this.root, newNode);
        }
    }

    _addTo(currentNode, newNode) {
        if (newNode.data < currentNode.data) {
            if (currentNode.left === null) {
                //if new node is less than the current node
                //add to left
                currentNode.left = newNode;
            } else {
                this._addTo(currentNode.left, newNode);
            }
        } else {
            //if new node is greater than/ equal to the current node
            //add to right
            if (currentNode.right === null) {
                currentNode.right = newNode;
            } else {
                this._addTo(currentNode.right, newNode);
            }

        }
    }

I put an underscore before the addTo method to hint me that it is meant to act as a private method.

(ii).Searching

 //try find data in tree
    contains(data) {
        let current = this.root;
        let parent = null

        //while we don't have a match
        while (current !== null) {
            if (data < current.data) {
                //if value is less than current, go left
                parent = current;
                current = current.left;
            } else if (data > current.data) {
                //if value is greater than current, go right
                parent = current;
                current = current.right;
            } else {
                //we have a match
                break;
            }
        }
        return[ current, parent ];
    }
    find(data) {
     //return first value returned by contains() method
        return this.contains(data)[0];
    }

While implementing the remove operation, I realized I needed to check if the node to be removed exists and return the node and its parent. Adding the contains method saved me from duplicating code.
The contains method checks if a node exists and if it does, returns an array containing the found node and its parent.
The find method returns the first value of the array which is the node we are looking for.

(iii)Remove
This was honestly a tough one for me. Took me more than 8hrs to understand how it works.

A simple walk through before we jump into code 😉 .

find node to be deleted
    if node does not exists, exit
if node is terminal node
    remove parent's pointer to the deleted node
if node is not terminal node
    find the child to replace the deleted node

Three scenarios in finding the child to replace deleted node:

1.Removed node has no right child - The left child replaces the removed node

2.Removed node has a right child that has no left child - right child replaces the removed node

3.Removed node has a right child which has a left child - the right child's left most child replaces the removed node

The code

  remove(data) {
        let parent = this.contains(data)[1];
        let current = this.find(data);

        if (current === null) {
            return false;
        }

        //CASE 1
        //removing node with no right child
        //its left child replaces the removed node
        if (current.right === null) {
            if (parent === null) {
                //if we are removing root node
                this.root = current.left;
            } else {
                if (parent.data > current.data) {
                    //make current left child, left child of parent
                    //rare case
                    parent.left = current.left;
                } else if (parent.data < current.data) {
                    //make current left child, right child of parent
                    parent.right = current.left;
                }
            }
        }

        //CASE 2
        //removing node whose right child has no left child
        //right child replaces the removed node
        else if (current.right.left === null) {
            //move removed node left child to the left of removed's right
            current.right.left = current.left;
            if (parent === null) {
                this.root = current.right;
            } else {
                if (parent.data > current.data) {
                    //make current right child a left child of parent
                    parent.left = current.right;
                } else if (parent.data < current.data) {
                    //make current right child a right child of parent
                    parent.right = current.right;
                }
            }

        }

        //CASE 3
        //if removed node's right child has a left child
        //replace removed with its right child's left most node
        else {
            //find right leftmost child
            let leftMost = current.right.left;
            let leftMostParent = current.right;
            while (leftMost.left != null) {
                //move to the left most node of the right child
                leftMostParent = leftMost;
                leftMost = leftMost.left;
            }
            //the parent's left subtree becomes the leftmost's right subtree
            leftMostParent.left = leftMost.right;
            //assign leftmost's left n right to current's left n right
            leftMost.left = current.left;
            leftMost.right = current.right;
            if (parent === null) {
                this.root = leftMost;
            }
            else {
                if (parent.data > current.data) {
                    //make leftmost the parent's left child
                    parent.left = leftMost;
                } else if (parent.data < current.data) {
                    //make leftmost the parent's right child
                    parent.right = leftMost
                }
            }
        }
        return true;

    }

(iv). Tree Traversal
Here we enumerate nodes in a well defined order.

Basic Algorithm;

Process Node
Visit left
Visit right

There are three common orders. They vary in the steps.

Preorder traversal

Process Node
Visit left
Visit right

Postorder traversal

Visit left
Visit right
Process Node

Inorder traversal

Visit left
Process Node
Visit right

The code

  //TREE TRAVERSAL
    preorder(current) {
        if (current === null) {
            return;
        }
        console.log(current.data);
        this.preorder(current.left);
        this.preorder(current.right);
    }

    postorder(current) {
        if (current === null) {
            return;
        }
        this.postorder(current.left);
        this.postorder(current.right);
        console.log(current.data);
    }

    inorder(current) {
        if (current === null) {
            return;
        }
        this.inorder(current.left);
        console.log(current.data);
        this.inorder(current.right);
    }

Sample test code

const tree = new BinaryTree();
tree.add(4);
tree.add(2);
tree.add(1);
tree.add(3);
tree.add(6);
tree.add(5);
tree.add(7)
tree.find(6);
tree.remove(6)

tree.postorder(tree.root) // 1 3 2 5 7 6 4
tree.preorder(tree.root) // 4 2 1 3 6 5 7
tree.inorder(tree.root) // 1 2 3 4 5 6 7

Note:Different helper methods can be declared as per requirements.

Priority Queue

Ivy-Walobwa — Sun, 12 Apr 2020 20:32:42 +0000

A priority queue does not work on First in First Out principle rather it returns item with highest priority.
We will be designing a priority queue in which we add elements to the queue according to its priority(ie;first item in queue has highest priority)

Properties of our Priority Queue

1.Each item has a priority number associated with it.
2.Items added to queue as per their priority.
3.Items with lowest priority numbers are removed first(first item in queue).

Implementations

1.Create item and queue class

class Item {
  constructor(data, number) {
    this.data = data;
    this.number = number;
  }
}

class PriorityQueue {
  constructor() {
    this.items = [];
  }
//add methods
}

The item class stores the item data and it's priority number.
The the priority queue class instantiates an array used to store items.

2.Add methods to class

Enqueue

enqueue(data, number) {
   //create new item
    let item = new Item(data, number);
    let addedFlag = false;

      //loop through array, to end of array
      for (let idx = 0; idx < this.items.length; idx++) {
        //if new item has a lower number
        //add new item before current item
        if (this.items[idx].number > item.number) {
            this.items.splice(idx, 0, item);
            addedFlag = true;
            break;
        }
    }
//default action is to add item at the end of queue
    if (!addedFlag) {
      this.items.push(item);
    }
    }

The enqueue method adds item to queue according to it's priority. A higher number given to item means the item has a lower priority compared to item with a lower number.
Example;
item A with priority number 2 and item B with priority number 1. Item B is of a higher priority than A. Hence A is pushed to end of queue and B front of queue.

Dequeue

dequeue() {
        //if empty do nothing else remove first item in queue
        if (this.items.length === 0) {
            return;
        }
        this.items.shift()
    }

peek

peek() {
        //if not empty return first item in queue
        if (this.items.length === 0) {
            return "Empty queue";
        }
        return this.items[0].data;
    }

Test Code

const queue = new PriorityQueue();
queue.enqueue(3, 4);
queue.enqueue(6, 5);
queue.enqueue(7, 3);
queue.enqueue(8, 1);
queue.dequeue()//removes 8 from queue
console.log(queue.peek()) //prints 7

console.log(queue);

Queue: Array as Storage

Ivy-Walobwa — Sat, 11 Apr 2020 20:13:10 +0000

Implementing a queue using arrays in JavaScript is quite simple.
You use the push() and shift() methods provided for Arrays.

Implementation

1.Create queue class

class Queue{
    constructor() {
        this.items = [];
    }
//add methods
}

We create an items array to store our data

2.Add methods to class

We'll implement the enqueue, dequeue and peek operation on queues.

Enqueue

  enqueue(data) {
        //add data to end of queue
        this.items.push(data);
    }

The push method on arrays, adds data to end of queue.

Dequeue

    dequeue() {
        //if empty do nothing else remove first item
        if (this.items.length === 0) {
            return;
        }
       //return this.items.shift()
        this.items.shift()
    }

The shift() method removes the first item in queue and returns it.

Peek

 peek() {
        //if not empty return first item
        if (this.items.length === 0) {
            return "Empty queue";
        }
        return this.items[0];
    }

This returns the first item in queue.

Pretty straightforward.

Queue: Linkedlist as storage

Ivy-Walobwa — Fri, 10 Apr 2020 18:48:01 +0000

Queue

Unlike stack, a queue works on First in First Out(FIFO) principle. Two main operations are done on a queue; enqueue and dequeue.

To enqueue involves adding item to the back of queue while to dequeue involves removing front item in queue.

Linkedlist as storage

Implementing a queue using linkedlist;
1.The head of list is the head(front) of queue
2.The insertLast method is used to enqueue
3.The removeFirst method is used to dequeue

Implemetation

1.Create node and queue class

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
    }
//add methods
}

Our queue has a head(front) and tail(back) item.

2.Add methods to our queue class to perform enqueue, dequeue and peek

Enqueue

//add item to queue
    enqueue(data) {
        let node = new Node(data);
        //if empty, set new node as head and tail
        if (this.tail == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        //add node as last item in queue
        this.tail.next = node;
        //set node as tail
        this.tail = node;
    }

Dequeue

//remove item from queue
    dequeue() {
        //if empty, do nothing
        if (this.head == null) {
            return;
        }
        //remove curent head and set head to next item in queue
        this.head = this.head.next;

        // set tail to null if queue is emptied
        if (this.head == null) {
            this.tail = null;
        }
    }

peek

 //return first item in queue
    peek() {
        if (this.head == null) {
            return "Queue is empty";
        }
        return this.head.data;
    }

I'll be implementing a queue with arrays next, stay tuned.
Happy Coding! 👯

Stack: PostFix Calculator

Ivy-Walobwa — Thu, 09 Apr 2020 19:28:10 +0000

Postfix Arithmetic

Postfix arithmetic means that the operator goes after the two numbers. Example; 6 * 7 becomes 6 7 *. A postfix expression can be an operand in another postfix expression: 6 7 * 1 - is equivalent to (6 * 7 ) - 1.

Using the stack class in 'stack:array as storage', we will evaluate a postfix expression.

Postfix pseudocode

foreach token 
    if token is integer 
        push token
    else if token is operator
        pop right side value
        pop left side value
        evaluate operator
        push result
next

Postfix Calculator

function postFixCalc(expression) {
    //create new stack
    let stack = new Stack();

    //loop through each character in provided expression
    for (let idx = 0; idx < expression.length; idx++) {
        //store each character
        let token = expression[idx];

        //if it's a number, push to stack
        //else pop right side and left side, perform operation and push to stack
        if (!isNaN(token)) {
            stack.push(Number(token));
        } else {
            let rhs = stack.pop();
            let lhs = stack.pop();
            //if right or left side is not available
            if (rhs === "UnderFlow" || lhs === "UnderFlow" ) {
                return "Can't perform postfix calculation";
            }
            switch (token) {
                case '+':
                    stack.push(lhs + rhs);
                    break;
                case '-':
                    stack.push(lhs - rhs);
                    break;
                case '*':
                    stack.push(lhs * rhs);
                    break;
                case '/':
                    stack.push(lhs / rhs);
                    break;
                case '%':
                    stack.push(lhs % rhs);
                    break;
            }
        }

    };
   //return result of calculation
    return stack.pop();
}

Sample test code

console.log(postFixCalc('567*+1-'))

The result should be 46 😄.
Thank you for reading!

Stack: Array as Storage

Ivy-Walobwa — Thu, 09 Apr 2020 09:17:26 +0000

Before writing this, I had a serious debate with myself. Is there a need to implement your own stack using arrays in JavaScript, when the the language itself provides methods, pop() and push(), which are needed in a typical stack???

For the sake of understanding stacks better, I ended up implementing my own, assuming that my stack grows dynamically.

Implementation

1.Create a stack class

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

In our stack class, we declare an array to implement a stack and set the size to -1 (empty).

2.Add methods to stack class to perform push, pop, peek.

push item to stack

push(data) {
        //if an item is provided
        if (data) {
            //add item to array
            this.items.push(data);
            //increase size
            this.size++;
        }
        return;        
    }

Here, an item is added to top of stack.

pop item in stack
The top item in stack is removed and returned. If list is empty Underflow is returned.

pop() {
    //if empty
    if (this.size === -1) {
      return "UnderFlow";
    } else {
        this.size--;
        //return top item in stack
      return this.items.pop();
    }
  }

peek
Returns top element but does not remove it from stack

 peek() {
    //if empty
    if (this.size === -1) {
      return "Empty stack";
    }
    //return top item in stack
    return this.items[this.size];
  }

Example Test Code

let stack = new Stack();
stack.push(3);
stack.push(5);
stack.push(7);
console.log(stack.pop());//7
console.log(stack.peek());//5
console.log(stack)//[3, 5]

Next, I'll be applying my stack knowledge in creating a postfix calculator 😉 .
Happy coding.

Stack: Linked List as storage

Ivy-Walobwa — Wed, 08 Apr 2020 20:08:07 +0000

A stack is a collection in which data is added or removed in Last in First Out order (LIFO).

A stack can easily be implemented using linked list. The top data element is the head where pushing and popping items happen at the head.

Implementation

If you've read on Linked List , this would be simple to work on.
1.We'll create a node and a stack class

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

class Stack {
    constructor() {
        this.head = null;
        this.size = 0;
    }
//add methods here
}

2.We'll add methods to our stack class to perform push, pop and peek operations

Push node to stack
Insert the element into linked list which will be the top node of Stack

    //add data to stack
    //adds on top of stack
    push(data) {
        this.head = new Node(data, this.head);
        this.size++;
    }

pop node from stack
Return top element from the Stack and move the top pointer to the second node of Stack

//remove data on top of stack
    //returns removed data
    pop() {
        if (this.size === 0) {
            return;
        } else {
            //select top node
            let poppedNode = this.head;
            //make second data in stack top node
            this.head = this.head.next;
            //clear popped node's link
            poppedNode.next = null;
            this.size--;
            // console.log(poppedNode);
            return poppedNode.data;
        }
    }

peek
Return the top element.

  //return head node data
    peek() {
        if (this.size === 0) {
            return;            
        } else {
            // console.log(this.head.data)
            return this.head.data; 
        }

    }

Example test code

let stack = new Stack();
stack.push(70);
stack.push(80);
stack.push(90);
stack.pop();
stack.peek();

In the next series, we'll implement a stack using arrays as the storage mechanism.
Happy Learning! ❤️

Singly Linked List

Ivy-Walobwa — Mon, 06 Apr 2020 16:50:21 +0000

This is the most common used linked list. It is a single chain of nodes.

The Node

In singly linked list, each node contains two parts; data and a link to next node.

Linked List

Singly Linked List contains a header pointer which contains address of the first node (the head node). Forward sequential movement, only, is possible here.
Note that the last node has it's link part set to null

Implementation

First we'll create a node class which we will instantiate when we want to create a node.

class Node {
  constructor(data, next = null) {
    this.data = data;
//link to next node
    this.next = next;
  }
}

The link to next node is set to null for a single node.

We then create a Linked List class

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

For an empty list, head is null and the size is 0.

We then need to add methods in our linked list class to perform various operations such as add, remove and find.

Add node to start of list

 insertFirst(data) {
    this.head = new Node(data, this.head);
    this.size++;
  }

If the list was empty, the new node is set as the head and the link is set to null.
If the list was not empty, the new node is set as the new head and it's link set to the previous head.
The size of list is increased by one.

Add node to end of list

insertLast(data) {
    let node = new Node(data);
    let current;
    //if list is empty, make new node the head
    if (this.size === 0) {
      this.head = node;
    } else {
      //select head as current node
      current = this.head;
      //go to end of list
      while (current.next) {
        current = current.next;
      }
      //add new node as next value of the last node
      current.next = node;
    }
    this.size++;
  }

The while loop terminates if current.next is null and the new node is added as it's value. The size of list is increased by one.

Remove first node of list

  removeFirst() {
    if (this.size !== 0) {
      this.head = this.head.next;
      this.size--;
      if (this.size === 0) {
        this.head = null;
      }
    }
  }

If the list is not empty, the head is removed and replaced by the next node.
The size is decreased

Remove Last node of list

 removeLast() {
    let current, previous;
    //if list is not empty
    if (this.size !== 0) {
      //if list contains one node
      if (this.size === 1) {
        this.head = null;
      } else { 
         current = this.head;
        //go to end of list
        while (current.next) {
          previous = current;
          current = current.next;
        }   
        //remove last node
        previous.next = null;       
      }
      this.size--;
    }
  }

Current and previous variables hold the current node and previous node respectively.

Find index of node in list

findIndexOf(data) {
    let idx = 0;
    //set current to first node
    let current = this.head;
    //iterate over list
    while (current) {
      if (current.data === data) {
        console.log(idx)
        //return index of item
        return idx;
      }
      //increase index by one 
      idx++;
      //move to next node and recheck
      current = current.next;
    }
    console.log(-1);
    //not found
    return -1;
  }

Starting from the head, we check if data in current node equals the data in question and return it's index. After each check the index counter increases by one. If the data is not in the list -1 is returned.

Print Linked List Data

printListData() {
    //set current to first node
    let current = this.head;
    //iterate over list
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

Clear List

  clearList() {
    this.head = null;
    this.size = 0;
  }

Example test code;

//create empty list
const list = new LinkedList();

list.insertLast(400);
list.insertLast(500);
list.insertFirst(600);
list.findIndexOf(500)

console.log(list);
list.printListData();

Thank you for reading ❤️ .