Kashu_happy

Posted on Feb 18, 2022 • Updated on Mar 4, 2022

Introduction to Data Structures and Algorithms With Modern JavaScript.

#javascript #webdev

A data structure, in more technical terms, is a collection of data values, their connections, and the functions or operations that may be performed on the data.

1. Arrays.

An array is a single variable in JavaScript that keeps numerous elements,unlike other languages where array is a reference to several variables. When we wish to keep a list of elements and retrieve them with a single variable, we utilize it frequently.

In JavaScript, an array may hold different items such as Boolean, strings, and numbers, all of which can be stored in a single array.

1.1 Declaring an Array.

An array can be declared in one of the following two ways:

// Method 1:
let arr = [];

// Method 2:
let arr = new Array();

Method 1 is the most commonly used and preferred method above method 2 because when initializing;
Method 1:

// initialization and declaring
let arr = ["mango", "pineapple"];

Method 2:

// initialization and declaring
// array has 3 elements/strings
let arr = new Array ("Toyota", "Audi", "Porshe");

//array has 4 elements that are defined
let arr1 = new Array (1, 2, 3, 4);

//array has 4 undefined elements
let arr2 = new Array (4);

It is evident from the above example that arr1 has 4 items, however arr2 has 4 undefined elements instead of a single element 4. As a result, method 2 is not favored when working with integers, but it is good when working with Boolean and strings, as illustrated above.

In method 2 startup of part 3 can, however, be changed to:

//First create an array of 4 undefined elements
let fruits = new Array(4);

// Assign the array values
fruits[0] = "mango";
fruits[1] = "apple";
fruits[2] = "banana";
fruits[3] = "orange";

1.2 Accessing Items in an Array.

Because arrays are indexed from 0, a number in square brackets is used to access elements in an array.

let fruits = ["mango", "apple", "banana"];
console.log(fruits[0]); // mango
console.log(fruits[1]); // apple
console.log(fruits[2]); // banana

We already know that 0 always produces the first item in an array. You can use the length property, which we'll discuss later, to retrieve the final element in an array by performing the following procedure.

let fruits = ["mango", "apple", "banana"];
const lastItem = fruits.length -1;
console.log(fruits[lastItem]); // banana

//attempting to access a nonexistent element
console.log(fruits[5]); // returns undefined

You need add another index that corresponds to the inner array to be able to retrieve an item in a nested array.

let nestedArray = [
    [
        "mango",
        "banana",
    ],
    [
        "orange",
        "avocado",
    ]
];
console.log(nestedArray[1][1]); // avocado

1.3 Length property of an Array.

The number of elements in an array is returned using the length property of arrays.

An array's length attribute can be returned as:

let fruits = ["mango", "apple", "banana"];
console.log(fruits.length); // 3

However, to set the number of elements in an array, we may use the assignment operator with the length property.

let fruits = ["mango", "apple", "banana"];
fruits.length = 2;
console.log(fruits.length); // 2

1.4 Adding an Item to an Array.

We may assign a value to the next index to add a new value to our fruit variable, which has 3 items in the indices 0 to 2.

let fruits = ["mango", "apple", "banana"];
fruits[3] = "grape";
console.log(fruits);

Output:

[ 'mango', 'apple', 'banana', 'grape' ]

Push() can be used to add an item at the end of an array to avoid scenarios when you mistakenly skip an index while adding an item, resulting in an empty item or items in the array.

let fruits = ["mango", "apple", "banana"];
fruits.push("pineapple");
console.log(fruits);

Output:

[ 'mango', 'apple', 'banana', 'pineapple' ]

The unshift() function, on the other hand, may be used to add an item to the beginning of an array.

let fruits = ["mango", "apple", "banana"];
fruits.unshift("pineapple");
console.log(fruits);

Output:

[ 'pineapple', 'mango', 'apple', 'banana' ]

1.5 Removing an Item from an Array.

We utilize the splice() function to remove or delete a specific item from an array.

let fruits = ["mango", "apple", "banana"];
fruits.splice(1, 1);
console.log(fruits);

Output:

[ 'mango', 'banana' ]

There should be two parameters when using the splice() function. The first parameter specifies the index number to be eliminated (in our case, 1), while the second specifies the number of items to be removed. Otherwise, when one parameter is entered, the item in the index number enter is deleted, along with all subsequent items.

To delete the first item and the last item of an array, use the shift() and pop() methods, respectively. When feasible, however, it is preferable to use the pop() method since the rest of the items in the array will maintain their original index numbers.

//using pop() to remove last item
let fruits = ["mango", "apple", "banana", "pineapple"];
fruits.pop();
console.log(fruits);

//using shift() to remove first item from the remaining items
fruits.shift();
console.log(fruits);

Output:

[ 'mango', 'apple', 'banana' ]
[ 'apple', 'banana' ]

1.6 Looping Through an Array.

To loop through an array, we may use the for keyword to loop through the full array, taking use of the length parameter.

//create an array of vehicles
let vehicles = [
    "trucks",
    "vans",
    "buses",
    "lorries"
];

//loop through the length of the array
for (let i = 0; i < vehicles.length; i++) {
    console.log(i, vehicles[i]);
}

Output:

0 'trucks'
1 'vans'
2 'buses'
3 'lorries'

Although it does not obtain the index of each item, using for...of loop is a simpler and more succinct approach of looping through an array.

//create an array of vehicles
let vehicles = [
    "trucks",
    "vans",
    "buses",
    "lorries"
];

//loop through each vehicle
for (let vehicle of vehicles) {
    console.log(vehicle);
}

Output;

trucks
vans
buses
lorries

2. Queue

The FIFO (First in, First Out) principle governs the operation of a queue. Queue, like Stack, is a linear data structure. The name queue is derived from the analogy of a client waiting at a bank. The client who arrives first is served first, while the customer who arrives later is lined at the back of the queue and will be served later.

Implementing a Queue.

An array may be used as a queue by employing the two Array methods, push() and shift(). In this scenario, the push() function corresponds to an enqueue action, but the shift() method corresponds to a dequeue operation.

Below is an example of a queue class,

class Queue {
    constructor () {
        this.data = [];
        this.rear = 0;
        this.size = 8;
    }
 }

The following variables are used in the above code:

data - array where queue elements are kept.
rear - used to store the position in the queue where the next element will be put.
size - the queue's size, which indicates how many elements are in the queue.

As a result, a queue has two primary operations:

Enqueue inserting a new element at the end of a queue. After adding an element to the queue, we must increment the rear value by 1 such that the rear points to the next place where the next element will be added.

const enqueue = (item) => queue.push(item);

Dequeue removing an element from the front of a queue.

const enqueue = () => queue.shift();

Using enqueue, dequeue, peek() and checking length of a queue

class Queue {
    constructor() {
      this.nums = {};
      this.frontIndex = 0;
      this.backIndex = 0;
    }

    enqueue(num) {
      this.nums[this.backIndex] = num;
      this.backIndex++;
    }

    dequeue() {
      const num = this.nums[this.frontIndex];
      delete this.nums[this.frontIndex];
      this.frontIndex++;
      return num;
    }
    //peek item at the head of the queue
    peek() {
      return this.nums[this.frontIndex];
    }
    // the number of items remaining in the queue
    get length() {
      return this.backIndex - this.frontIndex;
    }
  }

// create an instance of queue
const queue = new Queue();
// enqueue  items into the queue
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(6);
queue.enqueue(8);
console.log(queue.dequeue()); // 2
console.log(queue.peek());    // 4
console.log(queue.length);    // 3

There are various extra ways that may be applied to the queue, in addition to the primary techniques of the queue, which are:

Peek (): used to obtain the value at the front end of the queue.
isEmpty (): used to determine if the queue has elements or is empty.
printQueue (): used to return all of the queue's entries as a string.

3. Stacks

Stacks are linear data structures that only enable actions on one end, which means that all fundamental operations, such as insertion, may only be performed on this end of the stack. This is due to the idea of Last in First Out (LIFO), which states that the data inserted last will be the first to be withdrawn.The diagram below depicts how stacks function.

Push and Pop are the most fundamental operations performed on Stacks. Push adds an element to the Stack in the image above, whereas pop removes the available item on top of the stack.

Basic operations of Stacks.

push() method - inserts items into the stack.

let stack = [];

stack.push(1);
console.log(stack); // [1]

stack.push(2);
console.log(stack); // [1, 2]

stack.push(5);
console.log(stack); // [1, 2, 5]

pop() method - deletes or removes items from the stack. The code below demonstrates how to pop items from the preceding example.

console.log(stack.pop()); // 5
console.log(stack); // [1, 2]

console.log(stack.pop()); // 2
console.log(stack); // [1]

console.log(stack.pop()); // 1
console.log(stack); // []

console.log(stack.pop()); // undefined

peek() method - obtains the element at the very top of the stack that is recently added.

// prototype chain

Array.prototype.peek = function () {
    if (this.lemgth === 0) {
        throw new Error("can not be found");
    }
    return this[this.length - 1];
}
// create an array
const arr = [2, 4, 6, 8, 10];
//using peek() method
const data = arr.peek();
console.log(data); // 10

isEmpty - checks whether the stack is empty.

//Stack class
class Stack{
    constructor()
    {
        this.data = [];
    }
    isEmpty()
    {
        // returns true if stack is empty
        return this.data.length == 0;
    }
}
let stack = new Stack();
console.log(stack.isEmpty()); // true

Implementing a Stack.

A Stack data structure may be implemented in a variety of ways, the most popular of which being an array and a linked list.

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

    // add item into the array
    push(item) {
        this.items.push(item);
    }

    //returns the last item in the array by removing the item
    // will alter with the size of the array
    pop() {
        return this.items.pop();
    }
    //shows the last item in the array but does not remove the item
    peek() {
        if (this.items.length == 0) {
            return null;
        }
        return this.items[this.items.length - 1];
    }

    //returns the size of the stack
    getSize() {
        return this.items.length;
    }

    //checks if stack is empty or not
    isEmpty () {
        return this.getSize() === 0;
    }
}

//make a new stack
const fruits = new Stack();

fruits.push("mango");
fruits.push("apple");
fruits.push("banana");
console.log(fruits); // Stack { items: [ 'mango', 'apple', 'banana' ] }

console.log(fruits.pop()); // banana
console.log(fruits); // Stack { items: [ 'mango', 'apple' ] }

console.log(fruits.peek()); // apple
console.log(fruits); // Stack { items: [ 'mango', 'apple' ] }

console.log(fruits.getSize()); // 2

console.log(fruits.isEmpty()); // false

4. Linked Lists.

A linked list is a linear data structure that expresses a group of elements by pointing to the next one. This is to mean that, the head is the first element in the linked list, while the tail is the final element.

It is a dynamic structure composed of nodes that point to the next node in succession, producing a list. A node has two properties: data, which can be any time of data, and next, which refers to the next node in the list. Next can be null if it not pointing to any node in the list.

class Node{
    constructor(data){
        this.data = data;
        //this node is not referencing anything
        this.next = null;
    }
}

The following properties must be present in linked list elements:

head - the last element in the linked list.
tail - the last element in the linked list.
size - the number of nodes within the linked list.

// initializing an empty linked list

class LinkedList{
    constructor(){
        this.head = head;
        this.tail = tail;
        this.size = 0;
    }
}

Basic operations of Linked Lists.

insertAt: the function inserts an entry at the specified index.
getAt: the method returns the element at the specified index.
removeAt: the function deletes the element at the specified index.
reverse: the order of the linked list's elements is reversed.
clear: the linked list is cleared.

Implementation of Linked Lists.

An example of linking two nodes:

const node1 = {
    data: 1
}

const node2 = {
    data: 2
}

node1.next = node2;
console.log(node1); // { data: 1, next: { data: 2 } }

Creating a linked list:

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

// const node1 = new Node(10);
// console.log(node1); // Node { data: 10, next: null }