DEV Community: Nitin Soni

Linked List

Nitin Soni — Tue, 20 May 2025 05:56:18 +0000

A linked list is a linear data structure consisting of a sequence of connected nodes, where each node contains two parts: the data and a reference (or pointer) to the next node in the sequence.

Every linked list starts with a special reference called the HEAD, which points to the first node in the list. The last node is identified by its next pointer being set to NULL, indicating the end of the list.

There are different types of linked lists: singly, doubly, and circular. In this article, we'll focus on the singly linked list.

Note: You might have played the game Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.

Linked List Overview

A Linked List is a linear data structure where each element (called a node) contains:

data: the actual value
next: a reference (or pointer) to the next node in the list

In this implementation, we use a singly linked list, meaning each node points only to the next one.

Structure of the Code

1. Node Class

class Node {
  constructor(data) {
    this.data = data; // value of the node
    this.next = null; // pointer to the next node (initially null)
  }
}

2. LinkedList Class

class LinkedList {
  constructor() {
    this.head = null; // first node of the list
    this.size = 0;    // keeps track of total elements
  }
}

Functionality Explained

1. addElement(element)

Adds a new element at the end of the list.
If the list is empty (this.head is null), the new node becomes the head.
Otherwise, it traverses the list until the last node and appends the new node.

2. insertAt(element, index)

Inserts a new element at a specific position (index).
Handles inserting at the beginning (index === 0).
Traverses to the correct position and inserts the node between prev and curr.

3. removeELement(element)

Removes the first occurrence of the element from the list.
If the element is the head, it updates this.head.
Otherwise, it traverses the list to find and remove the node.
Decrements size on successful removal.

4. getSize()

Simply logs the size of the list.

const linkedlist = new LinkedList();
linkedlist.addElement(2);  // List: 2
linkedlist.addElement(4);  // List: 2 -> 4
linkedlist.addElement(6);  // List: 2 -> 4 -> 6

linkedlist.removeELement(6); // List after removal: 2 -> 4

linkedlist.insertAt(3, 1); // List: 2 -> 3 -> 4
linkedlist.getSize();      // size: 3

Linked List code :

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

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

  addElement(element) {
    const node = new Node(element);

    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }

    this.size++;
  }

  insertAt(element, index) {
    if (index < 0 || index > this.size) {
      return "please enter valid index";
    } else {
      let node = new Node(element);

      let curr, prev;

      // curr = this.head;

      if (index === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        curr = this.head;
        let it = 0;

        while (it < index) {
          it++;
          prev = curr;
          curr = curr.next;
        }

        node.next = curr;
        prev.next = node;
      }
      this.size++;
    }
  }

  removeELement(element) {
    if (!this.head) {
      console.log("List is empty");
      return;
    }

    if (this.head.data === element) {
      this.head = this.head.next;
      this.size--;
      return;
    }

    let current = this.head;
    let prev = null;

    while (current && current.data !== element) {
      prev = current;
      current = current.next;
    }

    if (current && current.data === element) {
      prev.next = current.next;
      this.size--;
    } else {
      console.log("element not found");
    }
  }

  getSize() {
    console.log("size :", this.size);
  }
}

const linkedlist = new LinkedList();
linkedlist.addElement(2);
linkedlist.addElement(4);
linkedlist.addElement(6);

linkedlist.getSize();
console.log(linkedlist.head);
linkedlist.removeELement(6);
linkedlist.insertAt(3, 1);

Linked list Complexities

Time Complexity	Worst Case	Average Case
Search	O(n)	O(n)
Insert	O(1)	O(1)
Deletion	O(1)	O(1)

Space Complexity: O(n)

Applications of Linked Lists

1. Dynamic Memory Allocation

Linked lists allocate memory as needed, making them ideal for systems with constrained or dynamic memory requirements.

2. Implementation of Stack and Queue

Singly linked lists are used to implement stacks (LIFO), and doubly linked lists or circular linked lists can be used for queues (FIFO).

3. Undo/Redo Functionality in Software

Doubly linked lists are used to track history in editors and applications to implement undo and redo operations.

4. Hash Tables (with Chaining)

In separate chaining for collision resolution, each bucket is implemented as a linked list.

5. Graphs (Adjacency List Representation)

Each vertex in a graph can store a linked list of its adjacent vertices.

6. Navigation Systems / Browser History

Doubly linked lists are used to move forward and backward efficiently between pages or routes.

7. Music and Video Playlists

Songs or videos are linked such that users can skip forward or backward.

8. Image Viewer

Viewing images in a slideshow allows navigating to the previous or next image, commonly using doubly linked lists.

9. Polynomial Arithmetic

Terms of polynomials are stored as nodes in a linked list to facilitate operations like addition or multiplication.

10. Memory Management in Operating Systems

Free blocks of memory can be maintained using a linked list for efficient allocation and deallocation.

11. Multilevel Data Structures

Structures like skip lists and adjacency matrices can use linked lists internally.

12. Job Scheduling

Tasks can be queued using a linked list structure in real-time operating systems.

13. Big Integer Arithmetic

For operations on very large integers, digits can be stored in nodes of a linked list.

14. Blockchain (Conceptual)

Though not implemented using traditional linked lists, blockchains follow a linked-list-like structure where each block references the previous one.

15. Circular Buffers

Circular linked lists are used to implement buffers in real-time systems or data streams.

Deque

Nitin Soni — Fri, 16 May 2025 10:31:17 +0000

A Deque (Double-Ended Queue) is a type of linear data structure that allows insertion and deletion of elements from both the front and the rear ends. Unlike a standard queue, it does not strictly follow the FIFO (First In, First Out) principle.

Types of Deque

Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both the ends.
Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both the ends.

Operations on a Deque

Below is the circular array implementation of deque. In a circular array, if the array is full, we start from the beginning.

But in a linear array implementation, if the array is full, no more elements can be inserted. In each of the operations below, if the array is full, "overflow message" is thrown.

Before performing the following operations, these steps are followed.

Take an array (deque) of size n. Set two pointers front = -1 and rear = 0.

1. Insert at the Front

This operation adds an element at the front.

Check if the deque is full.

If the deque is full (i.e. (front == 0 && rear == n - 1) || (front == rear + 1)), insertion operation cannot be performed (overflow condition).
If the deque is empty, reinitialize front = 0. And, add the new key into array[front].
If front = 0, reinitialize front = n-1 (last index).

Else, decrease front by 1.
Add the new key 5 into array[front].

2. Insert at the Rear

This operation adds an element to the rear.

Check if the deque is full.
If the deque is full, insertion operation cannot be performed (overflow condition).
If the deque is empty, reinitialize rear = 0. And, add the new key into array[rear].
If rear = n - 1, reinitialize real = 0 (first index).
Else, increase rear by 1.

Add the new key 5 into array[rear].

3. Delete from the Front

The operation deletes an element from the front.

Check if the deque is empty.

If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.
Else if front is at the last index (i.e. front = n - 1), set front = 0.
Else, front = front + 1.

4. Delete from the Rear

This operation deletes an element from the rear.

Check if the deque is empty.

If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else follow the steps below.
If rear is at the first index (i.e. rear = 0), reinitialize rear = n - 1.
Else, rear = rear - 1

5. Check Empty

This operation checks if the deque is empty. If front = -1, the deque is empty.

6. Check Full

This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front = rear + 1, the deque is full.

Deque Code:

class Deque {
  constructor(size) {
    this.size = size;
    this.arr = new Array(size);
    this.front = -1;
    this.rear = 0;
  }

  isFull() {
    return (
      (this.front === 0 && this.rear === this.size - 1) ||
      this.front === this.rear + 1
    );
  }

  isEmpty() {
    return this.front === -1;
  }

  insertFront(key) {
    if (this.isFull()) {
      console.log('Overflow! Cannot insert at front');
      return;
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else if (this.front === 0) {
      this.front = this.size - 1;
    } else {
      this.front--;
    }

    this.arr[this.front] = key;
    console.log(`Inserted ${key} at front`);
  }

  insertRear(key) {
    if (this.isFull()) {
      console.log('Overflow! Cannot insert at rear');
      return;
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else if (this.rear === this.size - 1) {
      this.rear = 0;
    } else {
      this.rear++;
    }

    this.arr[this.rear] = key;
    console.log(`Inserted ${key} at rear`);
  }

  deleteFront() {
    if (this.isEmpty()) {
      console.log('Underflow! Cannot delete from front');
      return;
    }

    console.log('Deleting from front...', this.front);

    const removed = this.arr[this.front];
    this.arr[this.front] = null;  // <-- clear the slot
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.front === this.size - 1) {
      this.front = 0;
    } else {
      this.front++;
    }

    console.log(`Deleted ${removed} from front`, this.arr);
  }

  deleteRear() {
    if (this.isEmpty()) {
      console.log('Underflow! Cannot delete from rear');
      return;
    }

    const removed = this.arr[this.rear];
    this.arr[this.rear] = null; // <-- clear the slot
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.rear === 0) {
      this.rear = this.size - 1;
    } else {
      this.rear--;
    }

    console.log(`Deleted ${removed} from rear`);
  }

  getFront() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return null;
    }
    return this.arr[this.front];
  }

  getRear() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return null;
    }
    return this.arr[this.rear];
  }

  printDeque() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return;
    }

    let i = this.front;
    let result = [];
    while (true) {
      result.push(this.arr[i]);
      if (i === this.rear) break;
      i = (i + 1) % this.size;
    }
    console.log('Deque contents:', result.join(' -> '));
  }
}

// Example usage:
const dq = new Deque(4);
dq.insertFront(5);
dq.insertRear(6);
dq.insertRear(7);
dq.insertFront(8);
dq.printDeque();  // Expected: 2 -> 5 -> 10 -> 20
dq.deleteRear();  // Expected: Deleted 20
dq.deleteFront(); // Expected: Deleted 2
dq.printDeque(); // Expected: 5 -> 10

Time Complexity

The time complexity of all the above operations is constant i.e. O(1).

Applications of Deque Data Structure

In undo operations on software.
To store history in browsers.
For implementing both stacks and queues.

Circular Queue

Nitin Soni — Wed, 14 May 2025 10:10:39 +0000

A circular queue is a special type of queue where the last element is connected back to the first one, making a circle. This helps in using the available space more efficiently.

A circular queue solves the main problem of a normal queue. In a regular queue, after some insertions and deletions, empty spaces are left at the front that can't be used.

Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This reduces the actual size of the queue.

How Circular Queue Works

A circular queue works using circular increment. This means when we move the pointer forward and reach the end of the queue, we go back to the beginning.

This circular movement is done using modulo division with the queue size. That is :

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular Queue Operations

The circular queue work as follows:

two pointers FRONT and REAR
FRONT track the first element of the queue
REAR track the last elements of the queue
initially, set value of FRONT and REAR to -1

1. Enqueue Operation

check if the queue is full
for the first element, set value of FRONT to 0
circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
add the new element in the position pointed to by REAR

2. Dequeue Operation

check if the queue is empty
return the value pointed by FRONT
circularly increase the FRONT index by 1
for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

Case 1: FRONT = 0 && REAR == SIZE - 1
Case 2: FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

Circular Queue Code:

class CircularQueue {
  constructor(size) {
    this.size = size;
    this.items = new Array(size).fill(null);
    this.front = -1;
    this.rear = -1;
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return (this.rear + 1) % this.size === this.front;
  }

  enqueue(element) {
    if (this.isFull()) {
      console.log("Queue is full");
      return;
    }

    if (this.isEmpty()) {
      this.front = this.rear = 0;
    } else {
      this.rear = (this.rear + 1) % this.size;
    }

    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }

    let dequeuedValue = this.items[this.front];

    this.items[this.front] = null;

    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.size;
    }

    return dequeuedValue;
  }

  peek() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return null;
    }
    return this.items[this.front];
  }

  print() {
    console.log(this.items);
  }
}

const circularQueue = new CircularQueue(5);

circularQueue.enqueue(2);
circularQueue.enqueue(3);
circularQueue.enqueue(4);
circularQueue.enqueue(5);
circularQueue.enqueue(9);
console.log(circularQueue.isFull());

console.log(circularQueue.dequeue());
console.log(circularQueue.dequeue());
circularQueue.enqueue(11);
circularQueue.enqueue(12);

circularQueue.isEmpty();
console.log("peek : ", circularQueue.peek());
circularQueue.print();

Circular Queue Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).

Applications of Circular Queue

CPU scheduling
Memory management
Traffic Management

Queue

Nitin Soni — Wed, 14 May 2025 05:40:10 +0000

A queue is a commonly used data structure in programming. It works just like a line of people waiting to buy a ticket — the first person to join the line is the first one to get served.

This follows the First In, First Out (FIFO) rule — the item added first is the one that comes out first.

In the above image, since 1 was kept in the queue before 2, it is the first to be removed from the queue as well. It follows the FIFO rule.

In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.

We can implement the queue in any programming language like C, C++, Java, Python or C#, but the specification is pretty much the same.

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:

- Enqueue: Add an element to the end of the queue
- Dequeue: Remove an element from the front of the queue
- IsEmpty: Check if the queue is empty
- IsFull: Check if the queue is full
- Peek: Get the value of the front of the queue without removing it

Working of Queue

Queue operations work as follows:

Two pointers FRONT and REAR
FRONT track the first element of the queue
REAR track the last element of the queue
initially, set value of FRONT and REAR to -1

Enqueue Operation

check if the queue is full
for the first element, set the value of FRONT to 0.
increase the REAR index by 1
add the new element in the position pointed to by REAR

Dequeue Operation

check if the queue is empty
return the value pointed by FRONT
increase the FRONT index by 1
for the last element, reset the values of FRONT and REAR to -1

Queue Code implementation:

class Queue {
  constructor(maxSize) {
    this.items = new Array(maxSize);
    this.maxSize = maxSize;
    this.front = -1;
    this.rear = -1;
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return this.rear === this.maxSize - 1;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }
    if (this.front === -1) this.front = 0;
    this.rear += 1;
    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.isEmpty()) {
      return 'Queue is empty';
    }

    const removed = this.items[this.front];

    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front += 1;
    }

    return removed;
  }

  peek() {
    return this.isEmpty() ? 'Queue is empty' : this.items[this.front];
  }

  print() {
    if (this.isEmpty()) return [];
    return this.items.slice(this.front, this.rear + 1);
  }

  size() {
    return this.isEmpty() ? 0 : this.rear - this.front + 1;
  }

  clear() {
    this.front = this.rear = -1;
  }
}

const queue = new Queue(4);

queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.enqueue(9);

queue.dequeue();

console.log(queue.peek());
console.log(queue.size());
console.log(queue.print());
queue.clear();
console.log(queue.print());

Limitations of Queue

As you can see in the image below, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.

And we can only add indexes 0 and 1 only when the queue is reset (when all the elements have been dequeued).

After REAR reaches the last index, if we can store extra elements in the empty spaces (0 and 1), we can make use of the empty spaces. This is implemented by a modified queue called the circular queue.

Complexity Analysis

The time complexity of enqueue in a queue implemented using an array is O(1) when inserting at the end (e.g., using push() in JavaScript).
The time complexity of dequeue is O(n) when removing from the front (e.g., using shift()), because all subsequent elements must be shifted one position to the left.

Applications of Queue (Extended List)

1. CPU Scheduling

Processes are scheduled using queues in different scheduling algorithms like FCFS (First Come First Serve), Round Robin, etc.

2. Disk Scheduling

Disk I/O requests are managed in queues to improve seek time and efficiency.

3. Asynchronous Data Transfer (Synchronization)

Queues help buffer data between producer and consumer processes.
Examples: I/O Buffers, Pipes, File I/O, Streams.

4. Interrupt Handling in Real-Time Systems

Hardware interrupts are stored in queues to be handled based on priority or arrival time.

5. Call Center Systems

Incoming calls are queued and answered in the order they are received.

6. Print Queue in Operating Systems

Multiple documents sent to a printer are held in a queue and printed in sequence.

7. Task Scheduling in Operating Systems

Tasks waiting to be executed are placed in a queue by the task scheduler.

8. Breadth-First Search (BFS) in Graphs

BFS uses a queue to explore nodes level by level.

9. Message Queues in Distributed Systems

Systems like RabbitMQ, Apache Kafka, and AWS SQS use queues to manage asynchronous communication between services.

10. Job Scheduling in Batch Systems

Jobs submitted by users are queued and executed one by one or in a time-sharing manner.

11. Network Packet Management

Routers and switches use queues to store packets before processing and forwarding.

12. Order Processing in E-Commerce

Orders are placed in a queue and processed in the order they are received.

13. Buffering in Streaming Services (e.g., YouTube, Netflix)

Video data is buffered in a queue before being rendered on the screen.

14. Customer Service Queues

Tickets or support requests are handled in FIFO order.

15. Simulation Systems (e.g., Airports, Banks)

Queues are used to simulate waiting lines for services.

16. Traffic Management Systems

Vehicles at traffic signals or toll booths are queued before being allowed to pass.

Types of Queue

There are four different types of queues:

- Simple Queue
- Circular Queue
- Priority Queue
- Double Ended Queue

Simple Queue

In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly follows the FIFO (First in First out) rule.

Circular Queue

In a circular queue, the last element points to the first element making a circular link.

The main advantage of a circular queue over a simple queue is better memory utilization. If the last position is full and the first position is empty, we can insert an element in the first position. This action is not possible in a simple queue.

Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

Insertion occurs based on the arrival of the values and removal occurs based on priority.

Deque (Double Ended Queue)

In a double ended queue, insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO (First In First Out) rule.

Understanding Node.js Architecture: Deep Dive into Event Loop, Threads, and Concurrency

Nitin Soni — Mon, 05 May 2025 12:29:05 +0000

Node.js is a popular tool for building fast and scalable server-side applications using JavaScript. But what makes it so powerful? Behind the scenes, Node.js uses a smart architecture that lets it handle many tasks at the same time — without blocking or waiting.

In this blog, we’ll break down how Node.js works, including:

Working of Node.js and architecture
Processes and threads
Synchronous vs. asynchronous behavior
Worker threads
Single threaded and multithreading

What is Node.js?

Node.js is a runtime environment that allows you to run JavaScript on the server. It is built on:

Google’s V8 JavaScript engine: Compiles JavaScript into machine code
Libuv library: Provides the event loop, asynchronous I/O, and thread pool
Node.js core APIs: File system, networking, streams, and more

Node.js uses a single-threaded event-driven model to handle multiple concurrent clients efficiently without spawning new threads for each connection.

Node.js Architecture and Working

Lets understand event loop and how node.js work internally.

Nodejs uses libuv library to run the javascript code in run time environment and also handle asynchronous operations.

Now, understand what is libuv library.

Libuv

libuv is a multi-platform support library that focuses on asynchronous I/O. It is written in C and is used internally by Node.js to abstract away operating system differences, providing:

Event loop implementation
Thread pool
File system operations
Networking support
Timers

Working

Node.js is a runtime environment that allows you to run JavaScript on the server. It’s built on the Google V8 JavaScript engine, Libuv library, and Node.js core APIs (like the file system, networking, etc.).

Despite being single-threaded at its core, Node.js can handle non-blocking operations efficiently. Let's break down how this works:

Main Thread (Master Thread)

When the Node.js server starts, it creates a main thread (sometimes referred to as the master thread), which is responsible for executing the application code. This main thread represents a single process that runs your server.

In this main thread, we have:

Event loop cycle
Event queue
Thread pool

When a request comes to the server, the event queue waits for the request or event. The event loop in the idle/prepare phase waits for requests to process. Once a request arrives, the event loop checks whether the task is blocking or non-blocking.

Blocking vs. Non-Blocking Operations

Blocking Operations: These are operations that block the main thread, causing other tasks in the thread pool to wait. For example, heavy computations, file system operations, or synchronous database queries. When these operations are running, other tasks cannot execute, which can cause the server to slow down.
Non-Blocking Operations: These operations run in the background and don't block the main thread. This allows the event loop to continue handling other tasks while waiting for the non-blocking task to complete. For example, asynchronous operations like setTimeout, file reading, and database queries.

Event Loop and Event Queue

When a request hits your Node.js server (e.g., a login request), it gets handled through the event loop. The event loop processes tasks in two main categories:

🧵 1. Microtask Queue

Includes: Promise.then(), async/await (under the hood), process.nextTick()
Priority: Higher
Executed right after the current code finishes, but before any macrotasks.
Fast, short tasks that must run immediately

🧵 2. Macrotask Queue

Includes: setTimeout(), setInterval(), I/O operations
Priority: Lower
Executed after microtasks are done
Once all tasks are completed, the event loop sends the response to the user.

Login API Example (with both queues)

const express = require('express');
const app = express();
app.use(express.json());

app.post('/login', async (req, res) => {
  console.log('🟢 1. Login request received');

  setTimeout(() => {
    console.log('🟡 4. setTimeout (Macrotask)');
  }, 0);

  Promise.resolve().then(() => {
    console.log('🔵 3. Inside Promise.then (Microtask)');
  });

  console.log('🟢 2. End of login handler');

  res.send('Login successful');
});

app.listen(3000, () => {
  console.log('✅ Server is running on port 3000');
});

Timers, Pending Callbacks, Poll, Check, and Close Callbacks

The Node.js event loop has several phases that manage the execution of asynchronous operations. These phases are:

1. Timers:

Executes callbacks scheduled by setTimeout() and setInterval().
If a timer's time has expired, its callback runs here.

Example :

setTimeout(() => {
  console.log("Timer triggered after 2 seconds");
}, 2000);

2. Idle/Prepare(Internal Phase) :

Used internally by Node.js and libuv.
Prepares for the Poll phase by collecting data and organizing things.
As a developer, you typically don’t interact with this phase, but it ensures the loop functions efficiently.

3. Pending Callbacks: This phase runs delayed system-level operations — mostly things you don’t control directly in your code, but Node.js handles behind the scenes.

Think of it like this:

“If Node.js has some low-level work (like networking errors or TCP socket responses) that couldn’t run right away, it puts them here to be handled later.”

These callbacks are usually added by Node.js C++ internals (libuv) — not your JavaScript code.

✅ Real-world Analogy:

Imagine you're running a server and it tries to connect to a remote server (like for email or file transfer). If the connection fails, the error callback is queued in this phase.

Example:

const net = require('net');

const server = net.createServer((socket) => {
  console.log('Client connected');

  socket.on('error', (err) => {
    console.log('Socket error:', err.message);
  });
});

server.listen(3000, () => {
  console.log('TCP server running on port 3000');
});

If something goes wrong with the TCP connection (e.g., client disconnects abruptly),
The error callback doesn’t run immediately.
It goes into the Pending Callbacks phase, and Node.js handles it when that phase comes around.

4. Poll: Retrieves new I/O events and executes their callbacks (like reading from a file or waiting for DB responses).

If there are no I/O tasks:

If there are setImmediate callbacks waiting, the poll phase ends and moves to check.

Otherwise, it will wait for more I/O events.

Example :

// Simulated DB check
db.query("SELECT * FROM users WHERE email = ?", [email], (err, user) => {
  // This callback runs in the poll phase
});

5. Check:

Executes setImmediate() callbacks.
These are guaranteed to run after I/O tasks and before the next loop iteration.

setImmediate(() => {
  console.log("SetImmediate callback runs in Check phase");
});

6. Close Callbacks:Runs cleanup code when something closes (like sockets, streams, or file descriptors).

Example :

stream.on("close", () => {
  console.log("Stream closed. Cleanup runs in Close Callbacks phase.");
});

Thread Pool (For Blocking Operations)

For blocking operations, like filesystem tasks or synchronous database queries, the event loop sends these tasks to a thread pool. The thread pool, by default, has 4 threads, but we can increase the number of threads as needed (up to 128).

The thread pool works as follows:

1. When a blocking task arrives, it is sent to the thread pool.

2. The thread pool waits for the main thread (call stack) to be free.

3. Once the thread pool gets an available thread, it processes the task.

4. After the task is complete, it sends the result back to the main thread via the event loop.

Worker Threads in Node.js

In cases where a task is CPU-heavy or takes a long time, we use worker threads. Worker threads are not part of the main thread or the thread pool, but they help offload heavy tasks to run in parallel. Each worker thread runs in its own separate instance of the Libuv library and can be used to perform tasks in the background.

Example of Worker Threads:

const { Worker } = require('worker_threads');

const worker = new Worker('./worker.js');

worker.on('message', (message) => {
  console.log('Message from worker:', message);
});

worker.postMessage('Start processing');

This allows Node.js to handle multiple tasks without blocking the main thread.

Clustering in Node.js

Since Node.js is single-threaded, it can only utilize one CPU core by default. However, we can scale Node.js applications by creating multiple server processes (workers) using the cluster module. Each worker runs on a different CPU core, making the application multi-core and improving performance under heavy loads.

Here’s how it works:

Main Thread (Master): The main process creates child processes (workers) for each CPU core.
Workers: Each worker is a separate instance of the server and handles requests independently, with its own event loop and memory.

Why Use Clustering in Node.js?

Let's say you have a streaming backend application that handles billions of requests. If you only have one Node.js server (process), the server could become overwhelmed, leading to performance issues or even crashes.

By using the cluster module, you can create multiple Node.js servers that run on separate CPU cores. Each server handles a portion of the load, improving performance and scalability.

Node.js vs. Other Platforms (IIS / Kestrel and Java)

In Node.js, the cluster module makes it easy to create replicas of the server. However, in .NET (using IIS / Kestrel) or Java (using multiple JVMs), the replication process is not built-in and must be configured manually using load balancers, reverse proxies, or containerization.

Process and thread

Process
A process is an independent unit of execution that has its own memory space.

Each process runs in its own isolated environment and has its own set of resources (memory, CPU time, etc.).

In Node.js, the main execution environment is a single process (the main process), which is responsible for running the event loop, handling incoming requests, and managing resources.

Thread
A thread is the smallest unit of a CPU's execution. It is a sequence of instructions that can be scheduled and executed by the operating system.

Threads share the same memory space within a process, meaning they can communicate with each other more easily, but they must be synchronized to avoid issues like race conditions.

In Node.js, the event loop and JavaScript code run in a single thread (main thread), but Node.js also uses threads internally for I/O operations via the libuv library (which manages asynchronous operations).

Synchronous vs. Asynchronous in Node.js

1. Synchronous

In synchronous code:

Operations run one after another.
Each task blocks the execution of the next one until it completes.

Example:

console.log("Start");

const result = doHeavyCalculation(); // Blocks until complete
console.log("Result:", result);

console.log("End");

🔴 Problem:

If doHeavyCalculation() takes 5 seconds, nothing else runs during that time.
This is blocking, and in Node.js (single-threaded), it freezes the entire server.

2. Asynchronous

In asynchronous code:

Operations don't block the execution.
Long-running tasks (like I/O, timers) are offloaded, and a callback or Promise is used when the result is ready.

Example:

console.log("Start");

setTimeout(() => {
  console.log("Async task done");
}, 2000);

console.log("End");

Output:

Start
End
Async task done

🟢 Why?

setTimeout is handled by libuv.
Its callback is queued to run later, after 2 seconds.
Meanwhile, other code continues executing — non-blocking behavior.

Worker thread

Node.js is single-threaded by default (main thread = Event Loop). But for CPU-intensive tasks, you can use Worker Threads to run JavaScript in parallel threads, without blocking the main thread.

✅ Use Cases for Worker Threads

CPU-heavy computations (encryption, image processing, large data parsing)
Parallel processing (multi-core utilization)
Avoid blocking the event loop

❌ Don't use for I/O tasks (Node’s async model already handles I/O well)

⚙️ How Do Worker Threads Work?

1. Each Worker has its own thread and V8 engine
→ Each worker runs in its own separate background thread, like a separate copy of Node.js.

2. Workers talk using messages
→ You can send and receive messages between the main thread and worker using:

postMessage() → to send
on('message') → to receive

3. Data is copied when sent
→ When you send data to a worker, it is copied, not shared.
→ But if you want to share memory, use SharedArrayBuffer.

📦 Enabling Worker Threads

Worker threads were added in Node.js v10.5.0 (stable in v12+).

Import them from the worker_threads module.

🧪 Basic Example
🔹 main.js (main thread)

const { Worker } = require('worker_threads');

const worker = new Worker('./worker.js');

worker.on('message', (msg) => {
  console.log('From worker:', msg);
});

worker.postMessage('Start calculation');

🔹 worker.js (worker thread)

const { parentPort } = require('worker_threads');

parentPort.on('message', (msg) => {
  // Simulate heavy computation
  let sum = 0;
  for (let i = 0; i < 1e9; i++) {
    sum += i;
  }

  parentPort.postMessage(`Done. Sum = ${sum}`);
});

🔄 Output:

From worker: Done. Sum = 499999999500000000

Meanwhile, the main thread remains free to handle other requests!

Single threaded and Multithreading

1 .Single-Threaded in Node.js

By default, Node.js runs JavaScript in a single thread — this is called the main thread, where the event loop operates.

🔹 What It Means:

Only one operation executes at a time in the main thread.
No parallel execution of JS code.
Good for I/O-heavy apps (like APIs, web servers).

Example :

console.log("Start");

setTimeout(() => {
  console.log("Async");
}, 1000);

console.log("End");

Even though setTimeout is async, the JS code is executed on a single thread.

2. Multi-threading in Node.js

Node.js can use multiple threads in two ways:

🔸 A. Worker Threads (for JS parallelism)

You create separate threads for CPU-heavy tasks.
Each worker has its own V8 engine and thread.
Communicate via postMessage() and on('message').

🔸 B. Thread Pool (built into libuv)
Node uses 4 background threads by default (can increase).

Used for:
- File system (fs.readFile)
- DNS lookup
- Compression
- Crypto (e.g. bcrypt)
You don’t write these threads manually — Node does it internally.

Stack

Nitin Soni — Fri, 02 May 2025 04:45:27 +0000

A stack is a type of data structure where the last item added is the first one to be removed. This is called Last In, First Out (LIFO).

Think of it like a stack of books — you add books on top, and when you want one, you take the top book off first.

Here, you can:

Put a new book on top of the stack
Remove the top book
And, if you want the book at the bottom, you must first take off all the books above it

This is exactly how the stack data structure works — just like a stack of books!

LIFO Principle of Stack

In programming terms, putting an item on top of the stack is called push and removing an item is called pop.

In the above image, although item 3 was kept last, it was removed first. This is exactly how the LIFO (Last In First Out) Principle works.

We can implement a stack in any programming language like C, C++, Java, Python or C#, but the specification is pretty much the same.

Basic Operations of Stack

There are some basic operations that allow us to perform different actions on a stack.

Push: Add an element to the top of a stack
Pop: Remove an element from the top of a stack
IsEmpty: Check if the stack is empty
IsFull: Check if the stack is full
Peek: Get the value of the top element without removing it

Working of stack data structure

A stack uses a special pointer (we don't need to define it separately in JavaScript) to keep track of the top element.
In JavaScript, we use an array (this.items) to store elements.
When you push an element, it gets added to the end of the array, which acts as the top of the stack.
When you pop an element, the last element (top) is removed.
To see the top element without removing it, we use the peek() method.
We always check if the stack is empty before popping or peeking to avoid errors.

Stack Algorithm :

Algorithm Stack:
  Initialize an empty list called items

  Method push(element):
    Add element to the end of items

  Method pop():
    If items is empty:
      Return "stack is empty"
    Else:
      Remove the last element from items

  Method peek():
    If items is empty:
      Return "stack is empty"
    Else:
      Return the last element in items

  Method size():
    Return the number of elements in items

  Method isEmpty():
    Return true if items has no elements, otherwise false

  Method print():
    Display all elements in items

Create a new Stack called stack

Call stack.push(1)
Call stack.push(3)
Call stack.push(5)
Call stack.push(9)

Call stack.pop()

Display "peek:" and result of stack.peek()
Display "size:" and result of stack.size()

Call stack.print()

Stack Code :

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

  push(element) {
    this.items[this.items.length] = element;
  }

  pop() {
    if (this.isEmpty()) {
      return "stack is empty";
    }
    this.items.length = this.items.length - 1;
  }

  peek() {
    if (this.isEmpty()) return "stack is empty";

    return this.items[this.items.length - 1];
  }

  size() {
    return this.items.length;
  }

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

  print() {
    console.log(this.items);
  }
}

const stack = new Stack();

stack.push(1);
stack.push(3);
stack.push(5);
stack.push(9);

stack.pop();

console.log("peek :", stack.peek());
console.log("size :", stack.size());
stack.print();

Stack Complexity

Time complexity is O(1) for all basic operations — in best, average, and worst cases.
Space complexity is O(n), where n is the number of elements stored in the stack.

Applications of Stack Data Structure

Even though a stack is a simple structure, it’s used in many powerful ways:

1. 🔁 Reversing a word or string

Push all letters into a stack and pop them one by one to get the reverse.

2. 🧮 Expression Evaluation (Compilers)

Used to evaluate expressions like 2 + 4 / 5 * (7 - 9) by converting them to prefix/postfix notation.

3. 🌐 Browser History (Back Button)

Each visited page is stored in a stack. Pressing “Back” pops the current page and goes to the previous one.

4. 🔙 Undo Function in Text Editors

Every action (typing, deleting) is pushed onto a stack. When you hit “Undo”, the last action is popped and reversed.

5. 🔗 Recursive Function Calls

When a function calls itself, each call is stored on the call stack. It pops off each one as it finishes.

6. 🔄 Syntax Parsing

Used in parsers to check if brackets/parentheses are balanced in code like { [ ( ) ] }.

7. 📦 Stack Memory in Programming

Local variables and function calls are stored in the stack section of memory.

8. 🧭 Depth-First Search (DFS) in Graphs

DFS uses a stack to keep track of visited nodes while exploring paths.

9. 🛠 Backtracking Algorithms

Problems like solving a maze or Sudoku use stacks to backtrack to the previous step when stuck.

10. 📱 App Navigation (Mobile Apps)

Mobile apps use stack navigation — screens are pushed and popped like pages in a book.

Radix Sort

Nitin Soni — Thu, 01 May 2025 10:00:08 +0000

Radix Sort is a sorting algorithm that works by sorting numbers based on their digits, starting from the least significant digit (rightmost) to the most significant digit (leftmost).

Let’s say we have an array:
[321, 232, 464, 45, 0, 55, 689]

1. First, we sort the numbers based on the units place (1s digit).

2. Next, we sort based on the tens place (10s digit).

3. Finally, we sort based on the hundreds place (100s digit).

This process continues for each digit position until the entire array is sorted.

Note : Please go through the counting sort before reading this article because counting sort is used as an intermediate sort in radix sort.

Let the initial array be [321, 232, 464, 45, 0, 55, 689]. It is sorted according to radix sort as shown in the figure below.

Working of Radix Sort

Find the largest element in the array, i.e. max. Let X be the number of digits in max. X is calculated because we have to go through all the significant places of all elements.

In this array [321, 232, 464, 45, 0, 55, 689], we have the largest number 689. It has 3 digits. Therefore, the loop should go up to hundreds place (3 times).

2.Now, process each digit position (starting from the least significant place).

Use any stable sorting algorithm (like Counting Sort) to sort the elements based on the digit at the current place value.

For example, to sort based on the unit place digit (place = 1):

First, calculate the count of each digit (0–9).
Then, compute the cumulative count.
Finally, place each element in the output array based on its unit digit using the cumulative count.
This ensures the numbers are stably sorted at this digit position before moving to the next (e.g., tens, hundreds, etc.).

3. Now, sort the elements based on digits at tens place.

4. Finally, sort the elements based on the digits at hundreds place

5. So, Final Sorted array is:

Radix Sort Algorithm

FUNCTION CountingSortForRadix(arr, place):
    n ← length of arr
    output ← array of size n, initialized with 0
    count ← array of size 10, initialized with 0

    // Count occurrences of each digit at current place
    FOR i ← 0 TO n - 1:
        digit ← (arr[i] DIV place) MOD 10
        count[digit] ← count[digit] + 1

    // Compute cumulative count
    FOR i ← 1 TO 9:
        count[i] ← count[i] + count[i - 1]

    // Build the output array
    FOR i ← n - 1 DOWNTO 0:
        digit ← (arr[i] DIV place) MOD 10
        output[count[digit] - 1] ← arr[i]
        count[digit] ← count[digit] - 1

    // Copy output to original array
    FOR i ← 0 TO n - 1:
        arr[i] ← output[i]
END FUNCTION

FUNCTION RadixSort(arr):
    max ← maximum value in arr

    place ← 1
    WHILE (max DIV place) > 0:
        CountingSortForRadix(arr, place)
        place ← place * 10

    RETURN arr
END FUNCTION

Radix Sort Code

function countingSortForRadix(arr, place) {
  const n = arr.length;
  let output = new Array(n).fill(0);
  let count = new Array(10).fill(0);

  // Count occurrences of each digit at "place"
  for (let i = 0; i < n; i++) {
    let digit = Math.floor(arr[i] / place) % 10;
    count[digit]++;
  }

  // Compute cumulative count
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // Build the output array (placing elements in sorted order)
  for (let i = n - 1; i >= 0; i--) {
    let digit = Math.floor(arr[i] / place) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }

  // Copy sorted values back to arr
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

function radixSort(arr) {
  let max = Math.max(...arr);

  // Apply counting sort for each digit place (1s, 10s, 100s, etc.)
  for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
    countingSortForRadix(arr, place);
  }

  return arr;
}

// Example Usage
const inputArray = [321, 232, 464, 45, 0, 55, 689];
console.log("Sorted Array:", radixSort(inputArray));

Radix Sort Complexity

Time Complexity
Best	O(n+k)
Worst	O(n+k)
Average	O(n+k)
Space Complexity	O(max)
Stability	Yes

Since radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.

For the radix sort that uses counting sort as an intermediate stable sort, the time complexity is O(d(n+k)).

Here, d is the number cycle and O(n+k) is the time complexity of counting sort.

Thus, radix sort has linear time complexity which is better than O(nlog n) of comparative sorting algorithms.

If we take very large digit numbers or the number of other bases like 32-bit and 64-bit numbers then it can perform in linear time however the intermediate sort takes large space.

This makes radix sort space inefficient. This is the reason why this sort is not used in software libraries.

Applications of Radix Sort:

✅ 1. Sorting Large Sets of Integers
Radix Sort performs well when sorting large numbers of integers that have a fixed number of digits (e.g. phone numbers, zip codes, IDs). It's faster than comparison-based sorts in these cases.

✅ 2. Sorting Strings or Words (Fixed Length)
Radix Sort can be adapted to sort strings (like words or names) character by character, especially when they are of the same length — such as:

Sorting dictionary entries
Autocomplete suggestions

✅ 3. Used in Data Processing Systems
Systems that handle large volumes of numeric data (like logs, telemetry, sensor data) use radix sort for its linear-time efficiency.

✅ 4. Digital Systems / Embedded Devices
In low-memory or performance-critical environments, Radix Sort is used to sort data like:

Sensor readings
Timestamp logs
Signal values

✅ 5. Databases and Indexing
Some databases or file systems may use radix-like logic to quickly index and sort keys, especially when keys are numeric or fixed-length strings.

✅ 6. Graphics and Image Processing
Used in GPU sorting tasks (like depth sorting or bucket-based rendering) due to its predictable performance and parallelizability.

Counting Sort

Nitin Soni — Tue, 29 Apr 2025 08:52:34 +0000

Counting Sort is a sorting method that works by:

1. Counting how many times each number appears in the list.
2. Using those counts to figure out where each number should go in the final sorted list.

It uses an extra array to keep track of how many times each number appears, and then builds the sorted list based on those counts.

Working of Counting Sort

1. Find out the maximum element (let it be max) from the given array.

2. Create a new array of size max + 1, and set all its elements to 0. This array will be used to store how many times each number appears in the original array.

3. Store the count of each element at their respective index in count array.

For example: if the count of element 3 is 2 then, 2 is stored in the 3rd index of count array. If element "5" is not present in the array, then 0 is stored in 5th index.

4. Change the count array so that each position stores the total of all previous counts. This helps us know the correct position of each number in the sorted array.

5. For each element in the original array, find its value in the count array — this gives its position in the sorted array. Place the element at that position. Then, decrease the count by one. You can see this clearly in the iteration steps below:

6. Final sorted array is :

Counting Sort Algorithm

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Counting Sort Code

function countingSort(arr) {
  let n = arr.length;

  //finding the max element in the array
  let max = 0;
  for (let i = 0; i < n; i++) {
    max = Math.max(arr[i], max);
  }

  //creating a count array of size max+1
  let countArray = new Array(max + 1).fill(0);

  // storing the frequency of each element in the count array
  for (let i = 0; i < n; i++) {
    countArray[arr[i]]++;
  }

  // storing the cumulative frequency of each element in the count array
  for (let i = 1; i < countArray.length; i++) {
    countArray[i] += countArray[i - 1];
  }

  let output = new Array(n);

  // creating outputArray from countArray
  for (let i = 0; i < n; i++) {
    output[countArray[arr[i]] - 1] = arr[i];
    countArray[arr[i]]--;
  }

  return output;
}

const inputArray = [4, 3, 12, 1, 5, 5, 3, 9];
console.log(countingSort(inputArray));

Merge Sort Complexity

Time Complexity
Best	O(n+max)
Worst	O(n+max)
Average	O(n+max)
Space Complexity	O(max)
Stability	Yes

1. Time Complexities

Worst Case Complexity: O(n+max)
Best Case Complexity: O(n+max)
Average Case Complexity: O(n+max)

2. Space Complexity

Space Complexity: O(max) The space complexity of Counting Sort is O(max). Larger the range of elements, larger is the space complexity.

Applications of Counting Sort:

1. Sorting Student Scores / Grades

If you have a list of students' scores (e.g., 0–100), Counting Sort can sort them super quickly.

2. Sorting Ages in a Survey

If you’re dealing with ages (say, 1–120), Counting Sort is very efficient since the range is limited.

3. Sorting Colors (like in graphics or games)

When colors are represented by integer codes (like 0 = red, 1 = green, 2 = blue).

4. Sorting Characters in Strings (if we consider ASCII values)

You can sort characters in a string in O(n) time since there are only 256 possible ASCII values (or 26 for lowercase a–z).

5. In Radix Sort as a sub-routine

Counting Sort is often used within Radix Sort to sort digits efficiently because it preserves the order of equivalent elements (it's stable).

6. Sorting Event Timestamps (if timestamps are integers within a known range)

Can be used for sorting logs, or event times if the time is discretized to seconds, milliseconds, etc.

Binary Search

Nitin Soni — Fri, 11 Apr 2025 11:34:08 +0000

Binary Search is a searching algorithm to find an element in a sorted array by repeatedly dividing the search range in half.
It compares the target with the middle element and narrows the search to either the left or right half accordingly.

Note :

Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.

Working of Binary Search

Binary Search Algorithm can be implemented in two ways which are discussed below.

1. Iterative Method
2. Recursive Method

The recursive method follows the divide and conquer approach.

1. Start with a sorted array.

Let x = 18 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.

3. Find the middle position mid of the array ie. mid = (low + high)/2 and arr[mid] = 12.

4. If x == arr[mid], then return mid. Else, compare the element to be searched with arr[mid].

5. If x > arr[mid], compare x with the middle element of the elements on the right side of arr[mid]. This is done by setting low to low = mid + 1.

6. Else, compare x with the middle element of the elements on the left side of arr[mid]. This is done by setting high to high = mid - 1.

7. Repeat steps 3 to 6 until low meets high.

8. x = 18 is found.

Binary Search Algorithm in iterative method

function binarySearch(array, target):
    set low to 0
    set high to length of array - 1

    while low is less than or equal to high:
        set mid to (low + high) divided by 2 (rounded down)

        if array[mid] equals target:
            return mid (position found)

        else if array[mid] is greater than target:
            set high to mid - 1 (search left half)

        else:
            set low to mid + 1 (search right half)

    return -1 (target not found)

Binary Search Code in iterative method

function binarySearch(arr, k) {
  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (high >= low) {
    mid = Math.floor((high + low) / 2);

    if (arr[mid] === k) return mid;
    else if (arr[mid] > k) high = mid - 1;
    else low = mid + 1;
  }

  return -1;
}

console.log(binarySearch([3, 6, 7, 18, 34], 18));

Binary Search Algorithm in recursive method

function binarySearch(array, target, low = 0, high = array.length - 1):
    if low > high:
        return -1  

    mid = (low + high)

    if array[mid] == target:
        return mid  
    else if array[mid] > target:
        return binarySearch(array, target, low, mid - 1)  
    else:
        return binarySearch(array, target, mid + 1, high)

Binary Search code in recursive method

function binarySearch(arr, k, low = 0, high = arr.length - 1) {
  if (low > high) return -1;

  const mid = Math.floor((low + high) / 2);

  if (arr[mid] === k) return mid;
  else if (arr[mid] > k) return binarySearch(arr, k, low, mid - 1);
  else return binarySearch(arr, k, mid + 1, high);
}

console.log(binarySearch([3, 8, 12, 18, 34], 18));

Time Complexities

Best case complexity: O(1)
Average case complexity: O(log n)
Worst case complexity: O(log n)

Space Complexity
The space complexity of the binary search is O(1).

Real-World Applications of Binary Search

📚 Dictionary Word Search
Just like a dictionary is sorted alphabetically, binary search helps you jump to the middle, decide which half to search, and quickly find a word.

🔍 Auto-complete and Search Suggestions
When you type in Google or any app, it uses binary search on sorted suggestion lists to quickly match what you're typing.

📈 Stock Market Apps
Binary search is used to find the price of a stock at a specific timestamp in historical data (which is sorted by time).

🎮 Game Leaderboards
In online games, scores are often sorted. Binary search helps find a player's rank or check if a score exists quickly.

📅 Calendar Apps (Event Lookup)
When looking for events on a specific date from a large sorted list, binary search helps find it fast.

🛒 E-commerce Filters
When filtering products by price (e.g., show items between ₹500–₹1000), binary search helps quickly find the first and last product in that price range.

🚀 GPS/Navigation Systems
To find locations or routes from large, sorted datasets like maps or coordinates, binary search helps improve lookup speed.

💾 File Systems
Operating systems use binary search to find files in a sorted directory structure.

Linear Search

Nitin Soni — Thu, 10 Apr 2025 17:16:33 +0000

Linear search is the simplest searching algorithm. It works by checking each element in the list one by one, starting from the beginning, until it finds the item you're looking for.

Working of Linear Search

1. Suppose we need to find element k = 6 listed below.

2. Start from the first element, compare k with each element x.

3. If x == k, return the index.

4. Else, return not found.

Linear Search Algorithm

LinearSearch(array, key)
  for each item in the array
    if item == value
      return its index

Linear Search Code

function linearSearch(arr, key){
  for (let i = 0; i < arr.length; i++)  if (arr[i] === key) return i

  return "not found";
};

console.log(linearSearch([1, 2, 4, 5], 4));

Linear Search Complexities

Time Complexity
Best	O(1)
Worst	O(n)
Average	O(n)
Space Complexity	O(1)
Stability	N/A

1. Time Complexities

Best Case: O(1)
When the target element is the first item in the list, it's found immediately.
Worst Case: O(n)
When the target is the last element or not in the list at all. We have to check every item.
Average Case: O(n)
On average, the target is somewhere in the middle of the list, so about half the elements are checked.

2. Space Complexity

Space Complexity: O(1) Linear search uses no extra space, it just checks elements one by one.

Applications of Linear Search

1. Unsorted Data

Linear search works well on unsorted or unstructured data where sorting is not possible or needed.

2. Small Data Sets

Ideal for small lists where performance isn’t a concern.

3. Searching in User Input

Used in basic input validation where the system checks for a value in a list of allowed values.

4. Search in Linked Lists

Since linked lists don’t allow direct access by index, linear search is a good fit.

5. Browser History or Chat Search

Quickly check if a particular URL or message exists.

6. Finding Duplicate Entries

Check through each element to find any repeated items.

7. Educational Purpose

Great for teaching basic search concepts before moving to more complex algorithms like binary search.

Quick Sort

Nitin Soni — Thu, 10 Apr 2025 16:02:32 +0000

Quicksort is a sorting algorithm that uses the divide and conquer method.

1. First, a pivot element is chosen from the array.

2. The array is then divided into two parts:

Elements less than the pivot go to the left.
Elements greater than the pivot go to the right.

3. This process is repeated for the left and right parts until each
subarray has only one element.

4. At that point, the elements are already sorted, and the final sorted array is formed by combining all the parts.

Working of Quicksort Algorithm

1. Choose the Pivot Element
In Quicksort, the pivot can be chosen in different ways. In our case, we will always pick the last element of the array as the pivot.

2. Split into Left and Right Arrays

Create a left array with elements less than pivot.
Create a right array with elements more than pivot.

3. Recursive Calls on Subarrays
As we know, JavaScript is synchronous. So, we first call quickSort() recursively on the left array. But as you can see above, the left array has only one element, so it returns immediately.

Next, we call quickSort() on the right array and step 1 and 2 will repeat during this process.

4. Again, we recursively call on right array

5. Finally, we combine the returned value.
You can understand how the returned values are combined with the help of the visual image below.

Quick Sort Algorithm

FUNCTION quickSort(arr):
    IF length of arr <= 1:
        RETURN arr

    SET pivot TO last element of arr
    INITIALIZE left as empty list
    INITIALIZE right as empty list

    FOR each element in arr EXCEPT the last one:
        IF element < pivot:
            ADD element to left
        ELSE:
            ADD element to right

    RETURN quickSort(left) + [pivot] + quickSort(right)

Quick Sort Code

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  let pivot = arr[arr.length - 1];
  let left = [];
  let right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) left[left.length] = arr[i];
    else right[right.length] = arr[i];
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([5, -11, 9, 2, 1]));

Quick Sort Complexity

Time Complexity
Best	O(n*log n)
Worst	O(n²)
Average	O(n*log n)
Space Complexity	O(log n)
Stability	No

1. Time Complexities

Worst Case Complexity: O(n²) If the pivot is the smallest or largest number, it goes to the end of the sorted array.

One side becomes empty, and the other side has almost all the elements. So, Quicksort keeps working on the bigger side again and again.

It works much better when the pivot is somewhere in the middle, not at the ends.

Best Case Complexity: O(n log n)
It occurs when the pivot element is always the middle element or near to the middle element.
Average Case Complexity: O(n log n)
It occurs when the above conditions do not occur.

2. Space Complexity

Space Complexity: O(n) The space complexity for quicksort is O(log n).

Applications of Quicksort

1. General Purpose Sorting

Used in libraries and frameworks for sorting numbers, strings, and other data types.
Example: JavaScript's Array.sort() uses a variation of Quicksort under the hood in some engines.

2. Large Datasets

Performs well for large datasets that fit in memory.
Searching Algorithms
Prepares data for binary search by sorting the array first.

3. Data Processing

Useful in data analysis pipelines to sort values quickly.

4. Distributed Systems

Used in parallel versions like parallel quicksort for dividing and sorting data across nodes.

5. Embedded Systems

Efficient for systems with limited memory due to its in-place sorting.

6. Databases

Helps optimize query performance by sorting records for indexing and searching.

Merge Sort

Nitin Soni — Thu, 10 Apr 2025 06:32:53 +0000

Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm.

In this approach, the problem is broken down into smaller sub-problems, each of which is solved separately. The solutions to these sub-problems are then combined to form the final solution.

Working of Merge Sort

Suppose we need to sort the following array.

1. Find the Midpoint

Divide the array into two halves by calculating the middle index.

2. Split into Left and Right Arrays

Create a left array with elements before the mid.
Create a right array with elements from mid to the end.

3. As we know javascript is synchronous so, recursively call mergeSort() on left Array
This process is for first left array which we inserted initially and further process for first right array can see in step 7. so, Keep dividing the left array until each sub-array contains only one element. Steps 1 and 2 will repeat during this process.

4. Recursively Call mergeSort() on right Array
Repeat the same process for the right array — divide and reduce to single elements. Steps 1 and 2 will repeat during this process.

5. Merge and sort left and right array by calling merge() function
When both left and right return single-element arrays, the merge() function is called to combine and sort them.

6. Repeat Merging Up the Stack
The merge() function continues to be called step-by-step as the recursion unwinds, combining and sorting the small arrays until the full array is rebuilt and sorted.
In below image we taken the left array of step 3 and right array of step 5.

7. Now we recursively call mergeSort() function for the first right array which we inserted in step 1 for that we again follow the same process of step 1 and step 2

8. Again we recursively call mergeSort() function.

9. Merge left and right Array.

10. Again Merge and sort left and right array.

11. finally we merge and sort left and right array of step 6 and step 10.

Merge Sort Algorithm

function MERGE_SORT(array)
    if length of array ≤ 1
        return array

    mid ← floor(length of array / 2)

    left ← empty array
    right ← empty array

    for i from 0 to mid - 1
        add array[i] to left

    for i from mid to length of array - 1
        add array[i] to right

    left ← MERGE_SORT(left)
    right ← MERGE_SORT(right)

    return MERGE(left, right)


function MERGE(left, right)
    result ← empty array
    i ← 0
    j ← 0

    while i < length of left AND j < length of right
        if left[i] < right[j]
            append left[i] to result
            i ← i + 1
        else
            append right[j] to result
            j ← j + 1

    while i < length of left
        append left[i] to result
        i ← i + 1

    while j < length of right
        append right[j] to result
        j ← j + 1

    return result

Merge Sort Code

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);
  let left = [];
  let right = [];

  for (let i = 0; i < mid; i++) left[left.length] = arr[i];

  for (let i = mid; i < arr.length; i++) right[right.length] = arr[i];

  left = mergeSort(left);
  right = mergeSort(right);

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result[result.length] = left[i];
      i++;
    } else {
      result[result.length] = right[j];
      j++;
    }
  }

  while (i < left.length){
    result[result.length] = left[i];
    i++;
  }

  while (j < right.length){
    result[result.length] = right[j];
    j++;
  }

  return result;
}

console.log(mergeSort([12, 3, 10, 25, 6, 1]));

Merge Sort Complexity

Time Complexity
Best	O(n*log n)
Worst	O(n*log n)
Average	O(n*log n)
Space Complexity	O(n)
Stability	Yes

1. Time Complexities

Worst Case Complexity: O(n log n)
Merge Sort always divides the array into two halves and takes linear time to merge two halves. The division happens log n times and merging takes O(n) time, resulting in O(n log n) overall.
Best Case Complexity: O(n log n)
Even when the array is already sorted, Merge Sort still divides and merges the array the same way, so the best case is also O(n log n).
Average Case Complexity: O(n log n)
On average, Merge Sort performs consistently in O(n log n) time due to the divide-and-conquer approach.

2. Space Complexity

Space Complexity: O(n) Merge Sort requires additional space proportional to the size of the array for merging the divided arrays. So, the auxiliary space used is O(n).

Real-World Application of Merge Sort

1. E-Commerce Product Sorting

💡 Use Case: Sorting products by price, rating, or discount.

Why Merge Sort?

It’s stable and works well even with large datasets. Imagine you fetch 1000+ products and need to sort them by price while maintaining their display order (e.g., sponsored first). Merge Sort keeps that order intact.

// Example: Sorting products by price
const products = [
  { name: "Shoes", price: 50 },
  { name: "T-Shirt", price: 20 },
  { name: "Jacket", price: 120 },
];

const sortedProducts = mergeSort(products, (a, b) => a.price - b.price);

2. Leaderboard Ranking System

💡 Use Case: Sorting players by scores or time taken.

Why Merge Sort?

In gaming or quiz apps, merge sort can be used to build real-time leaderboards while keeping the results stable and performant.

3. Log Analysis Tool

💡 Use Case: Sorting logs by timestamps.

Why Merge Sort?

If you're building a monitoring or analytics dashboard in Node.js or frontend, and you need to merge and sort logs from multiple sources by time.

4. Contact or User List Sorting

💡 Use Case: Sorting contacts alphabetically or by date added.

Why Merge Sort?

Especially useful in messaging or CRM apps where a consistent user order is crucial.

5. File Chunk Merging (Upload Systems)

💡 Use Case: When implementing large file uploads in chunks (e.g., S3 or Google Cloud), Merge Sort can be used to order file pieces before reconstruction.