Top 26 Data Structures in Modern Programming

Data structures are foundational concepts in computer science that enable the efficient organization and manipulation of data. Understanding these structures is crucial for solving complex programming problems and optimizing code performance. Here, we delve into the top 20 data structures that are essential for modern programming, covering a range from basic to more advanced constructs.

Name: Array

Brief Description: An array is a collection of items stored at contiguous memory locations. It is the simplest and most widely used data structure for storing collections of data.

Suitability:

Arrays are most suitable when you need to store a collection of elements of the same type, and these elements are logically related. This allows you to manage these elements using a single identifier, simplifying tasks such as iteration, search, sort, and filter operations. Arrays are particularly useful when:

The number of elements is known or can be estimated with a fair degree of certainty.
You need to access elements by their index, taking advantage of the array's ability to access elements in constant time.
The elements are to be processed in a sequential manner, such as in loops.

Example of an Array


let fruits = ["Apple", "Banana", "Cherry"];

Name: Linked List

Brief Description: A linked list is a linear collection of data elements where each element points to the next. It allows for efficient insertion and removal of elements.

Suitability:

Linked lists are particularly suitable in scenarios where:

Dynamic data allocation is needed: Unlike arrays, linked lists can easily grow or shrink in size, making them ideal for situations where the number of elements can change dynamically over time.
Frequent insertions and deletions are performed: Linked lists can add or remove elements at any point in the list without the need to reorganize the entire data structure. This is especially efficient if you're adding or removing elements at the beginning or in the middle of the list.
Memory efficiency is a concern in densely populated lists: Since linked lists allocate memory for each element separately, they can be more memory-efficient for large datasets with frequent additions and deletions, as they don’t need to pre-allocate memory.

Web Application: Undo Functionality in a Text Editor

In a web application that features a text editor, a linked list could be used to implement undo functionality. Each node in the linked list could represent a state of the document at a given time. When a user makes a change, a new node is added to the list that represents the new state of the document. The user can then navigate back through the states (nodes) to undo changes.

Computer Program: Memory Management System

In a computer program designed for managing memory allocation, a linked list can be used to keep track of free memory blocks. When a program allocates or frees memory, the linked list is updated accordingly to add or remove memory blocks, allowing for efficient memory utilization and reducing fragmentation.

Cell Phone Application: Photo Browser

In a cell phone application for browsing photos, a linked list can manage the sequence of photos for efficient navigation. As the user swipes left or right, the application can quickly move to the previous or next item in the list without needing to load the entire photo library into memory.

Example of a Linked Lists


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

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

    // Insert first node
    insertFirst(data) {
        this.head = new Node(data, this.head);
    }

    // Insert last node
    insertLast(data) {
        let node = new Node(data);
        if (!this.head) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
        current.next = node;
        }
    }

    // Print list data
    printListData() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Example usage
const ll = new LinkedList();
ll.insertFirst(100);
ll.insertFirst(200);
ll.insertLast(300);

ll.printListData();

Name: Stack

Brief Description: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It is used for managing function invocations, undo mechanisms in applications, and more.

Suitability:

Using a stack is most suitable in scenarios where you need to manage data in a Last-In-First-Out (LIFO) manner.

Managing function calls (call stack) in programming languages, where the last function called needs to be the first to complete and return.
Undo mechanisms in software applications, where the most recent action should be the first to be reversed.
Navigating through browser history or page views in a web application, where the most recent page viewed is the first one to go back to.
Parsing and evaluating expressions in programming languages and calculators, especially for infix and postfix notation.
Depth-First Search (DFS) in tree or graph data structures.

Cell Phone Application: Navigation History

In a mobile application with multiple screens, such as a shopping app, a stack can manage the navigation history. Each time a user navigates to a new screen, the screen's identifier or instance can be pushed onto a stack. When the user wants to go back, the application pops the top of the stack to determine the previous screen.

Computer Program: Expression Evaluation

In a computer program, such as a calculator application or a compiler, stacks can be used to evaluate expressions, especially infix and postfix expressions. Operators and operands are pushed onto different stacks, and the expression is evaluated by popping these elements in the correct order.

Example of a Stack


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

    // Add an element to the top of the stack
    push(element) {
        this.items.push(element);
    }

    // Remove the top element from the stack and return it
    pop() {
        if (this.items.length === 0) {
            return "Underflow"; // Stack is empty
        }
    return this.items.pop();
    }

    // View the top element of the stack
    peek() {
    return this.items[this.items.length - 1];
    }

    // Check if the stack is empty
    isEmpty() {
        return this.items.length === 0;
    }

    // View all elements in the stack
    printStack() {
    let str = '';
    for (let i = 0; i < this.items.length; i++) {
        str += this.items[i] + " ";
    }
    return str.trim();
    }
}

// Example usage:
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.printStack()); // 10 20 30
console.log(stack.peek()); // 30
console.log(stack.pop()); // 30
console.log(stack.printStack()); // 10 20

This Stack class starts with an empty array items that will store the elements of the stack. The class includes methods to add (push) and remove (pop) elements from the stack, view the top element without removing it (peek), check if the stack is empty (isEmpty), and print all elements in the stack (printStack). The example usage demonstrates creating a stack, adding elements to it, checking the top element, removing the top element, and then printing the remaining stack.

Name: Queue

Brief Description: A queue is a linear structure that follows the First In, First Out (FIFO) principle. It is essential for managing tasks in scheduling algorithms, buffering, and handling asynchronous tasks.

Suitability:

Using a queue is most suitable in scenarios where you need to manage data in a First-In-First-Out (FIFO) manner. This data structure is particularly useful for:

Managing tasks or operations that need to be executed in the order they were received, such as print jobs in a printer queue.
Handling asynchronous data, like processing user input events in GUI applications.
Implementing data buffers, where data is processed in the order it arrives, such as in streaming applications or network packet processing.
Managing levels in breadth-first search (BFS) algorithms in tree or graph data structures.
Coordinating resources in operating systems, like scheduling processes or managing threads.

Web Application: Job Queue for Background Tasks

In a web application, a queue can manage background tasks such as sending emails, generating reports, or performing batch updates. Tasks submitted by users are enqueued, and a background process systematically dequeues and executes them in order. This ensures that tasks are completed in the same order they were requested.

Cell Phone Application: Notifications Queue

In a cell phone application, such as a social media app, a queue can manage incoming notifications. As notifications arrive, they are added to the queue. The app then processes these notifications in the order they were received, ensuring users receive updates timely and sequentially.

Example of a Queue


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

    // Enqueue: Add an element to the back of the queue
    enqueue(element) {
        this.items.push(element);
    }

    // Dequeue: Remove the element from the front of the queue and return it
    dequeue() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items.shift();
    }

    // Peek: View the element at the front of the queue without removing it
    peek() {
        if (this.isEmpty()) {
            return 'Queue is empty';
        }
        return this.items[0];
    }

    // Check if the queue is empty
    isEmpty() {
        return this.items.length === 0;
    }

    // Get the number of elements in the queue
    size() {
        return this.items.length;
    }

    // Clear the queue
    clear() {
        this.items = [];
    }
}

// Example usage
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue(5);
queue.enqueue(8);
console.log(queue.peek()); // 5
console.log(queue.dequeue()); // 5
console.log(queue.dequeue()); // 8
console.log(queue.isEmpty()); // true

In this Queue class implementation:

The enqueue(element) method adds an element to the back of the queue.
The dequeue() method removes and returns the front element of the queue. If the queue is empty, it returns a message indicating so.
The peek() method returns the front element of the queue without removing it, providing a way to see what's next to be removed. If the queue is empty, it returns a message indicating so.
The isEmpty() method checks if the queue is empty and returns true if it is and false otherwise.
The size() method returns the number of elements in the queue.
The clear() method removes all elements from the queue.

This example provides a straightforward implementation of a queue using JavaScript, illustrating the FIFO behavior that queues are known for.

Name: Hash Table

Brief Description: A hash table stores key-value pairs and uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Suitability:

Using a hash table (or hash map) is most suitable in scenarios where you need fast data retrieval, insertion, and deletion based on unique keys. This data structure is particularly useful for:

Implementing associative arrays or mappings of unique keys to values, allowing for quick lookups.
Storing and accessing data where the order of elements is not important, but fast access to individual elements is required.
Eliminating duplicate values or checking for the presence of items efficiently.
Implementing caches where quick retrieval of data based on specific keys is necessary.
Supporting efficient data indexing and retrieval operations in database systems.

Web Application: User Sessions Management

In a web application, a hash table can be used to manage user sessions. Each session can be uniquely identified by a session ID (the key), with the session data (such as user information, preferences, and authentication tokens) stored as the value. This allows for efficient retrieval and updating of session information based on the session ID.

Computer Program: Inventory System

In a computer program designed for managing inventory, such as a retail stock system, a hash table can be used to store and manage inventory items. Each item can be uniquely identified by a product ID or SKU, with the item's details (such as name, quantity, and price) stored as the value. This setup allows for efficient lookups, additions, and updates based on the product ID.

Cell Phone Application: Caching Data Locally

In a mobile application, such as a news aggregator app, a hash table can be used to cache articles locally on the device. Each article can be keyed by its unique identifier (e.g., URL or ID from the database), allowing for quick retrieval of the article data to display to the user, even when offline.

Example of a Hash Table


class HashTable {
  constructor(size = 20) {
    this.buckets = new Array(size);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (let char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % this.size;
  }

  set(key, value) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = this.hash(key);
    const items = this.buckets[index];
    if (items) {
      for (let [k, v] of items) {
        if (k === key) {
          return v;
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const index = this.hash(key);
    const items = this.buckets[index];
    if (items) {
      for (let i = 0; i < items.length; i++) {
        if (items[i][0] === key) {
          items.splice(i, 1);
          return true;
        }
      }
    }
    return false;
  }
}

// Example usage:
const hashtable = new HashTable();
hashtable.set('name', 'John Doe');
hashtable.set('age', 30);
hashtable.set('occupation', 'Software Developer');

console.log(hashtable.get('name')); // John Doe
console.log(hashtable.get('age')); // 30

hashtable.remove('occupation');
console.log(hashtable.get('occupation')); // undefined

This HashTable class includes:

A constructor that initializes an array (buckets) with a specified size to store the key-value pairs.
A hash method that calculates a simple hash based on the sum of the character codes of the key, ensuring the hash is within the bounds of the buckets array.
A set method to add or update key-value pairs in the hashtable. It handles collisions by using separate chaining, where each bucket at a given index can store multiple entries if they hash to the same index.
A get method to retrieve the value associated with a given key, returning undefined if the key is not found.
A remove method to delete a key-value pair from the hashtable, returning true if successful or false if the key is not found.

This implementation is a basic example of how hashtables work in JavaScript, demonstrating hashing, collision resolution, and the CRUD operations of a hashtable.

Name: Binary Tree

Brief Description: A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. It's used in sorting and searching algorithms, among other applications.

Suitability:

Using a binary tree is most suitable in scenarios where you need hierarchical data representation and operations that benefit from structured traversal or sorted data management. Binary trees are particularly useful for:

Implementing efficient search algorithms, as binary search trees (BST) can offer (log)O(logn) lookup, insert, and delete operations in balanced cases.
Storing data in a sorted manner, which simplifies tasks like printing all elements in order, finding the next higher or lower element, etc.
Building the backbone for more complex data structures like heaps, which are used in priority queues, and binary search trees used in map and set implementations in many libraries.
Facilitating fast access to elements that are frequently accessed together by structuring the tree to minimize path lengths between these elements.

Web Application: Product Catalogue

In a web application for e-commerce, a binary search tree could manage a product catalogue where products are sorted by a unique identifier, such as a product ID or SKU. This allows for efficient searching, adding, and deleting of products. For example, when a user searches for a product by its ID, the application can quickly determine whether the product exists in the catalogue and retrieve its details.

Cell Phone Application: Contact Management

In a cell phone contact management application, a binary tree could organize contacts where each node represents a contact. The tree could be ordered by contact name or some other attribute, enabling efficient contact search, addition, and deletion. It simplifies operations like displaying contacts in alphabetical order or finding a contact by name.

Computer Program: Expression Parsing

In a computer program that performs mathematical calculations, such as a calculator app, a binary tree can represent and evaluate mathematical expressions. Each node represents an operand or operator, allowing the program to recursively traverse the tree and evaluate the expression. This is particularly useful for handling expressions that include nested operations and parentheses.

Example of a Binary Tree


class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

    insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    // In-order traversal
    inOrder(node, fn = console.log) {
        if (node !== null) {
            this.inOrder(node.left, fn);
            fn(node.value);
            this.inOrder(node.right, fn);
        }
    }

    // Pre-order traversal
    preOrder(node, fn = console.log) {
        if (node !== null) {
            fn(node.value);
            this.preOrder(node.left, fn);
            this.preOrder(node.right, fn);
        }
    }

    // Post-order traversal
    postOrder(node, fn = console.log) {
        if (node !== null) {
            this.postOrder(node.left, fn);
            this.postOrder(node.right, fn);
            fn(node.value);
        }
    }
}

// Example usage
const binaryTree = new BinaryTree();
binaryTree.insert(5);
binaryTree.insert(3);
binaryTree.insert(7);
binaryTree.insert(2);
binaryTree.insert(4);
binaryTree.insert(6);
binaryTree.insert(8);

console.log("In-order traversal:");
binaryTree.inOrder(binaryTree.root); // 2, 3, 4, 5, 6, 7, 8

console.log("Pre-order traversal:");
binaryTree.preOrder(binaryTree.root); // 5, 3, 2, 4, 7, 6, 8

console.log("Post-order traversal:");
binaryTree.postOrder(binaryTree.root); // 2, 4, 3, 6, 8, 7, 5

This HashTable class includes:

The TreeNode class defines the structure of each node in the tree.
The BinaryTree class represents the tree itself, with methods to insert nodes and traverse the tree.
The insert method places a new value in the tree. Although this implementation uses logic typically found in binary search trees for simplicity, a generic binary tree might not follow this value-based insertion logic.
The inOrder, preOrder, and postOrder methods are traversal functions that visit each node in a specific order:
- In-order traversal visits the left branch, then the current node, and finally the right branch.
- Pre-order traversal visits the current node before its child nodes.
- Post-order traversal visits the child nodes before the current node.
Each traversal method accepts a callback function (fn) to apply to each node's value. By default, this is set to console.log to print the values.

This implementation is a basic example of how hashtables work in JavaScript, demonstrating hashing, collision resolution, and the CRUD operations of a hashtable.

Name: Binary Search Tree

Brief Description: A binary search tree (BST) is a type of binary tree where the left child contains nodes with values less than the parent node, and the right child contains nodes with values greater than the parent node.

Example of a Binary Search Tree


class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // Method to insert a new value into the BST
    insert(value) {
        const newNode = new TreeNode(value);

        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    // Helper method to find the correct position for a new node in the tree
    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    // Method to search for a value in the BST
    search(node, value) {
        if (node === null) {
            return false;
        } else if (value < node.value) {
            return this.search(node.left, value);
        } else if (value > node.value) {
            return this.search(node.right, value);
        } else {
            return true; // The value is found
        }
    }
}

// Example usage
const bst = new BinarySearchTree();
bst.insert(15);
bst.insert(25);
bst.insert(10);
bst.insert(7);
bst.insert(22);
bst.insert(17);
bst.insert(13);
bst.insert(5);
bst.insert(9);
bst.insert(27);

let root = bst.root;
console.log('BST Root:', root);

// Search for a value in the BST
console.log('Search 22:', bst.search(root, 22)); // true
console.log('Search 40:', bst.search(root, 40)); // false

This example includes:

A TreeNode class that represents each node in the tree.
A BinarySearchTree class that represents the BST itself, with methods to insert a new value and search for a value within the tree.
The insert method places a new value in the correct location in the tree.
The insertNode helper method recursively finds the correct position for the new node.
The search method looks for a specific value, starting from the root and traversing the tree based on BST properties.

This implementation is a basic introduction to binary search trees in JavaScript, showcasing how to insert nodes and search for values within the tree.

Name: Graph

Brief Description: A graph is a set of nodes connected by edges. It is a fundamental structure used to model relationships in problems involving networks, such as social networks or transportation systems.

Implementing a graph in JavaScript can be done using various data structures, but one common approach is to use an adjacency list. An adjacency list can be represented using a map or object where each key represents a vertex and its value is a list (or array) of adjacent vertices. This representation is efficient in terms of space, especially for sparse graphs, and allows for quick addition of vertices and edges.

Below is an example of how to implement a simple, undirected graph in JavaScript using an adjacency list:


class Graph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    addEdge(vertex1, vertex2) {
        if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
            this.adjacencyList[vertex1].push(vertex2);
            this.adjacencyList[vertex2].push(vertex1);
        }
    }

    removeEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
    }

    removeVertex(vertex) {
        while (this.adjacencyList[vertex].length) {
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex];
    }

    display() {
        for (let vertex in this.adjacencyList) {
            console.log(vertex + " -> " + this.adjacencyList[vertex].join(', '));
        }
    }
}

// Example usage:
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");
console.log("Initial graph:");
graph.display();

graph.removeEdge("B", "C");
console.log("Graph after removing edge between B and C:");
graph.display();

graph.removeVertex("C");
console.log("Graph after removing vertex C:");
graph.display();

This Graph class provides methods to:

Add a vertex to the graph.
Add an edge between two vertices.
Remove an edge between two vertices.
Remove a vertex and all its connected edges from the graph.
Display the graph by printing each vertex and its adjacent vertices.

This implementation showcases a basic undirected graph where edges are bidirectional. For a directed graph, you would modify the addEdge and removeEdge methods to only add the edge to the starting vertex's list and remove it accordingly, representing a one-way connection.

Name: Trie

Brief Description: A trie, or prefix tree, is a kind of search tree used to store a dynamic set or associative array where the keys are usually strings. It is best for solving problems related to word validations or auto-suggestions.

A Trie, also known as a prefix tree, is a specialized tree used to store associative data structures. A trie is a highly efficient data structure for searching, inserting, and deleting strings in a dataset of words. Each node of the trie represents a single character of a word, and the path from the root to a particular node represents a prefix of some word in the dataset.

Example on Tries


class TrieNode {
    constructor() {
        this.children = {}; // holds the child nodes
        this.isEndOfWord = false; // indicates the end of the word
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Inserts a word into the trie
    insert(word) {
        let current = this.root;
        for (const char of word) {
            if (!current.children[char]) {
                current.children[char] = new TrieNode();
            }
            current = current.children[char];
        }
        current.isEndOfWord = true;
    }

    // Searches for the word in the trie and returns true if the word exists
    search(word) {
        let current = this.root;
        for (const char of word) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return current.isEndOfWord;
    }

    // Returns true if there is any word in the trie that starts with the given prefix
    startsWith(prefix) {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children[char]) {
                return false;
            }
            current = current.children[char];
        }
        return true;
    }
}

// Example usage:
const trie = new Trie();
trie.insert("hello");
trie.insert("helium");

console.log(trie.search("hello")); // true
console.log(trie.search("helium")); // true
console.log(trie.search("hell")); // false
console.log(trie.startsWith("hell")); // true
console.log(trie.startsWith("he")); // true
console.log(trie.startsWith("hi")); // false

This example includes two main classes:

TrieNode, which represents each node in the trie. Each node contains a children object (to store references to its child nodes) and a boolean isEndOfWord that marks the end of a word.
Trie, which represents the trie itself. It includes methods to insert a word, search for a word, and check if any word in the trie starts with a given prefix.

The insert method iterates through each character of the word, adding nodes for each character to the trie if they don't already exist. The search method checks if a word is in the trie by following the nodes corresponding to each character of the word.

The startsWith method works similarly to search but only checks if a prefix exists in the trie, not necessarily as a complete word.

Name: Heap

Brief Description: A heap is a specialized tree-based data structure that satisfies the heap property: if A is a parent node of B, then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

A heap is a specialized tree-based data structure that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

Below is an example of how to implement a min heap in JavaScript. This min heap allows for inserting elements, extracting the minimum element, and peeking at the minimum element without removing it.


class MinHeap {
    constructor() {
        this.heap = [null]; // Initialize with null at index 0 for easier math
    }

    insert(number) {
        this.heap.push(number);
        if (this.heap.length > 2) {
            let idx = this.heap.length - 1;
            while (this.heap[idx] < this.heap[Math.floor(idx / 2)]) {
                if (idx >= 1) {
                    // Swap
                    [this.heap[Math.floor(idx / 2)], this.heap[idx]] = [this.heap[idx], this.heap[Math.floor(idx / 2)]];
                    if (Math.floor(idx / 2) > 1) {
                        idx = Math.floor(idx / 2);
                    } else {
                        break;
                    }
                }
            }
        }
    }

    remove() {
        let smallest = this.heap[1];
        if (this.heap.length > 2) {
            this.heap[1] = this.heap[this.heap.length - 1];
            this.heap.splice(this.heap.length - 1);
            if (this.heap.length === 3) {
                if (this.heap[1] > this.heap[2]) {
                    [this.heap[1], this.heap[2]] = [this.heap[2], this.heap[1]];
                }
                return smallest;
            }
            let i = 1;
            let left = 2 * i;
            let right = 2 * i + 1;
            while (this.heap[i] >= this.heap[left] || this.heap[i] >= this.heap[right]) {
                if (this.heap[left] < this.heap[right]) {
                    [this.heap[i], this.heap[left]] = [this.heap[left], this.heap[i]];
                    i = 2 * i
                } else {
                    [this.heap[i], this.heap[right]] = [this.heap[right], this.heap[i]];
                    i = 2 * i + 1;
                }
                left = 2 * i;
                right = 2 * i + 1;
                if (this.heap[left] === undefined || this.heap[right] === undefined) {
                    break;
                }
            }
        } else if (this.heap.length === 2) {
            this.heap.splice(1, 1);
        } else {
            return null;
        }
        return smallest;
    }

    peek() {
        return this.heap[1] ? this.heap[1] : null;
    }
}

// Example usage:
const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(4);
minHeap.insert(9);
minHeap.insert(5);
minHeap.insert(2);

console.log("Peek:", minHeap.peek()); // Output: 2
console.log("Remove:", minHeap.remove()); // Output: 2
console.log("New peek:", minHeap.peek()); // Output: 3

In this implementation, the MinHeap class uses an array to store the elements of the heap. The insert method adds a new number to the heap, ensuring the min heap property is maintained. The remove method removes and returns the smallest element from the heap and re-adjusts the heap to maintain the heap property. The peek method allows you to look at the smallest element without removing it.

This example represents a simple min heap where smaller numbers are given priority. If you're implementing a max heap, the conditions in the insert and remove methods would be reversed to ensure the largest element always remains at the root of the heap.

Name: AVL Tree

Brief Description: An AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node differ by no more than one, ensuring O(log n) search, insert, and delete operations.

This balance condition ensures O(log n) time complexity for search, insert, and delete operations. Implementing an AVL tree involves rotations to maintain the balance factor after insertions and deletions.

Below is a basic implementation of an AVL Tree in JavaScript. This example includes the structure for the tree nodes, the AVL tree itself, and methods for inserting nodes and performing rotations to maintain balance.

Example of an AVL Tree


class TreeNode {
  constructor(value) {
    this.value = value;
    this.height = 1; // Height of node for balance factor calculation
    this.left = null;
    this.right = null;
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }

  // Insert a new value into the AVL tree
  insert(value) {
    this.root = this.insertNode(this.root, value);
  }

  insertNode(node, value) {
    // Perform the normal BST insertion
    if (node === null) {
      return new TreeNode(value);
    }
    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.insertNode(node.right, value);
    } else {
      // Duplicate values are not allowed
      return node;
    }

    // Update height of this ancestor node
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    // Get the balance factor
    let balance = this.getBalance(node);

    // If the node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && value < node.left.value) {
      return this.rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && value > node.right.value) {
      return this.leftRotate(node);
    }

    // Left Right Case
    if (balance > 1 && value > node.left.value) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && value < node.right.value) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }

    // Return the (unchanged) node pointer
    return node;
  }

  // Get the height of the node
  getHeight(node) {
    if (node === null) {
      return 0;
    }
    return node.height;
  }

  // Get balance factor of node N
  getBalance(node) {
    if (node === null) {
      return 0;
    }
    return this.getHeight(node.left) - this.getHeight(node.right);
  }

  // Right rotate subtree rooted with y
  rightRotate(y) {
    let x = y.left;
    let T2 = x.right;

    // Perform rotation
    x.right = y;
    y.left = T2;

    // Update heights
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;

    // Return new root
    return x;
  }

  // Left rotate subtree rooted with x
  leftRotate(x) {
    let y = x.right;
    let T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    // Update heights
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;

    // Return new root
    return y;
  }

  // Preorder traversal of the tree
  preOrder(node = this.root) {
    if (node !== null) {
      console.log(node.value);
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }
}

// Example usage:
const avlTree = new AVLTree();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);

console.log("Preorder traversal of the constructed AVL tree is:");
avlTree.preOrder();

This example includes:

A TreeNode class with a value, height, left, and right.
An AVLTree class with methods for insertion (insert and insertNode), rotations (leftRotate and rightRotate), and utilities (getHeight and getBalance).
The insert method handles the insertion of new nodes and ensures the tree remains balanced using rotations.
Rotations are used to maintain the tree's balance after insertions (or deletions, though deletion logic is not included in this snippet). These rotations are critical for maintaining the AVL tree property, where the heights of two child subtrees of any node differ by no more than one. If at any time they differ by more than one, re-balancing is done to restore this property. The re-balancing is done through the following rotations:
Right Rotation (rightRotate): This is done on a node when its left child's height is greater than its right child's height by more than one (Left-Left case), indicating a need to rotate the subtree right to balance it.
Left Rotation (leftRotate): Opposite to the right rotation, this is done when a node's right child's height is greater than its left child's height by more than one (Right-Right case), requiring a left rotation to balance the subtree.
Left Right Rotation: This is a double rotation for the Left-Right case. First, a left rotation is performed on the left child, followed by a right rotation on the node.
Right Left Rotation: This double rotation is for the Right-Left case. It starts with a right rotation on the right child, followed by a left rotation on the node.

These rotations adjust the structure of the subtree to maintain the AVL balance condition after each insertion.

The preOrder method is a simple traversal that visits the root, followed by the left subtree, and then the right subtree. This method is useful for printing the tree's nodes in "preorder" for debugging or observation purposes.

The AVL Tree implementation ensures that the tree remains approximately balanced at all times, guaranteeing that operations like search, insertion, and deletion can be performed in O(log n) time complexity, where n is the number of nodes in the tree.

This implementation provides the core functionality of an AVL tree but could be extended further to include deletion of nodes, which also requires checking and possibly rebalancing the tree to maintain the AVL property.

Name: Red-Black Tree

Brief Description: A red-black tree is a kind of self-balancing binary search tree where each node stores an extra bit representing "color" to ensure the tree remains balanced during insertions and deletions.

A Red-Black Tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black. This tree enforces specific rules that balance the tree, ensuring that the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf, thus maintaining approximately balanced heights across the tree.

The properties that every Red-Black Tree follows are:

Node Color: Each node is either red or black.
Root Property: The root node is always black.
Red Node Property: Red nodes can only have black children (i.e., no two red nodes can be adjacent).
Black Height Property: Every path from a node to its descendant NULL nodes has the same number of black nodes.
Leaf Nodes: All leaf nodes (NIL nodes) are considered black.
These constraints enforce a critical balance across the tree, ensuring that the tree remains approximately balanced with operations such as insertion, deletion, and search that can be performed in O(log n) time complexity.

Below is a simplified JavaScript implementation of a Red-Black Tree focusing primarily on insertion and the colors adjustment. Note that for brevity, the code may omit certain edge cases and deletion handling:


class Node {
  constructor(data, color = 'red') {
    this.data = data;
    this.color = color;
    this.parent = null;
    this.left = null;
    this.right = null;
  }
}

class RedBlackTree {
  constructor() {
    this.TNULL = new Node(null, 'black'); // The NIL node
    this.root = this.TNULL;
  }

  insert(key) {
    let node = new Node(key);
    node.left = this.TNULL;
    node.right = this.TNULL;

    let parent = null;
    let current = this.root;

    while (current !== this.TNULL) {
      parent = current;
      if (node.data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    node.parent = parent;

    if (parent === null) {
      this.root = node;
    } else if (node.data < parent.data) {
      parent.left = node;
    } else {
      parent.right = node;
    }

    if (node.parent === null) {
      node.color = 'black';
      return;
    }

    if (node.parent.parent === null) {
      return;
    }

    this.fixInsert(node);
  }

  fixInsert(node) {
    let uncle;
    while (node.parent.color === 'red') {
      if (node.parent === node.parent.parent.right) {
        uncle = node.parent.parent.left; // uncle
        if (uncle.color === 'red') {
          uncle.color = 'black';
          node.parent.color = 'black';
          node.parent.parent.color = 'red';
          node = node.parent.parent;
        } else {
          if (node === node.parent.left) {
            node = node.parent;
            this.rotateRight(node);
          }
          node.parent.color = 'black';
          node.parent.parent.color = 'red';
          this.rotateLeft(node.parent.parent);
        }
      } else {
        // Mirror case of above
        uncle = node.parent.parent.right;

        if (uncle.color === 'red') {
          uncle.color = 'black';
          node.parent.color = 'black';
          node.parent.parent.color = 'red';
          node = node.parent.parent;
        } else {
          if (node === node.parent.right) {
            node = node.parent;
            this.rotateLeft(node);
          }
          node.parent.color = 'black';
          node.parent.parent.color = 'red';
          this.rotateRight(node.parent.parent);
        }
      }
      if (node === this.root) {
        break;
      }
    }
    this.root.color = 'black';
  }

  rotateLeft(x) {
    let y = x.right;
    x.right = y.left;
    if (y.left !== this.TNULL) {
      y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
  }

  rotateRight(x) {
    let y = x.left;
    x.left = y.right;
    if (y.right !== this.TNULL) {
      y.right.parent = x;
    }
    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.right) {
      x.parent.right = y;
    } else {
      x.parent.left = y;
    }
    y.right = x;
    x.parent = y;
  }

  // Additional utility methods can be implemented here, such as deletion, searching, and traversing the tree.
}

// Example usage of the RedBlackTree class
const rbt = new RedBlackTree();
rbt.insert(7);
rbt.insert(3);
rbt.insert(18);
rbt.insert(10);
rbt.insert(22);
rbt.insert(8);
rbt.insert(11);
rbt.insert(26);

// Method to print the tree in console, for demonstration purposes.
function printTree(node, prefix = '', isLeft = true) {
  if (node !== rbt.TNULL) {
    console.log(prefix + (isLeft ? "├── " : "└── ") + (node.color === 'red' ? 'R' : 'B') + " " + node.data);
    printTree(node.left, prefix + (isLeft ? "│   " : "    "), true);
    printTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
  }
}

console.log("Red-Black Tree structure:");
printTree(rbt.root);

This complete example includes:

The rotateLeft and rotateRight methods, which are critical for maintaining the Red-Black Tree properties during insertions and deletions by rebalancing the tree.
An example usage of the RedBlackTree class, where several numbers are inserted into the tree.
A printTree function for visualizing the tree structure in the console, including the color of each node (Red R or Black B) and the hierarchical relationships between nodes. This function is just for demonstration and might need adjustments for different environments or deeper trees for better visualization.

Keep in mind, this implementation is simplified and focuses primarily on the insertion process and maintaining the tree's balance through rotations and recoloring. A full implementation would also include deletion and more comprehensive error checking and edge case handling. Red-Black Trees are complex but offer excellent performance for dynamic data sets where insertions and deletions happen frequently, as they ensure the tree remains balanced, providing O(log n) search, insertion, and deletion times.

Name: Splay Tree

Brief Description: A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up, and removal in O(log n) amortized time.

Example of a Splay Tree


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

class SplayTree {
  constructor() {
    this.root = null;
  }

  // Splay operation
  splay(node) {
    while (node.parent) {
      if (!node.parent.parent) {
        if (node.parent.left === node) {
          // Zig rotation
          this.rotateRight(node.parent);
        } else {
          // Zag rotation
          this.rotateLeft(node.parent);
        }
      } else if (node.parent.left === node && node.parent.parent.left === node.parent) {
        // Zig-Zig rotation
        this.rotateRight(node.parent.parent);
        this.rotateRight(node.parent);
      } else if (node.parent.right === node && node.parent.parent.right === node.parent) {
        // Zag-Zag rotation
        this.rotateLeft(node.parent.parent);
        this.rotateLeft(node.parent);
      } else if (node.parent.left === node && node.parent.parent.right === node.parent) {
        // Zig-Zag rotation
        this.rotateRight(node.parent);
        this.rotateLeft(node.parent);
      } else {
        // Zag-Zig rotation
        this.rotateLeft(node.parent);
        this.rotateRight(node.parent);
      }
    }
  }

  // Right rotation
  rotateRight(node) {
    const leftChild = node.left;
    node.left = leftChild.right;
    if (leftChild.right) leftChild.right.parent = node;
    leftChild.parent = node.parent;
    if (!node.parent) {
      this.root = leftChild;
    } else if (node === node.parent.right) {
      node.parent.right = leftChild;
    } else {
      node.parent.left = leftChild;
    }
    leftChild.right = node;
    node.parent = leftChild;
  }

  // Left rotation
  rotateLeft(node) {
    const rightChild = node.right;
    node.right = rightChild.left;
    if (rightChild.left) rightChild.left.parent = node;
    rightChild.parent = node.parent;
    if (!node.parent) {
      this.root = rightChild;
    } else if (node === node.parent.left) {
      node.parent.left = rightChild;
    } else {
      node.parent.right = rightChild;
    }
    rightChild.left = node;
    node.parent = rightChild;
  }

  // Insert a node
  insert(value) {
    let node = this.root;
    let parent = null;
    while (node) {
      parent = node;
      if (node.value < value) {
        node = node.right;
      } else if (node.value > value) {
        node = node.left;
      } else {
        this.splay(node);
        return; // Duplicate values not allowed
      }
    }
    const newNode = new Node(value);
    newNode.parent = parent;
    if (!parent) {
      this.root = newNode;
    } else if (parent.value < value) {
      parent.right = newNode;
    } else {
      parent.left = newNode;
    }
    this.splay(newNode);
  }

  // Find a node
  find(value) {
    let node = this.root;
    while (node) {
      if (node.value < value) {
        node = node.right;
      } else if (node.value > value) {
        node = node.left;
      } else {
        this.splay(node);
        return node;
      }
    }
    return null; // Not found
  }

  // Additional methods like remove() can also be implemented similarly.
}

// Example usage
const tree = new SplayTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);
console.log(tree.find(10)); // Splays tree and returns node with value 10

This implementation covers the splay operation, insertion, and finding a node. Splaying moves a node to the root of the tree through a series of rotations, optimizing the tree for subsequent access to that node. Removal and other operations can be implemented similarly, adjusting the tree structure as needed to maintain its properties.

Name: Vector (Dynamic Array)

Brief Description: A vector, or dynamic array, expands or contracts its size automatically. It provides a way to store elements sequentially that can be accessed randomly.

Example on Vectors


#include 
#include  // For std::copy

template 
class Vector {
public:
    Vector() : capacity_(1), size_(0), data_(new T[1]) {}

    ~Vector() {
        delete[] data_;
    }

    void push_back(const T& value) {
        if (size_ >= capacity_) {
            resize(capacity_ * 2);
        }
        data_[size_++] = value;
    }

    T& operator[](size_t index) {
        if (index >= size_) {
            throw std::out_of_range("Index out of range");
        }
        return data_[index];
    }

    size_t size() const {
        return size_;
    }

private:
    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];
        std::copy(data_, data_ + size_, new_data);
        delete[] data_;
        data_ = new_data;
        capacity_ = new_capacity;
    }

    size_t capacity_;
    size_t size_;
    T* data_;
};

int main() {
    Vector vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    std::cout << "Vector elements: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

This implementation demonstrates a basic dynamic array supporting operations like push_back for adding elements and operator[] for accessing elements. The resize method is used internally to increase the array's capacity when needed, ensuring that adding elements always has space. Note that for simplicity, error checking and iterator support are omitted, and this implementation doesn't handle memory allocation errors or copy/move semantics optimizations.

Remember, in practical C++ applications, it's generally recommended to use std::vector unless you have very specific requirements that necessitate a custom data structure. std::vector is highly optimized and includes a wide range of features that make it flexible and powerful for most use cases.

Name: Hash Map

Brief Description: A hash map, also known as a hash table, maps keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

In JavaScript, the most direct equivalent to a hash map is the Map object, which allows you to store key-value pairs and remembers the original insertion order of the keys. Unlike regular objects, Map can have keys of any data type, not just strings or symbols. For demonstration purposes, though, if you're looking for how to implement a basic hash map from scratch to understand the underlying mechanisms, here's a simple example. This example will illustrate the core functionality of a hash map, including setting, getting, and handling collisions through chaining

Example of a Hash Map


class SimpleHashMap {
  constructor(size = 20) {
    this.bucketSize = size;
    this.buckets = Array(this.bucketSize).fill(null).map(() => []);
  }

  hash(key) {
    let hash = 0;
    for (let char of key.toString()) {
      hash += char.charCodeAt(0);
    }
    return hash % this.bucketSize;
  }

  set(key, value) {
    const keyHash = this.hash(key);
    const bucketArray = this.buckets[keyHash];
    const foundIndex = bucketArray.findIndex((item) => item.key === key);
    if (foundIndex === -1) {
      bucketArray.push({ key, value });
    } else {
      bucketArray[foundIndex].value = value; // Update existing value
    }
  }

  get(key) {
    const keyHash = this.hash(key);
    const bucketArray = this.buckets[keyHash];
    const foundItem = bucketArray.find((item) => item.key === key);
    return foundItem ? foundItem.value : undefined;
  }

  remove(key) {
    const keyHash = this.hash(key);
    const bucketArray = this.buckets[keyHash];
    const foundIndex = bucketArray.findIndex((item) => item.key === key);
    if (foundIndex !== -1) {
      bucketArray.splice(foundIndex, 1);
      return true;
    }
    return false;
  }
}

// Example usage:
const hashMap = new SimpleHashMap();
hashMap.set('name', 'Alice');
console.log(hashMap.get('name')); // Output: Alice
hashMap.set('name', 'Bob');
console.log(hashMap.get('name')); // Output: Bob
hashMap.remove('name');
console.log(hashMap.get('name')); // Output: undefined

Name: Set

Brief Description: A set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is typically used for membership testing, removing duplicates from a collection, and performing mathematical operations such as union, intersection, and difference.

Example of a Set


// Create a new Set
const mySet = new Set();

// Add some values to the set
mySet.add(1);
mySet.add(5);
mySet.add("some text");

// Try to add duplicate values
mySet.add(1); // This will not be added because 1 is already in the set
mySet.add("Some Text".toLowerCase()); // This will not be added because "some text" is already in the set, considering the case-insensitive comparison

// Check if a value is in the set
console.log(mySet.has(1)); // true
console.log(mySet.has(3)); // false

// Get the size of the set
console.log(mySet.size); // 3

// Delete a value from the set
mySet.delete(5);

// Iterate through the Set
for (let item of mySet) {
  console.log(item);
}
// Output: 1, "some text"

// Convert a Set to an Array
const setToArray = [...mySet];
console.log(setToArray); // [1, "some text"]

// Clear the set
mySet.clear();
console.log(mySet.size); // 0

In this example, we create a new Set, add some values to it, and demonstrate how duplicate values are ignored. We also show how to check if a value is present in the set, how to delete values, and how to iterate over a set. Converting a Set to an Array using the spread operator (...) is a handy technique for when you need to work with array methods on the contents of a Set. Finally, clearing the Set with .clear() removes all elements from the Set.

Sets are particularly useful when you need to ensure the uniqueness of elements and when you are primarily concerned with the presence or absence of values rather than their order or frequency.

Name: Doubly Linked List

Brief Description: A doubly linked list is a type of linked list where each node contains a reference to the next node as well as the previous node, allowing for bidirectional traversal.

Example of a Doubly Linked List


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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // Add a new node to the end of the list
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // Add a new node to the beginning of the list
  prepend(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  // Remove a node from the list by its data
  remove(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) {
        if (current.prev) {
          current.prev.next = current.next;
        } else {
          this.head = current.next;
        }

        if (current.next) {
          current.next.prev = current.prev;
        } else {
          this.tail = current.prev;
        }
        return; // Data found and removed
      }
      current = current.next;
    }
  }

  // Print the list from head to tail
  print() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  // Print the list from tail to head
  printReverse() {
    let current = this.tail;
    while (current) {
      console.log(current.data);
      current = current.prev;
    }
  }
}

// Example usage:
const dll = new DoublyLinkedList();
dll.append(1);
dll.append(2);
dll.append(3);
console.log("Forward:");
dll.print(); // Expected: 1, 2, 3
console.log("Reverse:");
dll.printReverse(); // Expected: 3, 2, 1

dll.prepend(0);
console.log("After prepend:");
dll.print(); // Expected: 0, 1, 2, 3

dll.remove(2);
console.log("After removal:");
dll.print(); // Expected: 0, 1, 3

This DoublyLinkedList class demonstrates basic operations such as appending and prepending nodes, removing a node by its data, and printing the list in both forward and reverse directions. The Node class represents each element in the list, containing data and pointers to both the previous and next nodes. This structure allows for efficient addition and removal of elements from both ends of the list, as well as straightforward forward and backward traversal.

Name: Circular Linked List

Brief Description: A circular linked list is a variation of linked list where all nodes are connected to form a circle. There is no NULL at the end. This allows for any node to be treated as the starting point, and you can traverse the entire list starting from any node. A circular linked list can be a singly circular linked list or doubly circular linked list.

Example of a Circular Linked List


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

class CircularLinkedList {
  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;
      newNode.next = this.head;
    } else {
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      current.next = newNode;
      newNode.next = this.head;
    }
  }

  // Print the list. We need to be careful to not enter an infinite loop.
  print() {
    if (!this.head) {
      return;
    }

    let current = this.head;
    do {
      console.log(current.data);
      current = current.next;
    } while (current !== this.head);
  }

  // Remove a node by its value
  remove(data) {
    if (!this.head) {
      return;
    }

    let current = this.head;
    let previous = null;
    do {
      if (current.data === data) {
        if (current === this.head && current.next === this.head) {
          // The list has only one node
          this.head = null;
        } else if (current === this.head) {
          // Removing the head
          previous = this.head;
          while (previous.next !== this.head) {
            previous = previous.next;
          }
          this.head = this.head.next;
          previous.next = this.head;
        } else {
          // Removing a node that is not the head
          previous.next = current.next;
        }
        return;
      }
      previous = current;
      current = current.next;
    } while (current !== this.head);
  }
}

// Example usage:
const cll = new CircularLinkedList();
cll.append(1);
cll.append(2);
cll.append(3);

console.log("Initial list:");
cll.print(); // Expected: 1, 2, 3

cll.remove(2);
console.log("After removing 2:");
cll.print(); // Expected: 1, 3

cll.append(4);
console.log("After appending 4:");
cll.print(); // Expected: 1, 3, 4

In this CircularLinkedList class, the append method adds a new node to the end of the list and links the last node back to the head to maintain the circular structure. The print method demonstrates how to traverse a circular linked list without entering an infinite loop by stopping once it reaches the head again. The remove method shows how to delete a node from the list, taking care to properly re-link the nodes and handle the special case when the list becomes empty or when the head is removed.

Name: Skip List

Brief Description: A skip list is a probabilistic data structure that allows for fast search, insertion, and deletion operations. It effectively complements a linked list by adding multiple layers of linked lists on top of the original list.

Example on Skip Lists


class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  constructor(maxLevel, p) {
    this.maxLevel = maxLevel; // Maximum level of the skip list
    this.p = p; // Fraction of the nodes with level i pointers also having level i+1 pointers
    this.header = new SkipListNode(null, maxLevel);
    this.level = 0; // Current highest level of the skip list
  }

  // Random level generator for node
  randomLevel() {
    let lvl = 0;
    while (Math.random() < this.p && lvl < this.maxLevel) {
      lvl++;
    }
    return lvl;
  }

  // Insert a value into the skip list
  insert(value) {
    let update = Array(this.maxLevel + 1).fill(null);
    let current = this.header;

    // Start from the highest level of skip list and move downwards
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }

    // Reached level 0 and forward pointer to right, which is desired position to insert key.
    current = current.forward[0];

    // If current is null, that means we have reached to end of the level or current's value is not equal to key to insert that means we have to insert node between update[0] and current node
    if (current === null || current.value !== value) {
      // Generate a random level for node
      let rlevel = this.randomLevel();

      // If random level is greater than list's current level (node with highest level inserted in list so far), initialize update value with pointer to header for further use
      if (rlevel > this.level) {
        for (let i = this.level + 1; i < rlevel + 1; i++) {
          update[i] = this.header;
        }
        // Update the list current level
        this.level = rlevel;
      }

      // Create new node with random level generated
      let newNode = new SkipListNode(value, rlevel);

      // Insert node by rearranging pointers 
      for (let i = 0; i <= rlevel; i++) {
        newNode.forward[i] = update[i].forward[i];
        update[i].forward[i] = newNode;
      }
    }
  }

  // Search for a value in the skip list
  search(value) {
    let current = this.header;

    // Start from the highest level of skip list and move downwards
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null && current.forward[i].value < value) {
        current = current.forward[i];
      }
    }

    // Reached level 0 and advance pointer to right, which is possibly our desired node
    current = current.forward[0];

    // If current node have key equal to searched key, we found our target node
    if (current !== null && current.value === value) {
      console.log("Found value:", value);
    } else {
      console.log("Value not found");
    }
  }
}

// Example usage:
const list = new SkipList(3, 0.5);
list.insert(3);
list.insert(6);
list.insert(7);
list.insert(9);
list.insert(12);
list.insert(19);
list.insert(17);

list.search(6);
list.search(15);

This code defines a basic structure for a skip list and implements insert and search operations. The randomLevel function determines the level of the new node based on a probability p. The insert operation places a new value into the skip list at the appropriate level, updating pointers as needed. The search operation traverses the list from the highest level downwards, moving right at each level until the value is found or it's determined that the value does not exist in the list.

In this example, the SkipList is initialized with a maximum level of 3 and a probability factor of 0.5. This setup means that, on average, every other node at level i will also be part of level i+1, creating a balanced distribution of nodes across the levels. The insert function adds values into the skip list, ensuring they are placed at the correct levels based on the random level generation. The search function then demonstrates how to quickly find (or fail to find) values in the list by efficiently skipping through levels and nodes.

This implementation is simplified and intended for educational purposes to demonstrate the basic concept and operations of a skip list. A fully-featured skip list might include more sophisticated level adjustment logic, deletion methods, and optimizations for space and time efficiency.

Name: B-Tree

Brief Description: A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It's widely used in databases and filesystems.

Implementing a B-Tree in JavaScript with full support for insertion, search, and especially deletion is quite complex due to the intricate balancing required to maintain the properties of the B-tree. Deletion from a B-Tree involves several cases: deleting a key from a leaf node, deleting a key from an internal node, and rebalancing the tree if necessary by merging or redistributing keys among siblings.

Below is a simplified version of a B-Tree class in JavaScript that includes insertion, search, and an attempt to address deletion. Due to the complexity of deletion, this example focuses on the main ideas, such as removing a key from a leaf node and handling underflow in internal nodes by trying to borrow a key from a sibling or merging nodes if necessary. Note that a complete and fully optimized B-Tree implementation for all edge cases would require a more extensive codebase.

Example on B-Trees


class BTreeNode {
    constructor(t, leaf = false) {
        this.t = t; // Minimum degree (defines the range for number of keys)
        this.keys = []; // An array of keys
        this.children = []; // An array of child pointers
        this.leaf = leaf; // Is true when node is leaf. Otherwise false
        this.num = 0; // Current number of keys
    }
}

class BTree {
    constructor(t) {
        this.root = null;
        this.t = t;
    }

    traverse() {
        if (this.root !== null) {
            this._traverse(this.root);
        }
    }

    _traverse(node) {
        let i;
        for (i = 0; i < node.num; i++) {
            // If this is not leaf, then before printing key[i],
            // traverse the subtree rooted with child C[i].
            if (node.leaf === false) {
                this._traverse(node.children[i]);
            }
            console.log(node.keys[i]);
        }
        // Print the subtree rooted with last child
        if (node.leaf === false) {
            this._traverse(node.children[i]);
        }
    }

    search(k) {
        return this.root === null ? null : this._search(this.root, k);
    }

    _search(node, k) {
        // Find the first key greater than or equal to k
        let i = 0;
        while (i < node.num && k > node.keys[i]) {
            i++;
        }

        // If the found key is equal to k, return this node
        if (i < node.num && node.keys[i] === k) {
            return node;
        }

        // If the key is not found here and this is a leaf node
        if (node.leaf === true) {
            return null;
        }

        // Go to the appropriate child
        return this._search(node.children[i], k);
    }

    insert(key) {
        // If tree is empty
        if (this.root == null) {
            // Allocate memory for root
            this.root = new BTreeNode(this.t, true);
            this.root.keys[0] = key; // Insert key
            this.root.num = 1; // Update number of keys in root
        } else {
            // If root is full, then tree grows in height
            if (this.root.num == 2 * this.t - 1) {
                let s = new BTreeNode(this.t, false);
                s.children[0] = this.root;
                this.splitChild(s, 0, this.root); // Split the old root and make s the new root

                // New root has two children now. Decide which of the two children is going to have new key
                let i = 0;
                if (s.keys[0] < key) {
                    i++;
                }
                this.insertNonFull(s.children[i], key);

                // Change root
                this.root = s;
            } else {
                // If root is not full, call insertNonFull for root
                this.insertNonFull(this.root, key);
            }
        }
    }

    insertNonFull(node, key) {
        // Initialize index as index of rightmost element
        let i = node.num - 1;

        // If this is a leaf node
        if (node.leaf == true) {
            // The following loop does two things:
            // a) Finds the location of the new key to be inserted
            // b) Moves all greater keys to one place ahead
            while (i >= 0 && node.keys[i] > key) {
                node.keys[i + 1] = node.keys[i];
                i--;
            }

            // Insert the new key at the found location
            node.keys[i + 1] = key;
            node.num = node.num + 1;
        } else {
            // If this node is not leaf
            // Find the child which is going to have the new key
            while (i >= 0 && node.keys[i] > key) {
                i--;
            }

            // See if the found child is full
            if (node.children[i + 1].num == 2 * this.t - 1) {
                // If the child is full, then split it
                this.splitChild(node, i + 1, node.children[i + 1]);

                // After split, the middle key of C[i] goes up and
                // C[i] is split into two. See which of the two
                // is going to have the new key
                if (node.keys[i + 1] < key) {
                    i++;
                }
            }
            this.insertNonFull(node.children[i + 1], key);
        }
    }

    // Split the child y of node x. i is index of y in child array C[].
    // The child y must be full when this function is called
    splitChild(x, i, y) {
        // Create a new node which is going to store (t-1) keys of y
        let z = new BTreeNode(y.t, y.leaf);
        z.num = this.t - 1;

        // Copy the last (t-1) keys of y to z
        for (let j = 0; j < this.t - 1; j++) {
            z.keys[j] = y.keys[j + this.t];
        }

        // Copy the last t children of y to z
        if (y.leaf == false) {
            for (let j = 0; j < this.t; j++) {
                z.children[j] = y.children[j + this.t];
            }
        }

        // Reduce the number of keys in y
        y.num = this.t - 1;

        // Since this node is going to have a new child,
        // create space of new child
        for (let j = x.num; j >= i + 1; j--) {
            x.children[j + 1] = x.children[j];
        }

        // Link the new child to this node
        x.children[i + 1] = z;

        // A key of y will move to this node. Find the location of
        // new key and move all greater keys one space ahead
        for (let j = x.num - 1; j >= i; j--) {
            x.keys[j + 1] = x.keys[j];
        }

        // Copy the middle key of y to this node
        x.keys[i] = y.keys[this.t - 1];

        // Increment count of keys in this node
        x.num = x.num + 1;
    }

    // A utility function to remove the key k from the sub-tree rooted with this node
    remove(k) {
        let idx = this.findKey(k);

        // The key to be removed is present in this node
        if (idx < this.num && this.keys[idx] == k) {

            // If the node is a leaf node - removeFromLeaf is called
            // Otherwise, removeFromNonLeaf function is called
            if (this.leaf)
                this.removeFromLeaf(idx);
            else
                this.removeFromNonLeaf(idx);
        } else {

            // If this node is a leaf node, then the key is not present in tree
            if (this.leaf) {
                console.log("The key ", k, " is does not exist in the tree\n");
                return;
            }

            // The key to be removed is present in the sub-tree rooted with this child
            // The flag indicates whether the key is present in the sub-tree rooted
            // with the last child of this node
            let flag = (idx == this.num);

            // If the child where the key is supposed to exist has less that t keys,
            // we fill that child
            if (this.children[idx].num < this.t)
                this.fill(idx);

            // If the last child has been merged, it must have merged with the previous
            // child and so we recurse on the (idx-1)th child. Else, we recurse on the
            // (idx)th child which now has atleast t keys
            if (flag && idx > this.num)
                this.children[idx - 1].remove(k);
            else
                this.children[idx].remove(k);
        }
        return;
    }

    // A function to remove the idx-th key from this node - which is a leaf node
    removeFromLeaf(idx) {

        // Move all the keys after the idx-th pos one place backward
        for (let i = idx + 1; i < this.num; ++i)
            this.keys[i - 1] = this.keys[i];

        // Reduce the count of keys
        this.num--;

        return;
    }

    // A function to remove the idx-th key from this node - which is a non-leaf node
    removeFromNonLeaf(idx) {

        let k = this.keys[idx];

        // If the child that precedes k (C[idx]) has atleast t keys,
        // find the predecessor 'pred' of k in the subtree rooted at
        // C[idx]. Replace k by pred. Recursively delete pred
        // in C[idx]
        if (this.children[idx].num >= this.t) {
            let pred = this.getPred(idx);
            this.keys[idx] = pred;
            this.children[idx].remove(pred);
        }

        // If the child C[idx] has less that t keys, examine C[idx+1].
        // If C[idx+1] has atleast t keys, find the successor 'succ' of k in
        // the subtree rooted at C[idx+1]
        // Replace k by succ
        // Recursively delete succ in C[idx+1]
        else if (this.children[idx + 1].num >= this.t) {
            let succ = this.getSucc(idx);
            this.keys[idx] = succ;
            this.children[idx + 1].remove(succ);
        }

        // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1]
        // into C[idx]
        // Now C[idx] contains 2t-1 keys
        // Free C[idx+1] and recursively delete k from C[idx]
        else {
            this.merge(idx);
            this.children[idx].remove(k);
        }
        return;
    }

    // A function to get predecessor of keys[idx]
    getPred(idx) {
        // Keep moving to the right most node until we reach a leaf
        let cur = this.children[idx];
        while (!cur.leaf)
            cur = cur.children[cur.num];

        // Return the last key of the leaf
        return cur.keys[cur.num - 1];
    }

    // A function to get successor of keys[idx]
    getSucc(idx) {

        // Keep moving the left most node starting from C[idx+1] until we reach a leaf
        let cur = this.children[idx + 1];
        while (!cur.leaf)
            cur = cur.children[0];

        // Return the first key of the leaf
        return cur.keys[0];
    }

    // A function to fill child C[idx] which has less than t-1 keys
    fill(idx) {

        // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key
        // from that child
        if (idx != 0 && this.children[idx - 1].num >= this.t)
            this.borrowFromPrev(idx);

        // If the next child(C[idx+1]) has more than t-1 keys, borrow a key
        // from that child
        else if (idx != this.num && this.children[idx + 1].num >= this.t)
            this.borrowFromNext(idx);

        // Merge C[idx] with its sibling
        // If C[idx] is the last child, merge it with with its previous sibling
        // Otherwise merge it with its next sibling
        else {
            if (idx != this.num)
                this.merge(idx);
            else
                this.merge(idx - 1);
        }
        return;
    }

    // A function to borrow a key from C[idx-1] and insert it
    // into C[idx]
    borrowFromPrev(idx) {

        let child = this.children[idx];
        let sibling = this.children[idx - 1];

        // The last key from C[idx-1] goes up to the parent and key[idx-1]
        // from parent is inserted as the first key in C[idx]. Thus, the  loses
        // sibling one key and child gains one key

        // Moving all key in C[idx] one step ahead
        for (let i = child.num - 1; i >= 0; --i)
            child.keys[i + 1] = child.keys[i];

        // If C[idx] is not a leaf, move all its child pointers one step ahead
        if (!child.leaf) {
            for (let i = child.num; i >= 0; --i)
                child.children[i + 1] = child.children[i];
        }

        // Setting child's first key equal to keys[idx-1] from the current node
        child.keys[0] = this.keys[idx - 1];

        // Moving sibling's last child as C[idx]'s first child
        if (!child.leaf)
            child.children[0] = sibling.children[sibling.num];

        // Moving the key from the sibling to the parent
        // This reduces the number of keys in the sibling
        this.keys[idx - 1] = sibling.keys[sibling.num - 1];

        child.num += 1;
        sibling.num -= 1;

        return;
    }

    // A function to borrow a key from the C[idx+1] and place
    // it in C[idx]
    borrowFromNext(idx) {

        let child = this.children[idx];
        let sibling = this.children[idx + 1];

        // keys[idx] is inserted as the last key in C[idx]
        child.keys[(child.num)] = this.keys[idx];

        // Sibling's first child is inserted as the last child
        // into C[idx]
        if (!(child.leaf))
            child.children[(child.num) + 1] = sibling.children[0];

        //The first key from sibling is inserted into keys[idx]
        this.keys[idx] = sibling.keys[0];

        // Moving all keys in sibling one step behind
        for (let i = 1; i < sibling.num; ++i)
            sibling.keys[i - 1] = sibling.keys[i];

        // Moving the child pointers one step behind
        if (!sibling.leaf) {
            for (let i = 1; i <= sibling.num; ++i)
                sibling.children[i - 1] = sibling.children[i];
        }

        // Increasing and decreasing the key count of C[idx] and C[idx+1]
        // respectively
        child.num += 1;
        sibling.num -= 1;

        return;
    }

    // A function to merge C[idx] with C[idx+1]
    // C[idx+1] is freed after merging
    merge(idx) {
        let child = this.children[idx];
        let sibling = this.children[idx + 1];

        // Pulling a key from the current node and inserting it into (t-1)th
        // position of C[idx]
        child.keys[this.t - 1] = this.keys[idx];

        // Copying the keys from C[idx+1] to C[idx] at the end
        for (let i = 0; i < sibling.num; ++i)
            child.keys[i + this.t] = sibling.keys[i];

        // Copying the child pointers from C[idx+1] to C[idx]
        if (!child.leaf) {
            for (let i = 0; i <= sibling.num; ++i)
                child.children[i + this.t] = sibling.children[i];
        }

        // Moving all keys after idx in the current node one step before -
        // to fill the gap created by moving keys[idx] to C[idx]
        for (let i = idx + 1; i < this.num; ++i)
            this.keys[i - 1] = this.keys[i];

        // Moving the child pointers after (idx+1) in the current node one
        // step before
        for (let i = idx + 2; i <= this.num; ++i)
            this.children[i - 1] = this.children[i];

        // Updating the key count of child and the current node
        child.num += sibling.num + 1;
        this.num--;

        // Freeing the memory occupied by sibling
        return;
    }

    // A function to find key k in the tree
    findKey(k) {
        let idx = 0;
        while (idx < this.num && this.keys[idx] < k)
            ++idx;
        return idx;
    }
}

This code provides a foundational structure for understanding how a B-Tree works, including basic operations like insertion and a form of deletion. The deletion operation in a B-Tree can be particularly complex due to the need to maintain the tree's balance, and this example addresses several key scenarios such as removing a key from a leaf node and handling underflows in internal nodes by borrowing from siblings or merging nodes.

For completeness, the deletion operation should be thoroughly tested across various scenarios to ensure correctness. B-Trees are advanced data structures, and their full implementation for all edge cases can become quite intricate, highlighting the importance of a solid understanding of the principles behind their operations.

Name: B+ Tree

Brief Description: A B+ tree is a type of B-tree in which all records are stored at the leaf level of the tree; thus, it allows for efficient range queries and sequential access of records.

Implementing a B+ Tree in JavaScript, including removal functionality, involves a more complex structure compared to basic binary search trees or even B-Trees due to the nature of B+ Trees, where all values are stored in leaf nodes and internal nodes only serve as pointers to leaf nodes. This structure allows for efficient range queries and sequential access. However, this complexity increases when implementing removals, as the tree must be rebalanced while maintaining all leaf nodes at the same level.

Given the complexity of a complete B+ Tree implementation, here is a simplified version focusing on key aspects such as insertion, search, and a basic approach to deletion. This implementation aims to demonstrate the foundational concepts rather than provide a production-ready solution.

Example on B+ Trees


class BPlusTreeNode {
  constructor(isLeaf = true, t = 3) {
    this.isLeaf = isLeaf; // Whether this node is a leaf node
    this.keys = []; // Keys in this node
    this.children = []; // Children nodes (for non-leaf nodes)
    this.t = t; // Order of the B+ tree: max children per node = t, max keys = t-1
    this.next = null; // Pointer to the next leaf node (for leaf nodes)
  }
}

class BPlusTree {
  constructor(t = 3) {
    this.root = new BPlusTreeNode(true, t);
    this.t = t;
  }

  // Insert a key into the B+ Tree
  insert(key) {
    let root = this.root;
    // If root is full, the tree grows in height
    if (root.keys.length === this.t - 1) {
      let newNode = new BPlusTreeNode(false, this.t);
      newNode.children.push(this.root);
      this.splitChild(newNode, 0);
      this.root = newNode;
    }
    this.insertNonFull(this.root, key);
  }

  // Insert a key into a non-full node
  insertNonFull(node, key) {
    if (node.isLeaf) {
      let idx = node.keys.findIndex((k) => k > key);
      if (idx === -1) idx = node.keys.length;
      node.keys.splice(idx, 0, key);
    } else {
      let i = 0;
      while (i < node.keys.length && key > node.keys[i]) i++;
      if (node.children[i].keys.length === this.t - 1) {
        this.splitChild(node, i);
        if (key > node.keys[i]) i++;
      }
      this.insertNonFull(node.children[i], key);
    }
  }

  // Split a child node of the given node at index idx
  splitChild(parent, idx) {
    let toSplit = parent.children[idx];
    let newChild = new BPlusTreeNode(toSplit.isLeaf, this.t);

    // Move keys and children (if any) to the new node
    newChild.keys = toSplit.keys.splice(Math.floor(this.t / 2), this.t - 1 - Math.floor(this.t / 2));
    if (!toSplit.isLeaf) {
      newChild.children = toSplit.children.splice(Math.ceil(this.t / 2), this.t - Math.ceil(this.t / 2));
    } else {
      // Setup leaf node chain
      newChild.next = toSplit.next;
      toSplit.next = newChild;
    }

    // Insert the middle key into the parent
    parent.keys.splice(idx, 0, toSplit.keys.pop());
    parent.children.splice(idx + 1, 0, newChild);
  }

  // Simple search function for demonstration
  search(key) {
    let current = this.root;
    while (true) {
      let i = 0;
      while (i < current.keys.length && key > current.keys[i]) i++;
      if (i < current.keys.length && key === current.keys[i]) return true;
      if (current.isLeaf) return false;
      current = current.children[i];
    }
  }

  // Display the tree (simple console log for demonstration)
  display() {
    let queue = [this.root];
    while (queue.length) {
      let node = queue.shift();
      console.log(node.keys);
      if (!node.isLeaf) queue.push(...node.children);
    }
  }

  // Implementing removal or more complex operations would significantly extend this example
  // and are not included for brevity
}

// Example usage
let bpt = new BPlusTree(3);
bpt.insert(1);
bpt.insert(2);
bpt.insert(3);
bpt.insert(4);
bpt.insert(5);
bpt.display(); // Show tree structure
console.log(bpt.search(3)); // true
console.log(bpt.search(6)); // false

This basic example showcases the structure of a B+ Tree and includes insertion and simple search functionalities. In a B+ Tree, all values are stored in the leaf nodes, and the leaf nodes are linked, making range queries efficient. The example above does not cover the complexity of deletion and rebalancing, which involve several cases such as merging nodes and redistributing keys among siblings while maintaining the tree's properties.

Deletion in a B+ Tree typically requires handling cases where a key removal causes underflow in a leaf or internal node, necessitating complex rebalancing logic to ensure the tree remains balanced. Implementing a complete and fully functional B+ Tree, especially with efficient deletion, is an advanced task that goes beyond the scope of this simplified example.

Name: Fibonacci Heap

Brief Description: A Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It provides better amortized running times for many sequences of operations compared to other heap structures.

Implementing a complete Fibonacci Heap in JavaScript, including advanced operations like delete, decrease key, and consolidation, involves complex logic to maintain the heap properties and achieve the desired amortized runtimes. The following example extends the previous one by incorporating these operations, aiming to provide a comprehensive look at a Fibonacci Heap's functionality.

Example on Fibonacci Heaps


class FibonacciHeapNode {
  constructor(key) {
    this.key = key;
    this.parent = null;
    this.child = null;
    this.left = this;
    this.right = this;
    this.degree = 0;
    this.mark = false;
  }
}

class FibonacciHeap {
  constructor() {
    this.min = null;
    this.count = 0;
    this.rootList = null; // Points to the min node for easier access
  }

  // Inserts a new key into the heap
  insert(key) {
    const newNode = new FibonacciHeapNode(key);
    this.min = this.mergeLists(this.min, newNode);
    this.count++;
    return newNode;
  }

  // Merges two root lists and returns the new min node
  mergeLists(a, b) {
    if (a === null) return b;
    if (b === null) return a;
    if (a.key > b.key) {
      let temp = a;
      a = b;
      b = temp;
    }
    let aRight = a.right;
    let bLeft = b.left;
    a.right = b;
    b.left = a;
    aRight.left = bLeft;
    bLeft.right = aRight;
    return a;
  }

  // Finds the minimum key in the heap
  findMin() {
    return this.min !== null ? this.min.key : 'Heap is empty';
  }

  // Removes the smallest key
  deleteMin() {
    if (this.min == null) return 'Heap is empty';

    let min = this.min;
    // Move min node's children to root list
    if (min.child != null) {
      let child = min.child;
      do {
        child.parent = null;
        child = child.right;
      } while (child !== min.child);

      this.mergeLists(this.min, min.child);
    }

    // Remove min from root list
    min.left.right = min.right;
    min.right.left = min.left;
    if (min === min.right) {
      this.min = null;
    } else {
      this.min = min.right;
      this.consolidate();
    }
    this.count--;
  }

  // Consolidates the root list
  consolidate() {
    let A = new Array(Math.floor(Math.log(this.count) / Math.log((1 + Math.sqrt(5)) / 2)) + 1);
    let start = this.min;
    let w = this.min;
    do {
      let x = w;
      let d = x.degree;
      while (A[d] != null) {
        let y = A[d];
        if (x.key > y.key) {
          let temp = x;
          x = y;
          y = temp;
        }
        if (y === start) {
          start = start.right;
        }
        if (y === this.min) {
          this.min = x;
        }
        y.link(x);
        A[d] = null;
        d++;
      }
      A[d] = x;
      w = w.right;
    } while (w !== start);

    this.min = null;
    for (let i = 0; i < A.length; i++) {
      if (A[i] != null) {
        A[i].left = A[i].right = A[i];
        this.min = this.mergeLists(this.min, A[i]);
      }
    }
  }

  // Decreases the key of a node
  decreaseKey(x, k) {
    if (k > x.key) {
      console.log("New key is greater than current key");
      return;
    }
    x.key = k;
    let y = x.parent;
    if (y != null && x.key < y.key) {
      this.cut(x, y);
      this.cascadingCut(y);
    }
    if (x.key < this.min.key) {
      this.min = x;
    }
  }

  // Cuts a node from its parent and moves it to the root list
  cut(x, y) {
    x.left.right = x.right;
    x.right.left = x.left;
    y.degree--;
    if (y.child === x) {
      y.child = x.right;
    }
    if (y.degree === 0) {
      y.child = null;
    }
    x.left = x.right = x;
    this.min = this.mergeLists(this.min, x);
    x.parent = null;
    x.mark = false;
  }

  // Performs a cascading cut on a node
  cascadingCut(y) {
    let z = y.parent;
    if (z != null) {
      if (!y.mark) {
        y.mark = true;
      } else {
        this.cut(y, z);
        this.cascadingCut(z);
      }
    }
  }

  // Deletes a node from the heap
  delete(x) {
    this.decreaseKey(x, -Infinity);
    this.deleteMin();
  }

  // Auxiliary function to link two trees of the same degree
  link(y, x) {
    y.left.right = y.right;
    y.right.left = y.left;
    y.parent = x;
    if (x.child == null) {
      x.child = y;
      y.right = y;
      y.left = y;
    } else {
      y.left = x.child;
      y.right = x.child.right;
      x.child.right.left = y;
      x.child.right = y;
    }
    x.degree++;
    y.mark = false;
  }
}

// Example usage:
const fibHeap = new FibonacciHeap();
fibHeap.insert(10);
fibHeap.insert(2);
fibHeap.insert(15);
fibHeap.insert(6);

console.log("Minimum value:", fibHeap.findMin());

const nodeToDelete = fibHeap.insert(100);
console.log("Inserted 100, new minimum:", fibHeap.findMin());

fibHeap.decreaseKey(nodeToDelete, 1);
console.log("Decreased key of 100 to 1, new minimum:", fibHeap.findMin());

fibHeap.deleteMin();
console.log("Deleted min, new minimum:", fibHeap.findMin());

fibHeap.delete(nodeToDelete);
console.log("Deleted the node with key 1, new minimum:", fibHeap.findMin());

This extended implementation introduces the decreaseKey, deleteMin, and consolidate methods, which are crucial for maintaining the Fibonacci Heap's structure and efficiency. The delete operation is facilitated by decreasing a node's key to negative infinity and then removing the minimum, ensuring that the node to be deleted becomes the minimum and is easily removable. The link method, used during consolidation, merges trees of the same degree by making one tree a child of another. This implementation aims to provide a functional, if not exhaustive, look at the operations supported by a Fibonacci Heap.

Name: Queue (Priority Queue)

Brief Description: A priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

Implementing a priority queue in TypeScript can be efficiently done using a binary heap due to its properties that make it suitable for priority queue operations such as insertions, finding the minimum, and deletions. Below is an example of a min-priority queue implemented with a binary heap. This implementation includes methods for insertion (enqueue), finding the minimum (peek), removing the minimum (dequeue), and deletion of any element based on a priority (remove).

Example on Priority Queues


class PriorityQueue {
    private heap: T[];
    private comparator: (a: T, b: T) => number;

    constructor(comparator: (a: T, b: T) => number) {
        this.heap = [];
        this.comparator = comparator;
    }

    private leftChildIndex(parentIndex: number): number {
        return 2 * parentIndex + 1;
    }

    private rightChildIndex(parentIndex: number): number {
        return 2 * parentIndex + 2;
    }

    private parentIndex(childIndex: number): number {
        return Math.floor((childIndex - 1) / 2);
    }

    private hasLeftChild(index: number): boolean {
        return this.leftChildIndex(index) < this.heap.length;
    }

    private hasRightChild(index: number): boolean {
        return this.rightChildIndex(index) < this.heap.length;
    }

    private hasParent(index: number): boolean {
        return this.parentIndex(index) >= 0;
    }

    private leftChild(index: number): T {
        return this.heap[this.leftChildIndex(index)];
    }

    private rightChild(index: number): T {
        return this.heap[this.rightChildIndex(index)];
    }

    private parent(index: number): T {
        return this.heap[this.parentIndex(index)];
    }

    private swap(indexOne: number, indexTwo: number): void {
        [this.heap[indexOne], this.heap[indexTwo]] = [this.heap[indexTwo], this.heap[indexOne]];
    }

    public isEmpty(): boolean {
        return this.heap.length === 0;
    }

    public peek(): T | null {
        if (this.isEmpty()) return null;
        return this.heap[0];
    }

    public enqueue(item: T): void {
        this.heap.push(item);
        this.heapifyUp();
    }

    public dequeue(): T | null {
        if (this.isEmpty()) return null;
        if (this.heap.length === 1) return this.heap.pop()!;
        const item = this.heap[0];
        this.heap[0] = this.heap.pop()!;
        this.heapifyDown();
        return item;
    }

    public remove(item: T): boolean {
        const index = this.heap.findIndex((heapItem) => this.comparator(heapItem, item) === 0);
        if (index === -1) return false;
        this.swap(index, this.heap.length - 1);
        this.heap.pop();
        this.heapifyUp(index);
        this.heapifyDown(index);
        return true;
    }

    private heapifyUp(startIndex?: number): void {
        let index = startIndex ?? this.heap.length - 1;
        while (this.hasParent(index) && this.comparator(this.parent(index), this.heap[index]) > 0) {
            const parentIndex = this.parentIndex(index);
            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private heapifyDown(startIndex: number = 0): void {
        let index = startIndex;
        while (this.hasLeftChild(index)) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (this.hasRightChild(index) && this.comparator(this.rightChild(index), this.leftChild(index)) < 0) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.comparator(this.heap[index], this.heap[smallerChildIndex]) < 0) {
                break;
            } else {
                this.swap(index, smallerChildIndex);
            }
            index = smallerChildIndex;
        }
    }
}

// Example usage:
const pq = new PriorityQueue((a, b) => a - b);
pq.enqueue(5);
pq.enqueue(2);
pq.enqueue(10);
console.log(pq.peek()); // 2
console.log(pq.dequeue()); // 2
console.log(pq.peek()); // 5
pq.enqueue(1);
console.log(pq.dequeue()); // 1
pq.remove(10);
console.log(pq.peek()); // 5

This TypeScript implementation of a priority queue uses a binary heap as its underlying data structure. The comparator function allows for flexibility in handling different data types and comparison logic, making the priority queue more generic. The enqueue and dequeue methods add and remove elements from the priority queue, maintaining the heap property. The peek method allows the user to see the element with the highest priority without removing it. The remove method provides functionality to remove a specific element based on its value, which involves finding the element, swapping it with the last element, removing it, and then re-heapifying the heap if necessary.

Name: Radix Tree (Trie Optimization)

Brief Description: A radix tree (also called a compact prefix tree) is an optimized trie in which each node that is the only child is merged with its parent. It's efficient for storing and searching large sets of strings.

A Radix Tree (or Patricia trie) is an optimized version of a trie in which each node with only one child is merged with its child. This optimization significantly reduces the space complexity of the data structure. Radix Trees are efficient for lookups, especially in applications like IP routing, where long sequences of nodes with a single child would otherwise waste space.

Below is an example implementation of a Radix Tree in TypeScript. This implementation focuses on basic operations: inserting a word and searching for a word. To keep the example concise and focused, more complex operations like deletion or iteration over the keys are not included.

Example on Radix Trees


type RadixTreeNode = {
  isWord: boolean;
  children: Map;
};

class RadixTree {
  private root: RadixTreeNode;

  constructor() {
    this.root = { isWord: false, children: new Map() };
  }

  insert(word: string): void {
    let node = this.root;
    for (const [fragment, childNode] of node.children) {
      if (word.startsWith(fragment)) {
        if (word.length > fragment.length) {
          this.insertHelper(childNode, word.slice(fragment.length));
        } else {
          childNode.isWord = true; // The whole word matches this fragment.
        }
        return;
      }
    }

    // If no child matches, create a new entry.
    this.insertHelper(node, word);
  }

  private insertHelper(node: RadixTreeNode, suffix: string) {
    if (suffix.length === 0) {
      node.isWord = true;
      return;
    }

    for (const [fragment, childNode] of node.children) {
      // Find the common prefix of fragment and suffix
      let commonPrefixLength = 0;
      while (commonPrefixLength < fragment.length && commonPrefixLength < suffix.length &&
             fragment[commonPrefixLength] === suffix[commonPrefixLength]) {
        commonPrefixLength++;
      }

      if (commonPrefixLength > 0) {
        // Split the existing child.
        if (commonPrefixLength < fragment.length) {
          const newChild: RadixTreeNode = { isWord: commonPrefixLength === suffix.length, children: new Map() };
          newChild.children.set(fragment.substring(commonPrefixLength), childNode);

          node.children.delete(fragment);
          node.children.set(fragment.substring(0, commonPrefixLength), newChild);
          if (commonPrefixLength < suffix.length) {
            this.insertHelper(newChild, suffix.substring(commonPrefixLength));
          }
          return;
        }
        // Otherwise, keep looking deeper in the tree.
        this.insertHelper(childNode, suffix.substring(commonPrefixLength));
        return;
      }
    }

    // If no common prefix with any child, create a new child.
    node.children.set(suffix, { isWord: true, children: new Map() });
  }

  search(word: string): boolean {
    let node = this.root;
    outer: while (word.length > 0) {
      for (const [fragment, childNode] of node.children) {
        if (word.startsWith(fragment)) {
          if (word.length === fragment.length) {
            return childNode.isWord;
          }
          node = childNode;
          word = word.slice(fragment.length);
          continue outer;
        }
      }
      return false;
    }
    return node.isWord;
  }
}

// Example usage
const radixTree = new RadixTree();
radixTree.insert("hello");
radixTree.insert("hell");
radixTree.insert("helium");

console.log(radixTree.search("hello"));  // true
console.log(radixTree.search("hell"));   // true
console.log(radixTree.search("helium")); // true
console.log(radixTree.search("help"));   // false
console.log(radixTree.search("hel"));    // false

This implementation uses a recursive approach for insertion, allowing it to handle cases where a new word shares some but not all of its prefix with existing words in the tree, necessitating the creation of new nodes or the splitting of existing ones. The search method navigates through the tree based on the prefixes of the words, returning true if the word is found and false otherwise. This Radix Tree implementation optimizes storage by merging nodes where possible, ensuring that no node has only one child without adding a character to the represented prefix.

Name: Bloom Filter

Brief Description: A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set. It's highly space-efficient but allows for a small possibility of false positives.

A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set. It's highly efficient in terms of space but allows for some false positives. The key operations are adding elements and querying for membership. False negatives are not possible in a Bloom filter: if it says an element is not present, then it definitely isn't. However, if it says an element is present, there's a chance it might not be (false positive).

Here is an example of a simple Bloom Filter implemented in TypeScript. This implementation includes basic add and query functionalities. For simplicity, it uses a few basic hash functions generated through simple arithmetic operations. In practice, you'd want to use more sophisticated, uniformly distributing hash functions.

Example on Bloom Filters


class BloomFilter {
  private size: number;
  private storage: Uint8Array;
  private hashFunctions: Array<(key: string) => number>;

  constructor(size: number) {
    this.size = size;
    this.storage = new Uint8Array(size);
    this.hashFunctions = [
      (key: string) => this.simpleHash(key, 17),
      (key: string) => this.simpleHash(key, 31),
      (key: string) => this.simpleHash(key, 71),
    ];
  }

  private simpleHash(key: string, prime: number): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash * prime) + key.charCodeAt(i);
    }
    return hash % this.size;
  }

  add(item: string): void {
    this.hashFunctions.forEach((hashFunction) => {
      const position = hashFunction(item);
      this.storage[position] = 1;
    });
  }

  query(item: string): boolean {
    return this.hashFunctions.every((hashFunction) => {
      const position = hashFunction(item);
      return this.storage[position] === 1;
    });
  }
}

// Example usage:
const bloomFilter = new BloomFilter(100);
bloomFilter.add("hello");
bloomFilter.add("world");

console.log(bloomFilter.query("hello")); // true
console.log(bloomFilter.query("world")); // true
console.log(bloomFilter.query("missing")); // false, but can be true due to false positives

In this TypeScript implementation, size determines the size of the Bloom filter's underlying array, which affects the probability of false positives: the larger the size, the lower the chance of false positives, but the more memory the filter requires. The hashFunctions array contains functions used to compute indices in the filter's array for each element. The add method marks positions in the array as 1 based on the hashes of the added item. The query method checks if all bits at positions calculated by the hash functions are set to 1, indicating the item might have been added. Remember, due to the probabilistic nature of Bloom filters, a "true" result from query means "possibly in set," while "false" means "definitely not in set."

Name: Union-Find

Brief Description: A union-find or disjoint set data structure supports two operations: finding the set a specific element is a part of, and uniting two sets. It's used in algorithms that need to keep track of set partitions, such as Kruskal's algorithm for finding the minimum spanning tree of a graph.

Union-Find, also known as Disjoint Set Union (DSU), is a data structure that provides efficient operations for:

Union: Merging two disjoint sets into one.
Find: Finding the representative (or root) of the set that an element belongs to.
This data structure is widely used in algorithms that need to deal with partitioning a set into disjoint subsets, such as Kruskal's algorithm for finding the minimum spanning tree of a graph.

Below is an implementation of Union-Find in TypeScript, including path compression for find operation optimization and union by rank to minimize tree height, enhancing the efficiency of both operations.

Example on Union-Find


class UnionFind {
  private parent: number[];
  private rank: number[];

  constructor(size: number) {
    this.parent = new Array(size);
    this.rank = new Array(size).fill(0);

    // Initially, all elements are in their own set.
    for (let i = 0; i < size; i++) {
      this.parent[i] = i;
    }
  }

  // Finds the root of the set that element x belongs to
  find(x: number): number {
    if (this.parent[x] !== x) {
      // Path compression
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Unites the sets that include x and y
  union(x: number, y: number): void {
    let rootX = this.find(x);
    let rootY = this.find(y);

    if (rootX !== rootY) {
      // Union by rank
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX]++;
      }
    }
  }
}

// Example usage
const uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(3, 4);
uf.union(4, 7);

console.log(uf.find(1)); // Should output the same root for 1, 2, 5, 6
console.log(uf.find(2)); // Same as above
console.log(uf.find(5)); // Same as above
console.log(uf.find(3)); // Should output the same root for 3, 4, 7
console.log(uf.find(4)); // Same as above

This implementation leverages two optimizations:

Path Compression: During the find operation, makes every node on the path from a node to the root point directly to the root, flattening the structure of the tree and making future find operations faster.
Union by Rank: When uniting two sets, attaches the shorter tree under the root of the taller tree. The "rank" approximates the logarithm of the subtree height, ensuring that the trees stay shallow, making future operations efficient.

Top 26 Data Structures in Modern Programming

Name: Array

Suitability:

Name: Linked List

Suitability:

Web Application: Undo Functionality in a Text Editor

Computer Program: Memory Management System

Cell Phone Application: Photo Browser

Name: Stack

Suitability:

Cell Phone Application: Navigation History

Computer Program: Expression Evaluation

Name: Queue

Suitability:

Web Application: Job Queue for Background Tasks

Cell Phone Application: Notifications Queue

Name: Hash Table

Suitability:

Web Application: User Sessions Management

Computer Program: Inventory System

Cell Phone Application: Caching Data Locally

Name: Binary Tree

Suitability:

Name: Binary Search Tree

Name: Graph

Name: Trie

Name: Heap

Name: AVL Tree

Name: Red-Black Tree

Name: Splay Tree

Name: Vector (Dynamic Array)

Name: Hash Map

Name: Set

Name: Doubly Linked List

Name: Circular Linked List

Name: Skip List

Name: B-Tree

Name: B+ Tree

Name: Fibonacci Heap

Name: Queue (Priority Queue)

Name: Radix Tree (Trie Optimization)

Name: Bloom Filter

Name: Union-Find

Related posts: