Data Structures in JavaScript

What is Data Structure in JavaScript?

In JavaScript, a data structure refers to a specific format utilized for organizing, managing, and storing data, facilitating efficient access and modification of that data. Put simply, a data structure comprises a set of data values, the connections between them, and the various functions or operations that can be performed on that data.

To put it differently, a data structure can be described as a specific method for storing and arranging data on our devices, aimed at utilizing the data in an efficient and effective manner.

By utilizing data structures in JavaScript, we have the ability to reduce both time and space complexities. An optimal data structure not only consumes the least amount of memory but also demands minimal time for data execution.

How to start learning Data Structure with JavaScript?

In order to master data structures using JavaScript, it is essential to adhere to a series of steps in a logical order.

Let's see the process of learning data structure with JavaScript from scratch:

• ✅ Learn about Time and Space complexities
• ✅ Learn the basics of individual Data Structures
• ✅ Practice Problems with Data structure

Learn about Complexities

In the initial phase, our primary objective for utilizing the data structure is to address challenges in a manner that is both effective and efficient. To determine whether your program operates efficiently, it is essential to assess the complexities associated with it.

There are two types of complexity in DS:

Time complexity

It is utilized to quantify the duration needed to run the code.

Space complexity

This refers to the quantity of memory needed to effectively carry out the operations of a program. Occasionally, you may encounter the term Auxiliary Space frequently in Data Structures and Algorithms (DSA), which denotes the additional memory utilized by the program aside from the input data structure.

Both of the above complexities are measured with respect to the input parameters. But here arises a problem. The time required for executing a code depends on several factors, such as:

• ✅ The number of operations which is performed in the program.
• ✅ The speed of the device and also
• ✅ The speed of data transfer is being executed on an online platform.

Learn Data Structures

Data structures are composed of two fundamental components, which include:

• ✅ Data structure
• ✅ Algorithms

JavaScript provides a diverse array of data structures that enable developers to execute various functions, which are essential for tasks such as data analysis and visualization, as well as for the development of artificial intelligence (AI) and machine learning (ML) algorithms.

Array

In JavaScript, an array represents a group of variables or items of the same type that are allocated in consecutive memory addresses. This data structure is widely regarded for its simplicity and popularity, and it is frequently utilized to build other data structures. The indexing for each element within an array begins at 0.

Array Declaration: Fundamentally, there exist two primary methods for declaring an array.

Syntax

let arrayName = [value1, value2, ... ]; or
let arrayName = new Array();

Types of Array operations

• ✅ Traversal: In the JavaScript array, we traverse through the elements.
• ✅ Insertion: We insert a new element in an array.
• ✅ Deletion: Deleting element from the array in JavaScript.
• ✅ Searching: Search for an element in the array.
• ✅ Sorting: In this, we maintain the order of elements in the array.

Example

// Initializing while declaring
    // Creates an array having elements 5, 10, 15, 20, 25
    var house = new Array(5, 10, 15, 20, 25);
    
    // Creates an array of 5 undefined elements
    var house1 = new Array(5);
    
    // Creates an array with element 2BHK
    var home = new Array("2BHK");
    console.log(house)
    console.log(house1)
    console.log(home)

Output:

[ 5, 10, 15, 20, 25 ]
[ <5 empty items> ]
[ '2BHK' ]

Stack

In JavaScript, a stack represents a linear data structure that maintains a collection of elements. This stack adheres to the LIFO principle, which stands for Last In, First Out. This indicates that the element that was added most recently to the stack will be the first one to be extracted.

At the apex of the stack, two primary operations take place: push and pop. Through the implementation of the push method, it becomes possible to append one or multiple elements to the conclusion of the array. Conversely, utilizing the pop method allows for the elimination of the top element from the end of the array, which is subsequently returned to the calling function.

In JavaScript, stacks are not inherently supported, but they can be implemented quite easily using a standard array:

const stack = [];
//add item to the top
stack.push("value");
//remove the item from the top
const topItem = stack.pop();

In practical applications, the stack data structure can be utilized to monitor user interactions effectively. One notable implementation of this concept is in the creation of functionalities like an undo button.

Operations in a Stack

• ✅ Push: we can add an element to the top of the stack.
• ✅ Pop: This operation is used to remove an element from the top of the stack.
• ✅ IsEmpty: This operation is used to check if the stack is empty.
• ✅ IsFull: This operation is used to check if the stack is full.
• ✅ Top/Peek: We get the value of the top element without removing it.

Example

function Stack() {
    this.count= 0;
    this.storage = {};
    this.push = function (value){
        this.storage[this.count] = value;
        this.count++;
    }
    this.pop = function () {
        if (this.count === 0) {
          return undefined;
        }
        this.count--;
        var result = this.storage[this.count];
        delete this.storage[this.count];
        return result;
      }
    
      this.peek = function () {
        return this.storage[this.count - 1];
      }
    
      this.size = function () {
        return this.count;
      }
}

Queue

In JavaScript, queues bear some resemblance to stacks; however, there is a significant distinction between the two. Unlike a stack, which removes the most recently added element, a queue removes the element that was added first. This data structure functions based on the First In First Out principle, commonly referred to as FIFO.

Operations of Queue

In JavaScript, Queue is an object that helps us to perform some operations, such as:

• ✅ Enqueue: It adds an element to the end of the queue.
• ✅ Dequeue: It is an operation that removes an element from the front of the queue.
• ✅ IsEmpty: It is used to check if the queue is empty.
• ✅ IsFull: It is used to check if the queue is full.
• ✅ Top/Peek: We will get the value of the front of the queue without removing it.

Example

class Queue {
    constructor() {
        this.items = {}
        this.frontIndex = 0
        this.backIndex = 0
    }
    enqueue(item) {
        this.items[this.backIndex] = item
        this.backIndex++
        return item + ' inserted'
    }
    dequeue() {
        const item = this.items[this.frontIndex]
        delete this.items[this.frontIndex]
        this.frontIndex++
        return item
    }
    peek() {
        return this.items[this.frontIndex]
    }
    get printQueue() {
        return this.items;
    }
    // isEmpty function
isEmpty() {
//it will return true if the queue is empty.
return this.items.length == 0;
}

}
const queue = new Queue()
console.log(queue.enqueue(7 ))
console.log(queue.enqueue(2 ))
console.log(queue.enqueue(6 ))
console.log(queue.enqueue(4 ))
console.log(queue.dequeue())
console.log(queue.peek())
var str = queue.printQueue;
console.log(str)

Output:

7 inserted
2 inserted
6 inserted
4 inserted
7
2
{ '1': 2, '2': 6, '3': 4 }

Linked List

In JavaScript, a linked list represents a linear data structure, differing from arrays as it does not store elements in a contiguous block of memory. Fundamentally, a linked list consists of a sequence of nodes, where each node holds essential information, including data and a reference to the subsequent node in the sequence.

Within a linked list, there exists a head pointer that directs to the initial element of the linked list. In the case where the list is devoid of elements, this pointer will instead point to null or remain unassigned.

Operations on the Linked list

• ✅ Traversal: In JavaScript, we can traverse the entire linked list starting from the head node. Now, suppose there are n nodes, then the time complexity for traversal becomes O(n) as we hop through each and every node.
• ✅ Insertion: In JavaScript, insert a key to the linked list. An insertion can be done in 3 different ways: insert at the beginning of the list, insert at the end of the list, and insert in the middle of the list.
• ✅ Deletion: In JavaScript, it removes the element x from a given linked list. We cannot delete a node in a single step. A deletion can be done in 3 different ways: we can delete from the beginning of the list, we can delete from the end of the list, and we can delete from the middle of the list.
• ✅ Search: We can find the first element with the key k in the given linked list by a simple linear search and return a pointer to this element.

Example

// Node class
class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  
  // LinkedList class
  class LinkedList {
    constructor() {
      this.head = null;
    }
  
    // Add a new node to the end of the list
    append(data) {
      const newNode = new Node(data);
      if (!this.head) {
        this.head = newNode;
      } else {
        let current = this.head;
        while (current.next) {
          current = current.next;
        }
        current.next = newNode;
      }
    }
  
    // Print the linked list
    printList() {
      let current = this.head;
      while (current) {
        console.log(current.data);
        current = current.next;
      }
    }
  }
  
  // Create a new linked list
  const myList = new LinkedList();
  
  // Add some nodes to the list
  myList.append(1);
  myList.append(2);
  myList.append(3);
  myList.append(4);
  myList.append(5);
  
  // Print the linked list
  myList.printList();

Output:

1
2
3
4
5

In JavaScript, the tree data structure is categorized as non-linear and features a hierarchical format composed of a collection of nodes. Each node within the tree holds a value along with a list of references pointing to additional nodes.

In different terms, a tree represents a form of nested data structure in JavaScript. It features hierarchical arrangements that consist of a singular node referred to as the parent. This parent node encompasses children, which are elements embedded within the initial root node. Each of these children can also possess additional children nested inside them.

Types of trees

There are some different types of trees in DS, such as:

• ✅ Binary Tree
• ✅ Binary search tree
• ✅ AVL Tree
• ✅ B-Tree
• ✅ Red Black Tree

Operation on tree data structure

• ✅ Insert: We can insert the element in a tree, or we can create a tree.
• ✅ Search: We can also search the elements in the tree.
• ✅ Tree Traversal: The tree traversal algorithm is used in order to visit a specific node in the tree to perform a particular operation on it.

Example

class Node {
    constructor(value) {
      this.value = value;
      this.children = [];
    }
  
    addChild(node) {
      this.children.push(node);
    }
   }
  
  class Tree {
    constructor(root) {
      this.root = new Node(root);
    }
  
    traverse(node = this.root) {
      console.log(node.value);
      node.children.forEach(child => this.traverse(child));
    }
  }
  
  // Example usage:
  let tree = new Tree("A");
  let treeNodeB = new Node("B");
  let treeNodeC = new Node("C");
  let treeNodeD = new Node("D");
  let treeNodeE = new Node("E");
  let treeNodeF = new Node("F");
  
  tree.root.addChild(treeNodeB);
  tree.root.addChild(treeNodeC);
  treeNodeB.addChild(treeNodeD);
  treeNodeB.addChild(treeNodeE);
  treeNodeC.addChild(treeNodeF);
  
  tree.traverse();

Priority Queue

In JavaScript, a priority queue functions in a manner akin to a conventional queue, with the key distinction being the capacity to assign a priority level to every element. This feature enables the elements to be organized based on their respective priorities.

In basic terms, a priority queue is a specific kind of queue that allows for the organization of elements according to their assigned priority levels. Generally, elements that possess higher priority values are extracted prior to those with lower priority values.

It is essential to maintain the elements of the priority queue within a heap structure. In the context of priority queues, the element with the highest priority is consistently located at the root of the heap.

Example

class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(priority, item) {
    this.queue.push({ priority, item });
    this.queue.sort((a, b) => b.priority - a.priority);
  }

  dequeue() {
    return this.queue.shift().item;
  }

  peek() {
    return this.queue[0].item;
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

// Example usage:
const pq = new PriorityQueue();

pq.enqueue(3, "low priority task");
pq.enqueue(1, "high priority task");
pq.enqueue(2, "medium priority task");

console.log(pq.dequeue()); // "high priority task"
console.log(pq.dequeue()); // "medium priority task"
console.log(pq.dequeue()); // "low priority task"

Output:

low priority task
medium priority task
high priority task

In JavaScript, a Map is a collection that organizes elements in the form of key-value pairs. This data structure accommodates various objects, allowing both objects and primitive data types to be utilized as either keys or values.

In JavaScript, when you traverse a map object, it yields the key-value pairs in the exact sequence they were added.

Syntax:

new Map ([it])

Parameter:

It: It refers to any iterable entity where the items are maintained in pairs of keys and values. If the parameter is left unspecified, a new map that is empty will be generated.

Returns: A new Map object

Example

// Original array
const numbers = [1, 2, 3, 4, 5];

// Using map() to create a new array with squares
const squares = numbers.map(function(num) {
  return num * num;
});

console.log(squares); // Output: [1, 4, 9, 16, 25]

Output:

[ 1, 4, 9, 16, 25 ]