DEV Community: Swarup Das

Overview Of SQL Stored Procedures

Swarup Das — Wed, 16 Feb 2022 13:03:39 +0000

Hello Everyone, In the last post, I have covered the basics of how to create and delete Store procedures. In this post, I will go through the below topics and how to use in, Store procedures

Variables
Conditional statement
Switch statement
Loop
Cursors
Variable

Variables

Unlike other programming languages, a Variable is just a placeholder for the actual value. As the meaning of variable is, not consistent or having a fixed pattern; liable to change. Every Variable has 2 things i.e Name and DataType. To define/declare a variable. As shown below :

DECLARE VARIABLE_NAME DATATYPE DEFAULT VALUE

Example :

DECLARE done INT DEFAULT FALSE;

Conditional Statement

To handle the Logical behaviour of the SQL statement, we use the conditional statement. They allow us to handle the condition based upon a particular scenario. As shown below :

IF CONDITION THEN /* Statement */ ENDIF;

or alternative syntax
IF(CONDITION,TRUE VALUE, FALSE VALUE)

If the condition is satisfied, then the code surrounded by the IF block is executed. if the code has else block then the ELSE block is executed. You also have nested block as shown below :


    IF CONDITION THEN
        /* Statement */
        IF CONDITION THEN
            /* Statement */
        ELSE 
            /* Statement */
        ENDIF;
    ELSE 
       /* Statement */
    ENDIF;

To handle cases where the logical behaviour many outcomes. You can also have if-else-if-else or IF-ELSE-IF ladder. As shown below.

    IF CONDITION THEN
        /* Statement */
    ELSE IF CONDITION THEN
       /* Statement */
    ELSE 
       /* Statement */
    ENDIF;

Example :

    SELECT id,
        IF(`qty` > 0 && `stock_status` = 1,'ENABLE','DISABLE') as product_enable
    FROM products;

Switch Statement

An Alternate to IF-ELSE-IF ladder is SWITCH CASE, were operation is performed based upon the input value. As shown below.

WHEN CASE CONDITION THEN /* Statement */ CASE CONDITION THEN /* Statement */ ELSE RESULT END CASE;
Example :

    SELECT id,
        (
        CASE
            WHEN  `qty` > 0 && `stock_status` = 1 THEN 'ENABLE'
            WHEN  `qty` <= 0 && `stock_status` = 0  THEN 'DISABLE'
            END
        ) as product_enable
    FROM products;

Loop Statement

Loop is crucial to any programming language as it allows us to perform the same task iteratively if the condition is true. There are different variant of LOOPS WHILE and just a simple LOOP. As shown below :

WHILE LOOP WHILE expression DO /* Statement */ END WHILE;

Loop will go-on until the condition is satisfied. when false the execution of block stop

LOOP LOOP_NAME: LOOP /* Statement */ END LOOP;

You can leave LOOP if a certain case is true. As shown below :

LEAVE LOOP LOOP_NAME: LOOP IF CONDITION THEN LEAVE LOOP_NAME; END IF; /* Statement */ END LOOP;

Cursors

What is Cursors ?
A cursor allows you to iterate a set of rows returned by a query and process each row individually.

For any MySQL cursor, there are 5 parts ,

Declaration Statement DECLARE CURSOR_NAME CURSOR FOR SELECT_SQL_STATEMENT
Handler Statement : Handler allows us to handle the scenario when the cursor hits the end of the rows. DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;
Open Statement OPEN CURSOR_NAME;
Fetch Statement FETCH CURSOR_NAME INTO VAR1
Close Statement CLOSE CURSOR_NAME;

Complete Syntax :

    DECLARE VAR1  DATA_TYPE;
    DECLARE CURSOR_NAME CURSOR FOR SELECT FIELD FROM TABLE;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

    OPEN CURSOR_NAME;
        FETCH CURSOR_NAME INTO VAR1;
    CLOSE CURSOR_NAME;

Example of Loop & Cursor :

DELIMITER $$
    CREATE PROCEDURE updateStatus()
    BEGIN
        DECLARE done INT DEFAULT FALSE;
        DECLARE id INT;
        DECLARE cursor_products CURSOR FOR SELECT Id FROM products;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

        OPEN cursor_products;

        read_loop: LOOP
            FETCH cursor_products INTO id;
            IF done THEN
                LEAVE read_loop;
            END IF;
            UPDATE products set stock_status=IF(qty>0,1,0) WHERE Id=id;
        END LOOP;

        CLOSE cursor_products;
    END$$
DELIMITER ;

Conclusion:

To learn more about store procedures visit the below reference links as a starting point.

All the Best. To embark on the journey towards the stored procedure. 😊 😊

Happy Coding!
Reference

Overview Of SQL Stored Procedures

Swarup Das — Mon, 14 Feb 2022 14:41:55 +0000

Hello, This Blog is about MYSQL Stored Procedure. Think of it as a beginner guide or intro towards Stored Procedures.To follow along, you must at least know the basics understanding of MYSQL operations like creating a database/ table and simple DML (Data Manipulation Language) queries (INSERT, UPDATE AND DELETE) and DQL (Data Query Language) queries (SELECT).

Feel Free to comment down below you find any mistake or suggestion to improve 😊

Let's start

What ? is Stored Procedure?

In in a simple term, it’s just the bunch of SQL instructions (queries) run together, just like a function in other programming languages.

A stored procedure is a prepared SQL code that you can save, so the code can be reused over and over again. So if you have an SQL query that you write over and over again, save it as a stored procedure, and then just call it to execute it. You can also pass parameters to a stored procedure so that the stored procedure can act based on the parameter value(s) that is passed. – W3School

When ? to use it?

Let say, When you have a set of instructions that need to run one after another sequence and you miss something it’s might be troubling. Run a single query would be tedious. But creating a stored procedure for the mundane task, it would be easy to run in a single stored procedure call.

Where ? to use it?

Periodic processing of data is necessary.

Why ? to use it?

They allow modular programming.
They allow faster execution.
They can reduce network traffic.
They can be used as a security mechanism
If you invoke the same stored procedure in the same session again, MySQL just executes the stored procedure from the cache without having to recompile it.

Below query will run on MariaDB MYSQL but for other SQL, some commands may differ.

Let’s get querying !

For below example, we consider the below Product table

id	name	sku	qty	status
1	Apple	10000034	50	1
2	Pan	10000032	10	0
3	Desktop	10000031	1	1
4	mouse	10000030	23	1
5	graphic card	10000021	56	!

What is DeLimiter? How to change it?

A _delimiter _is a sequence of one or more characters for specifying the boundary between separate, independent regions in plain text or other data streams – wikipedia.org

When you write SQL query, you use the semicolon (;) to separate two statements like the following example:

SELECT name FROM Product;
SELECT sku FROM Product;

In case of SQL Default, Delimiter/End of SQL query is a semicolon (;) But to change the default delimiter to the dollar ($) like the following exampl:

DELIMITER $$

Delimiter Character may consist of single or double characters like // or $$ however you should avoid using backslash since it escapes sequence.

When creating a stored procedure from the command-line, you will likely need to differentiate between the regular delimiter and a delimiter inside a BEGIN END block. To understand better, consider the following example:

CREATE PROCEDURE  PROCEDURE_NAME() 
 BEGIN
 SELECT name FROM customer;
END;

If you enter above code line by line in command line then, MYSQL client will interpret the semicolon (;) as the end of the statement and will throw an exception. So, we temporarily change the delimiter other than the default

🎉How Write your own the Stored Procedure?🎉

We start with by changing the default Delimiter. All the SQL statements will be wrapped around BEGIN and END keyword as below

DELIMITER $$
  CREATE PROCEDURE PROCEDURE_NAME() 
   BEGIN
    /* Procedure code  */ 
    END $$
DELIMITER ;

If a Stored Procedure with the same name already exists, it will throw an exception

procedure with the same name already exists

To Run Stored Procedure Run Below SQL Query

CALL PROCEDURE_NAME();

Drop a Stored Procedure

If a stored procedure is not present, it will throw an exception. To prevent it,we can add a Conditional check [IF EXISTS ] clause

DROP PROCEDURE PROCEDURE_NAME;
    /* OR */
DROP PROCEDURE IF EXISTS PROCEDURE_NAME;

Get the list of stored procedures :

SHOW PROCEDURE STATUS;

Output : –

                  Db: testSP
                Name: udpateStatus
                Type: PROCEDURE
             Definer: root@%
            Modified: 2020-02-24 13:17:58
             Created: 2020-02-24 13:17:58
       Security_type: DEFINER
             Comment: 
character_set_client: utf8
collation_connection: utf8_general_ci
  Database Collation: latin1_swedish_ci

To Filter the result, you just need to add WHERE Clause as below.

SHOW PROCEDURE STATUS WHERE Db= DATABASE_NAME;

Conclusion

In my next post, I will explain more about store procedures like variables, conditions, loop, and cursor.

Data Structures & Algorithms in JavaScript(Hash Table)

Swarup Das — Mon, 07 Feb 2022 12:19:53 +0000

Hello, I’m back with another Data Structure Hash Table. It is a widely used data structure for its faster lookup. Like Arrays where data is stored in an indexed structure, whereas hashtable use hash mapped layout.

So, in general, it consists of two things :

Table: holds the data in an array or an object.
Hash function: To calculate the hash for the elements in the hash table.

What is Hash Table?

A Hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to value. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. - wikipedia

What is Hash Function?

A hash function is any function that can be used to map a data set of arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. - wikipedia

Different of Hash Function :

djb2
loose loose
sdbm

for more information here.

List of Available Methods :

put: Insert an element (it can also update)
remove: Remove an element
get: Get the inserted element

Implementation of Hash Table in JavaScript

if you just want the source code find here.

So, let’s started with defining a class ES6 HashTable; It will be the same as Dictionary.


class HashTable {
    constructor() {
        this.table = {};
    }
}

Hash Function

we will use the lose lose hash function, but you can use any of the above hash function

If its a number return number
If it's not a number then, stringify the key add up all the char with its ASCII value, we can use charCodeAt and divide it with an arbitrary number to work with lower numbers.

    _loseloseHashCode(key) {
        if (typeof key == "number") {
            return key;
        }
        const keyString = toStringFunc(key);
        let code = 0;
        for (let index = 0; keyString < key.length; index++) {
            code += keyString.charCodeAt(index);
        }
        return code % 37;
    }

Before implementing other methods, I want to clarify the differences between a HashMap and HashSet. HashMap behavior is more like a Map or dictionary, whereas elements are hash and stored as key-value pairs. In HashSet is stored as Set. For more information visit here or here.But in this article ,I will explain using hashmap.

Put

Check whether the keys and value in not NULL if yes return false.
If key and value is not null then calculate the hash using the above hash function method.
Set the table property's key as a hash value and value as key-value pairs same as KeyValue class of dictionary.

    put(key, value) {
        if (key != null && value != null) {
            const keyHash = this.getHashCode(key);
            this.table[keyHash] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

Remove

Calculate the hash using the above hash function method.
Check whether the element with the key is present in the table property if not return undefined.
If it's present delete the key in the table.

    remove(key) {
        const keyHash = this.getHashCode(key);
        if (this.table[keyHash]) {
            const value = this.table[keyHash];
            delete this.table[keyHash];
            return value;
        }
        return undefined;
    }

Get

Calculate the hash using the above hash function method.
Check whether the element with the key is present in the table property if not return undefined.

    get(key) {
        const keyHash = this.getHashCode(key);
        return this.table[keyHash] != null ? this.table[keyHash].value : undefined;
    }

you get the full source here.

So, in an ideal case, the Hash function always produces a different hash for any given key.

Eg: Let say , we want to store the list of email address against its name

dave : dave@gmail.com 

john : john@gmail.com

so its hash value will be dave: 9 and john:24 use above hash function.
But that's not the case, it may produce the same set of the hash value for two or more keys. This phenomenon is also known as Collision or Hash collision.

Eg: Now, for

nathan: nathan@gmail.com

sargeras: sargeras@gmail.com

Fig: Hash Collision in Hashtable

for both the hash value will be 5 respectively use above hash function.

What is Hash Collision?

In computer science a hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value, in this case, is derived from a hash function that takes a data input and returns a fixed length of bits - wikipedia

They are various methods to resolve hash collision :

Open Addressing
- Some types of probing are linear probing, double hashing, and quadratic probing
Separate Chaining
Cache-Conscious Collision Resolution

I will explain in detail in my next blogs.

Conclusion

Algorithm	Average	Worst case
Space	O(n)	O(n)
Search	O(1)	O(n)
Insert/Put	O(1)	O(n)
Delete/Remove	O(1)	O(n)

So, stay tuned for the next blog, in which I will cover linear probing.

Data Structures & Algorithms in JavaScript(Dictionary)

Swarup Das — Sun, 05 Jul 2020 11:27:08 +0000

Hello Everyone, this is part 10 in the series of blogs about data structures and algorithms in JavaScript. In this blog, I will cover the Dictionary Data Structure.

What is a Dictionary?

A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value. - Wikibooks

List Of Operations Available

set: insert a new key-value pair in the dictionary.
get: return the value if the key is present.
remove: remove key-value pair from the dictionary if present.
hasKey: check if the key exists for not.
keys: return all the keys in the dictionary.
values: return all the values in the dictionary.
keyValues : return an array containing all the pairs.
forEach: takes callback function to perform an operation on each pair.

A dictionary is also known as a map,symbol table, and an associative array

Implementation of Dictionary in JavaScript

So, Let's start with defining ES6 class Dictionary with a property table; it will hold all the elements.
In a dictionary, the ideal would be to store keys of type string and any type of value (from primitive type such as numbers, a string, to complex objects). However, because JavaScript is not strongly typed, we cannot guarantee the key will be a string .i.e,

We first transform the key whatever object is passed as the key into a string to make it easier to search and retrieve values from the Dictionary class.

Values will be Stored as table[stringify(Key)] = new KeyValues(key,value);

    class Dictionary {
    constructor(toStrFn = toStringFunc) {
        this.table = {};
        this.toStrFn = toStrFn;
        }
    }

Default String Stringify function


function toStringFunc(key) {
    if (key == null) {
        return 'NULL'
    }
    if (key == undefined) {
        return 'UNDEFINED'
    }
    if ((typeof key == "string") || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

Set

When inserting a key-value pair, we will check if the key & value is not null.

Else :

Stringify the key using the default string method
Create a new instance of KeyPair.
Add the stringify value as the key and value as the instance of Keypair.

Dictionary Keys are unique.You can't have two or more keys to the same value . if present then it will just override the old value with the new one.

    set(key, value) {
        if (key != null & value != null) {
            const stringKey = this.toStrFn(key);
            this.table[stringKey] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

KeyValue Class


     class KeyValue{
     constructor(key, value){
         this.key = key;
         this.value = value;
     }
     toString(){
         return `[#${this.key} , ${this.value}]`
     }
 }

HasKey

To check if the key is present or not, We will Stringify the key and check if its present or not.


    hasKey(key) {
        return this.table[this.toStrFn(key)] !== null;
    }

Remove

When removing a key-value pair, We first need to check if the key is present in the Dictionary using the HasKey method. If present then deletes the key-value pair.

    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

get

If a key-value pair, with a key, exists then return value or else null.
As we know that we first we stringify the key and set that as the Object key and value as the instance of KeyValue. ie.

Stringify the key.
Return the stringify key's KeyValue value.


    get(key) {
        const keyValuesPair = this.table[this.toStrFn(key)];
        return keyValuesPair != null ? keyValuesPair.value : null;
    }

KeyValues

This method will return all the stored key-value pair in the Dictionary class,

Initialize an array keyValuePairs
Iterate table property, if the key exists then push to keyValuePairs array
Return the keyValuePairs.

    keyValues() {
        const keyValuePairs = [];
        for (const key in this.table) {
            if (this.table.hasOwnProperty(key)) {
                keyValuePairs.push(this.table[key])
            }
        }
        return keyValuePairs;
    }

Keys

This method returns all the key-value pairs keys. We will evoke the KeyValues extract the keys using Array.prototype.map. Alternative use can also do the same thing using for loop.


    keys() {
        return this.keyValues().map(element => element.key);
    }

Values

This method returns all the key-value pairs values. We will evoke the KeyValues extract the values using Array.prototype.map


    values() {
        return this.keyValues().map(element => element.value);
    }

ForEach

ForEach is an iterator function, Which allows us to loop the all key-value pair present in the Dictionary class. But, the same can be applied for other data structures too.

We evoke the KeyValues and get all the key-value pairs.
We will iterate over the individual pairs and execute the callback until the condition is true.

    forEach(callback) {
        let keyValuePairs = this.keyValues();
        for (let index = 0; index < keyValuePairs.length; index++) {
            const result = callback(keyValuePairs[index].key, keyValuePairs[index].value);
            if (result == false) {
                break;
            }

        }
    }

you get the full source here

Map ES6 ,Is similar to Dictionary .

Conclusion :

Methods	Complexity
set	O(n)
get	O(1)
remove	O(1)
keys	O(n)
values	O(n)
KeyValues	O(n)
forEach	O(n)

So, stay tuned for the next blog, in which I will cover another DS Hash table.

Data Structures & Algorithms in JavaScript(Sets)

Swarup Das — Sun, 21 Jun 2020 17:02:47 +0000

Hello Everyone, this is part 9 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Set.

What is Set?

Sets are a type of associative containers in which each element has to be unique because the value of the element identifies it. The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element - geeksforgeeks

List Of Operations Available

Add: Insert an element in the set if present not.
Delete: Remove an element from the set.
Has : Return true if the an element is present or else return false.
Size: Return Size of the Set.
isEmpty : Check if the set is empty if empty return true else false.
Union: Return new Set which contains all the elements from two sets.
Intersection: Return new Set which contains the intersecting element from two sets.
Difference: Return new Set only containing the elements which are not present in other sets.
isSubset: Return true if all elements are present in the given otherSet.

Set Only Contains Unique Elements in it.

Implementation of Set in Javascript

Let start by defining an ES6 class class name Set that has one property, items which will hold the elements in the set.we are using objects to store elements in the set instead, you can also use an array.

 class Set {
    constructor() {
        this.items = {};
    }
 }

Add

While inserting an element into the Set, we first need to check if it already exists or not. By using has a method.

if the element is already present
- Return false
Else insert an element into the Set.
- Set items property key and value as an element.

 add(element) {
    if (!this.has(element)) {
        this.items[element] = element;
        return true;
    }
    return false;
    }

Has

Check if the element already exists in the set or not.
You can loop until the entire the items and compare the given element with the set elements. If a match is found then return true or else false.
Or you can javascript built-in method of Object.prototype.hasOwnProperty()

 has(element) {
        return Object.prototype.hasOwnProperty.call(this.items, 
 element);
    }

Delete

Remove an element from the set.

Check if the element is already present
- If not present return false.
- Else delete the element from the items property.


 delete(element) {
        if (this.has(element)) {
            delete this.items[element];
            return true;
        }
        return false;
    }

Elements

Return all elements present in the Set

 elements(){
        let elements = [];
        for (const key in this.items) {
            if (this.items.hasOwnProperty(key)) {
                elements.push(key);
            }
        }
        return elements;
    }

Set Data Structure was also introduced in the ES6, javascript all the methods defined until know is present in Standard ES6 Set.

Set Operations

In mathematics, a set also has some basic operations such as union, intersection, and difference.

Union

The union of the sets A and B, denoted by A ∪ B. It is set only contains distinct elements from set A or set B or both.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A ∪ B = { 1,2,3,4,5,6,10 }

otherSet Must be an Instance of Set if not throw an error.
Define a new Union Set.
Loop both the Sets and add elements into the Union Set if not present.

union(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const unionSet = new Set();
        this.elements().forEach(element => {
            unionSet.add(element);
        });
        otherSet.elements().forEach(element => {
            unionSet.add(element);
        });

        return unionSet;

    }

Intersection

The intersection of the sets A and B, denoted by A ∩ B, is the Set of elements belongs to both A and B, only common elements.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A ∩ B = {3,4,5 }

otherSet Must be an Instance of Set if not throw an error.
Define a new Intersection Set.
Loop the Set and add elements into the Intersection Set if and only if, the elements are present in both the Sets.

  intersection(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const intersectionSet = new Set();
        this.elements().forEach(element => {
            if (otherSet.has(element)) {
                intersectionSet.add(element);
            }
        });

        return intersectionSet;
    }

Difference

The difference between sets A and B is denoted by A – B. Only containing elements of set A but not in B.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A – B = {1,2,6}

otherSet Must be an Instance of Set if not throw an error.
Define a new Difference Set.
Loop the Set and add elements into the Difference Set which are not common in otherSet

difference(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const differenceSet = new Set();
        this.elements().forEach(element => {
            if (!otherSet.has(element)) {
                differenceSet.add(element);
            }
        });
        return differenceSet;
    }

isSubset

B is a subset of A, denoted by B ⊆ A or equivalently.if only if all the elements of B are present in A.

otherSet Must be an Instance of Set if not throw an error.
Loop the otherSet check if all the elements are present or not or use every method.

isSubset(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        if (!(otherSet.size() > this.size())) {
            return false;
        }
        let isSubset  = true;
        this.elements().every(element => {
            if (!otherSet.has(element)) {
                isSubset = false;
                return;
            }
        });

        return isSubset;

    }

you get the full source here

Conclusion :

Methods	Complexity
Add	O(n)
Delete	O(1)
Has	O(n)

So, stay tuned for the next blog, in which I will cover another DS Dictionary

Data Structures & Algorithms in JavaScript(Sorted linked list)

Swarup Das — Sat, 30 May 2020 12:57:38 +0000

Hello Everyone, this is part 8 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Sorted linked list.

What is Sorted linked list?

A sorted linked list is a list that keeps its elements sorted. To keep all elements sorted, instead of applying a sorting algorithm. - Learning JavaScript Data Structures and Algorithms Third Edition

List Of Operations Available

All methods will same as the single linked list .we will only overwrite the insert method.

Implementation of Sorted linked list in Javascript

The SortedLinkedList class does not need and additional properties, so we can simply extend the LinkedList Class, only overwrite the required methods.

  class SortedLinkedList extends LinkedList {
    constructor(func, CompareFun = defaultCompare){
        super(func);
        this.CompareFun = CompareFun;
    }
}

Insert

While Insert an element in SortedLinkedList, There are two scenarios:-

SortedLinkedList is Empty
- Called Parent Insert Method and set the index to zero.
SortedLinkedList is Not Empty
- Get the Next Sorted Position/Index using the getNextSortIndex method.
- Called Parent Insert Method and set the index to Next Sorted Position.

    insert(element, index =0){
        if (this.isEmpty()) {
            return super.insert(element,index)
        }else{
            const pos = getNextSortIndex(element);
            return super.insert(element,pos);
        }
    }

GetNextSortIndex

This method returns the sorted index by iteratively comparing the element with the linked list's nodes or until all nodes have been iterated.


    getNextSortIndex(element){
        let current = this.head;
        let i = 0;
        for (; i < current.next != null ; i++) {
            if (this.CompareFun(element,current.element) == Compare.LESS_THAN) {
                return i;
            }
            current = current.next;
        }
        return i;
    }

you get the full source here

Conclusion

The complexity of the Sorted Linked List will be the same as Single Linked List.

So, stay tuned for the next blog, in which I will cover another DS SET

Data Structures & Algorithms in JavaScript(Circular linked list)

Swarup Das — Mon, 25 May 2020 12:59:57 +0000

Hello Everyone, this is part 7 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Circular linked list.

What is the Circular linked list?

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. - geeksforgeeks.org

Fig: Circular Single Linked List

Fig: Circular Doubly Linked List

List Of Operations Available

All methods will same as single linked list. Only overwrite the insert, push and removeAt methods

Implementation of Circular linked list in Javascript

The CircularLinkedList class does not need and additional properties, so we can simply extend the LinkedList Class, only overwrite the required methods.


class CircularLinkedList extends  LinkedList {
     constructor(){
         super();
     }
}

Push

Push method will append an element at the end of the LinkedList. While appending an element (node), There are two scenarios :

LinkedList is Empty.
- set the linked list head property to the new node.
- set new node's next to the head, since circular LinkedList doesn't have a NULL pointer at the end.
LinkedList is Not Empty.
- loop till the end.
- set the End node to the new node i.e end node.next to the node.
- set new node's next to the head. after pushing an element to linked list increment the counter

   push(element){
         let node = new Node(element);
         let current = this.head;
         if (current == undefined) {
             this.head = node;
             node.next = this.head;
         } else {
             while(current.next != null){
                 current = current.next;
             }
             current.next = node;
             node.next = this.head;
         }
         this.count++;
         return this;
     }

Insert

Insert method will insert an element at a given position. The position must be greater than zero and less than or equal to count (length of LinkedList). If not return undefined.

The index is Zero
- Empty
- Same as push method condition, when LinkedList is empty
- Not Empty
- set the new node to the current head
- head to the new node
The index is equal to count .ie length of LinkedList
- Get the (index - 1) element using the getElementAt method, store as the previous Element.
- Set previous to the new node. And node's next to the head.
The index is greater than Zero
- Get the (index - 1) element using the getElementAt method, store as the previous Element.
- The indexed element will be previous. next, store as current.
- Set previous to the new node. And node's next to previous.

after pushing an element to linked list increment the counter

        insert(element,index){
         if (index >= 0 && index <= this.count) {
             const node = new Node(element);
             let current = this.head
             if (index == 0) {
                 if (this.head == undefined) {
                     this.head = node;
                     node.next = this.head;
                }else{
                    node.next = current;
                    this.head = node;
                 }
             }else if (index == this.count) {
                 const previous = this.getElementAt(index -1);
                 previous.next = node;
                 node.next = this.head;
             }else{
                const previous = this.getElementAt(index -1);
                current = previous.next;
                previous.next = node;
                node.next = current;
             }
             this.count++;
             return this;
         }
         return undefined;
     }

RemoveAt

RemovAt method will remove an element at a given position. The position must valid the index's out of bound error, by checking that the position is greater than and equal to zero and less than count. If not return undefined.

LinkedList is Empty
- return undefined
The index is Zero.
- Move the head to the next node.
The index is equal to the count - 1.
- Get the (index - 1) element using the getElementAt method, store as the previous Element.
- Set the previous's next to the head.

The index is greater than Zero
- Get the (index - 1) element using the getElementAt method, store as the previous Element.
- The indexed element will be previous.next, store as current.
- set the previous.next to the current.next.

after removing an element from the linked list decrement the counter

        removeAt(index){
         if (index >= 0 && index < this.count) {
            if (this.isEmpty()) {
                return undefined;
            }
            let current = this.head
             if (index == 0) {
                 this.head = current.next;
             } else if(index == this.count-1) {
                const previous = this.getElementAt(index-1);
                 current = previous.next;
                 previous.next = this.head;
             }else{
                const previous = this.getElementAt(index -1);
                current = previous.next;
                previous.next = current.next;
             }

             this.count --;
             return current.element;
         }
         return undefined;
     }

Get the full source code here

Conclusion :

Complexity will be the same as Single Linked List. This blog only covers a singly circular linked list. But the doubly circular linked list will similar to the doubly linked list.

So, stay tuned for the next blog, in which I will cover another DS Sorted Linked List.

Data Structures & Algorithms in JavaScript(Doubly linked list)

Swarup Das — Thu, 14 May 2020 08:42:54 +0000

Hello everyone, I'm back from my hibernation, I will continue to post the series about data Structure and algorithms, It's also part of my journey towards learning Data structures and algorithms ... once it for all, As in my engineering yrs, I was struggling to write the simple stack code. Looking back .. I have come a long way But now as a full-time developer. I once again decided to learn ds and algorithms to finish it this time.

Being consistent is the key to success...

Thank you dev community

Now Let's get started with part 6 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Doubly linked list.

What is the Doubly linked list?

A Doubly Linked List contains an extra pointer, typically called the previous pointer, together with next pointer and data which are there in the singly linked list. - geeksforgeeks.org

List Of Operations Available

All methods will same as single linked list.We only overwrite the insert, push and removeAt methods.

Implementation of Doubly linked list in Javascript

The doubly linked list is a special type of linked list. We will just extend the linked list class i.e inherit the LinkedList class. we call the parent constructor by super keyword to initialize the count and head properties of the Doubly linked list. besides, it has a tail property which refers to the end of the doubly linked list


class DoubleLinkedList extends LinkedList {
    constructor(func) {
        super(func);
        this.tail = undefined;
    }
}

DoubleLinkedList provides a way of iterating it from start to end or vice versa. We can go forward using next pointer or backward using previous pointer, for this behavior, we will keep track of the previous element in each node, therefore, we will define a DoublyNode Which will extend the Node class, element and next properties will be initialized by parent constructor and a previous property to keep track of the previous element.

class DoublyNode extends Node {
    constructor(element, next, previous) {
        super(element, next);
        this.previous = previous;
    }
}

All methods implementation will be similar to the single linked list. In addition to the next pointer, we also have the previous pointer.

Push

When Pushing an element to a doubly-linked list, we have two scenarios:

Doubly-linked list is empty.
Doubly-linked list is not empty and appends element at the end.

First, We will create a DoublyNode passing element as its value if the head is undefined then assign head pointer to the node ({1}) and also tail ({2}). Since the end node points to the tail pointer.

Secondly, If the doubly linked list is not empty we will define a current variable equal to tail ({3}), points the new node to the current.next ({4}) , node.next to current ({5}) and node.next ({6}) to the tail.


   push(element) {
        let node = new DoublyNode(element);
        if (this.head == undefined) {
            this.head = node; //1
            this.tail = node;  //2
        } else {
            let current = this.tail; //3
            current.next = node; //4
            node.previous = current; //5
            this.tail = node; //6

        }
        this.count++;
    }

Insert

To insert an element at a given the position; We validate the index, ie. index the must be greater than zero and less than and equal to count, there are three scenarios,

Insert an element at the start of the list (Index == 0).
- We check if the list's head is undefined :
  - If undefined then the same as the push method (head is undefined) ({2}). Set head ({3}) and tail ({4}) to the new Node.
  - Else, move the list's head to the new node.Define current variable equal to head ({1}),Set node.next to current ({6}),current.previous to node ({5}) and head to the new Node ({7}).

Insert an element at the end of the list (Index == count).
- This is the same push method. When the list is not empty.

Insert an element at the middle of the list (Index == n).
- Adding an element in the middle of the list. First, need to loop through the list until we reach the desired position. In this case, we will loop to index -1, meaning one position before where we desire to insert a new node.
- When we get out of the loop, the previous variable will be a reference to an element before the index where we would like to insert to new element and the current variable. So first, we link the node's next to current and also current's previous to the node, to change the link between previous and current. we need previous.next to the node and node's previous to the previous.


 insert(element, index) {
        if (index >= 0 && index <= this.count) {

            let node = new DoublyNode(element);
            let current = this.head; //1
            if (index == 0) {
                if (this.head == undefined) { //2
                    this.head = node; //3
                    this.tail = node; //4
                } else {
                    current.previous = node; //5
                    node.next = current;  //6
                    this.head = node;  //7
                }
            } else if (index == this.count) {
                current = this.tail;
                current.next = node;
                node.previous = current;
                this.tail = node;
            } else {
                let previous = this.getElementAt(index - 1);
                current = previous.next;
                previous.next = node;
                node.next = current;
                node.previous = previous;
                current.previous = node;
            }
            this.count++;
        }
    }

RemoveAt

Remove an element at the specified index, we first check if the linked list is empty else return undefined ({1}), After that we valid the index's out of bound error, by check is the index, greater than zero and less than count.there are three scenarios,

Remove an element at the start of the list
- Remove a node from the start, we just move the head node to head's next Node, To do that we first, define a current variable equal to head, set the head to the current.next.
- If the list count is 1 then set the tail to undefined, as end-node points to tail, we need to unset it by setting tail to undefined, else we set head previous to undefined, we need to unlink the previous head node.

Remove an element at the end of the list

Remove an element at the middle of the list


   removeAt(index) {
        if (this.isEmpty()) {
            return undefined;
        }
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index == 0) {
                this.head = current.next;
                if (this.count == 1) {
                    this.tail = undefined;
                }else{
                    this.head.previous = undefined;
                }
            }else if (index == this.count-1){
                current = this.tail;
                this.tail = current.previous;
                this.tail.next = undefined;
            }else{
                current = this.getElementAt(index);
                const previous = current.previous;
                // link previous with current's next
                previous.next = current.next;
                current.next.previous = previous;
            }
            this.count --;
            return current.element;
        }
    }

Get the full source code here

Difference between Single Listed List and Doubly Listed List

Single Listed List	Doubly Listed List
Uses Less Memory	Takes 2x Memory
Simple Implementation	fairly hard Implementation
Cannot easily access the previous element	Can easily access the previous element using the previous property

Conclusion :

Methods	Complexity
insert at head	O(1)
insert at tail	O(1)
search an element	O(n)
remove head element	O(1)
remove any element(removeAt)	O(n)

So, stay tuned for the next blog, in which I will cover another DS Circular Linked List.

Data Structures & Algorithms in JavaScript(Single Linked List) Part 2

Swarup Das — Mon, 23 Dec 2019 10:45:10 +0000

Hello Everyone, this is part 5.2 in the series of blogs about data structures and algorithms in JavaScript, In the previous blog, I had covered the linked list's push, insert and getElementAt methods. In this, I cover the remaining methods removeAt, remove, and indexOf.

Implementation of linked list in Javascript

IndexOf

This method will return the index of the given element if exists else return -1 ({4}) . To find the index of the element, we will start with the head element ({1}) and loop until the element is found ({2}) and returns its index ({3}) .


indexOf(element) {
        let current = this.head; //1
        for (let index = 0; index < this.count && current != null; index++) {
            if (current.element == element) { //2
                return index;
            }
            current = current.next; //3
        }
        return -1; //4
    }

RemoveAt

Remove an element at the specified index, we first check if the linked list is empty else return undefined ({1}) ,After that we valid the index's out of bound error, by check is the index, greater than zero and less than count.

We want to remove the first element i.e index equal to zero ({2}), shift the head to the next node. We will refer to the first element of the list using the current variable. If we assign head to current's next, we will remove the first element ({3}).

We want to remove the last element or an element from the linked list, we will use getElementAt method to get the one previous element using index -1 ({4}), current will be previous's next ({5}). So, to remove the current node, all we have do is to link the previous.next to current.next ({6}).




removeAt(index) {
        if (this.isEmpty()) {
            return undefined; //1
        }        
        if (index >= 0 && index < this.count) {

            let current = this.head
            if (index == 0) { // 2
                this.head = current.next;  //3 
            } else {
                let previous = this.getElementAt(index - 1);  //4               
                current = previous.next; //5
                previous.next = current.next; //6
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

Remove

To remove an element, we check if the linked list is not empty.
If not then get the index of the element using the indexOf method if the index is -1 then the element doesn't exist else use the index and remove the element from the linked list using removeAt method.


remove(element) {
        if (this.isEmpty()) {
            return undefined;
        }
        let index = this.indexOf(element);
        if (index != -1) {
            this.removeAt(index);
        }
        return undefined;
    }

you get the full source here

Conclusion :

Methods	Complexity
indexOf	O(n)
remove head element	O(1)
remove any element(removeAt)	O(n)

So, stay tuned for the next blog, in which I will cover another DS Doubly Linked List.

Data Structures & Algorithms in JavaScript(Single Linked List) Part 1

Swarup Das — Mon, 23 Dec 2019 10:44:58 +0000

Hello Everyone, this is part 5.1 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover linked list.

What is Linked List?

A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. - geeksforgeeks.org

List Of Operations Available

Push: Insert an element at the end of the linked list.
Insert: Insert an element at the given index of the linked list.
Remove: Remove the end element of the linked list.
RemoveAt: Remove the element at the given index of the linked list.
GetElementAt: Get the element at the given index of the linked list.
IndexOf: Return the index of the element in the linked list.

Implementation of linked list in Javascript

Let us define the ES6 class Node, with two properties data and next,
data property will hold, the data which we will insert in the linked list and next property will hold, the pointer to the next Node. A Linked List is just a chain of Node linked to each other by next pointer. What's a pointer? A pointer points to the next member of the list, as you see in the above image.

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

Now, Let's define the ES6 class linked list with three properties,
count to track the number elements in the linked list. the head which will always point to the starting node of the linked list but initially it will be undefined and equalFun to compare two nodes in the linked list . In a single Linked list, we only have a reference to the head node. So to traverse the linked list we always start with the head and walk through it. So, subsequent method we will always start with head.

class LinkedList {
    constructor(func) {
        this.count = 0;
        this.head = undefined;
        this.equalFunc = func || defaultEq;
    }
}

Push

When adding an element at the end of the linked list, there can be two scenarios:

When the head is undefined i.e linked list is empty.
When the linked list is not empty we need to append at the end.

First, we create a Node passing element as its value if the head is undefined then assign head to the node ({1}) else ,we will define a current variable equal to head and loop until we reach the end of the linked list i.e when node's next is null ({2}) and assign the end Node's next to the node ({3}), after adding an element will always increment the count variable ({4}).


push(element) {
        const node = new Node(element);
        let current = this.head;
        if (this.head == undefined) {
            this.head = node;  //1
        }else{
            while (current.next != null) { //2
                current = current.next
            }
            current.next = node; //3
        }
        this.count++ //4;
        return;
    }

GetElementAt

To get an element by its index we will first define a variable node, referring to head ({1}), we valid the index's out of bound error, by check is the index, greater than zero and less than count. ({2}); if not then return undefined ({5}), Now, iterate over the linked list starting from 0 to the index and ({3}), return the node ({4}). This method will be very useful in insert and remove an element from any position in the linked list.


  getElementAt(index) {
        let node = this.head; // 1
        if (index >= 0 && index < this.count) { //2
            for (let i = 0; i < index; i++) { //3
                node = node.next;
            }
            return node; //4
        }
        return undefined; //5
    }

Insert

Insert an element at a given the position; the index must be greater than zero and less than and equal to count, there are two scenarios,
we will first define a variable node which refers to the head.

index is equal to zero ({1})
- check if the head is undefined or not
  - if undefined than head equal to the node
  - else change the head node to the new node and node's next to the previous head.

index is greater than zero ({2})
- adding an element in the middle or at the end of the list. First, need to loop through the list until we reach the desired position. In this case, we will loop to index -1, meaning one position before where we desire to insert a new node
- When we get out of the loop, the previous variable will be reference to an element before the index where we would like to insert to new element, and the current variable .
- So , first we link the node's next to current and then change the link between previous and current. we need previous.next to the node.

insert(element, postion) {
        if (postion >= 0 && postion <= this.count) {
            const node = new Node(element);
            let current = this.head;
            if (postion == 0) { //1
                if (this.head == undefined) {
                    this.head = node;
                }
                this.head = node;
                node.next = current;
            } else {  
                let previous = this.getElementAt(postion - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
            }
         this.count++;
        }
    }

you get the full source here

Conclusion :

Methods	Complexity
insert at any position	O(n)
insert at head	O(1)
GetElementAt	O(n)

So, stay tuned for the next blog, in which I will cover remaining methods of Linked List.

Data Structures & Algorithms in JavaScript(Deque)

Swarup Das — Mon, 09 Dec 2019 17:55:26 +0000

Hello everyone,
Welcome to part 4 of our series on Data Structures and Algorithms in JavaScript. In this blog, we will be covering the _Deque _(Double-ended queue) data structure.

Unlike a traditional Queue, where elements are added at the end of the queue and removed from the front, in a Deque (Double-ended queue), elements can be added or removed from both ends

What is Deque?

In computer science, a double-ended queue (Deque) is an abstract data type that generalizes a Queue, for which elements can be added to or removed from either the front (head) or back (tail) - Wikipedia

Here are the operations and methods for a Deque (Double-ended queue):

AddFront: Insert an element at the front of the Deque.
AddBack: Insert an element at the back of the Deque.
RemoveFront: Remove an element from the front.
RemoveBack: Remove an element from the back.
PeekBack: This method returns the last element of the Deque, similar to the queue's front method.
PeekFront: This method returns the first element of the Deque, similar to the stack's peek method.
Size: Return the size of the Deque.
isEmpty: Check if the Deque is empty. If it's empty, return true; otherwise, return false.
Clear: Reset the Deque.

These methods allow you to manipulate and query a Deque efficiently for various use cases.

Implementation of Deque in Javascript

Deque class is similar to queue.


class Deque {
    constructor() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }
}

AddBack

Deque addback method is similar to queue's enqueue method.


addBack(element) {
        this.items[this.count] = element;
        this.count++;
    }

AddFront

When adding an element at the front Deque, There are three scenarios,

If the Deque is Empty then same as addBack method ({1})
When an element is removed from the front of the Deque ({2}),lowestCount will be greater > zero,
- Then decrement the count
- Assign the element to that object key.
If the lowestCount is equal to zero then, we need to shift the element by one position right and free the first position and assign the element to that object key ({3})


  addFront(element) {
        if (this.isEmpty()) {             //1
            this.addBack(element);
        } else if (this.lowestCount  > 0) {    //2
            this.lowestCount --;
            this.items[this.lowestCount] = element;
        } else {                                //3
            for (let index = this.count; index > 0; index--) {
                this.items[index] =  this.items[index -1];
            }
            this.count ++;
            this.items[0] = element;
        }
     return true;
    }

For removing an element from the Deque, we first need to check, if the Deque is not Empty else return undefined.

RemoveFront

While an element from the front of the Deque is as dequeue method of Queue


    removeFront() {
        if (this.isEmpty()) {
            return undefined;
        }

        let result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;

    }

RemoveBack

While an element from the back of the Deque is as pop method of the Stack


   removeBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        let result = this.items[this.count - 1];
        delete this.items[this.count - 1];
        this.count--;
        return result;
    }

size,clear,isEmpty will be same as queue methods

you get the full source here

Conclusion :

Methods	Complexity
addback	O(1)
addfront	O(1)
removeFront	O(1)
removeBack	O(1)

So, stay tuned for the next blog, in which cover another DS LinkedList.

Data Structures & Algorithms in JavaScript(Queue)

Swarup Das — Sun, 08 Dec 2019 13:40:06 +0000

Hello Everyone, Welcome to the 3rd part of the series on JavaScript Data Structures and Algorithms. In the 2nd part, we discussed the Stacks Data Structure, but in this article, we will discuss the Queue Data Structure.

What is the Queue?

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is FIFO(First In First Out)
-geeksforgeeks.org

A real-world example of a queue can be people standing at the bus stop where the first standing in the line will be the first person to get out of the line i.e. first in first out. If you compared it to a stack, the last person will be the first to leave.

This article will go through a list of following Queue DS,

Queue.
Deque(Double-ended queue).

List Of Operations Available

Enqueue : Insert an element at the end of the queue.
Dequeue : Remove an element from the front of the queue.
Front : Return the first element of the queue.
Size : Return Size of the queue.
isEmpty : Check if the queue is empty if empty return true else false.
Clear : Reset the queue.

Implementation of Queue in Javascript

Let’s define ES6 class name Queue, with properties :

count : To track the number of elements.
items : A Javascript object which will hold all the elements.
lowestCount : since we will be removing an element from the front of the queue, we also need a variable to help us track the first element.


class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}

Enqueue

Inserting an element in the queue is similar to Stack’s push method and Array’s push method, which add the elements at the end.


 enqueue(element){
         this.items[this.count] = element;
         this.count ++;
     }

Dequeue

Removing an element from the Queue, we have two scenarios;

If empty, return undefined.
Else store the lowestCount property element in a variable, To return an element after deletion, Delete the lowestCount item & increment the count by one. The dequeue method is similar to Array’s shift method.


   dequeue(){
         if (this.isEmpty()) {
             return undefined;
         }
         let result = this.items[this.lowestCount]; 
         delete this.items[this.lowestCount]; 
         this.lowestCount ++; 
         return result; 

     }

Front

This method returns the first element. To get the first element, we can return the lowestCount element


   front(){
         if (this.isEmpty()) {
             return undefined;
         }
         return this.items[this.lowestCount];

     }

Size

This method will return the size of the queue which is count minus the lowestCount.


size() {
        return this.count - this.lowestCount;
    }

Example:-In the below queue items object, If the zeroth element was removed from the front, the lowest count will be one. The total count of the element will be two, therefore, the size will count-lowest count


let queue = {
   1: "1",
   2: "2",
}

isEmpty

isEmpty will return true if the queue is empty.


 isEmpty() {
         return this.size() === 0;
    }

Clear

To clear all the elements from the queue, we can evoke the dequeue method until it returns undefined or we can simply reset the value of the Queue class properties to the same values as declared in its constructor method.

 clear() {
    this.items = {}
    this.count = 0;
    this.lowestCount = 0;
    return this.items;
    }

you get the full source here

Conclusion :

Methods	Complexity
equeue	O(1)
dequeue	O(1)
front	O(1)
size	O(1)

So, stay tuned for the next blog, in which cover another DS Deque.