Data structure in JS

A data structure is a way of organizing and storing data in a computer or a program- ming language. It defines the relationship between the data elements, the operations that can be performed, and the rules or constraints for accessing and modifying the data.

In theory, you need data structures when you must organize your data in a way that makes it easy and efficient to store and retrieve it according to some special rules.

For example

let fruits = ["apple", "banana"];

// Add an element to the **end** of the array
fruits.push("orange");  // ["apple", "banana", "orange"]

// Add an element to the **beginning** of the array
fruits.unshift("mango");  // ["mango", "apple", "banana", "orange"]

// Add an element at a specific **index**
fruits.splice(2, 0, "grape");  // ["mango", "apple", "grape", "banana", "orange"]

console.log(fruits);

Array

Dynamic array

We’ll move from one array to another array with double size

class DynamicArray {
  constructor() {
    this.capacity = 2;         // Initial size of internal storage
    this.length = 0;           // Number of actual elements
    this.data = new Array(this.capacity); // Underlying static array
  }

  // Add an element to the end
  push(element) {
    if (this.length === this.capacity) {
      this._resize();  // Double the capacity if full
    }
    this.data[this.length] = element;
    this.length++;
  }

  // Internal method to resize the array
  _resize() {
    this.capacity *= 2;
    const newData = new Array(this.capacity);

    for (let i = 0; i < this.length; i++) {
      newData[i] = this.data[i];
    }

    this.data = newData;
  }
}

 You may not need the extra slots that you asked for, and then that memory will be wasted. You aren’t using it, but no one else can use it either.

You may add more than 10 items to your task list and have to move anyway.

So it’s a good workaround, but it’s not a perfect solution. Linked lists solve this problem of adding items.

Sorted array : sorted faster at a price

Instead, we need to find the right place to put our new entry, where it won’t break the order, and then fix the array. (I’ll soon explain how.) Because of the way arrays work, this is not as easy as we might hope

class SortedArray {
  constructor(maxSize) {
    this._array = new Array(maxSize);
    this._size = 0;
    this._maxSize = maxSize;
  }

  insert(value) {
    if (this._size >= this._maxSize) {
      throw new Error(`The array is already full, maximum size: ${this._maxSize}`);
    }

    let i;
    // Find correct position by scanning from right to left
    for (i = this._size - 1; i >= 0; i--) {
      if (this._array[i] <= value) {
        // Found the insertion point
        this._array[i + 1] = value;
        this._size++;
        return;
      }
      // Shift element to the right
      this._array[i + 1] = this._array[i];
    }

    // Insert at beginning if we get here
    this._array[0] = value;
    this._size++;
  }

  getArray() {
    return this._array.slice(0, this._size); // Return only filled values
  }
}

What's Happening Internally:

• Starts from the end of the current sorted section

• Shifts values right until the right spot for value is found

• Inserts the value and increases size

• If no smaller value is found, inserts at position 0

Binary search in array

If your array is sorted, we have our advantage

function binarySearch(numbers, value) {
    let low = 0;
    let high = numbers.length - 1;

    while (low <= high) {
        const mid = Math.floor(low + (high - low) / 2);

        if (numbers[mid] === value) {
            return true;
        } else if (numbers[mid] > value) {
            high = mid - 1; // exclude mid
        } else {
            low = mid + 1;
        }
    }

    return false;
}

Insert into a sorted array

function insertBinary(arr,val) {
    let left = 0;
    let right = arr.length - 1;
    do {
        const mid = left + Math.floor((right-left)/2);
        if(arr[mid] < val) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    } while (left<=right)
    arr.splice(left,0,val);
    return arr;
}

Dynamic Array vs Linked-List

I understand now why array is 0(1) and array.shift() is 0(n) because the data in memory sits next to each-other, when you move one-piece you will have to the other pieces. For node data structure, data is not on a contigious memory, so when you move (delete or add) data it will not cost you 0(n)

Binary search

We have two ways to store data in memory

• In sequence (array)

• In random places (linked list)

• 

Linked List

Concept

It’s like a treasure hunt. You go to the first address, and it says, “The next item can be found at address 123.” So you go to address 123, and it says,“The next item can be found at address 847”

Predecessor and accessor

import java.util.LinkedList;

class Task {
    String name;
    public Task(String name) {
        this.name = name;
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        LinkedList<Task> taskQueue = new LinkedList<>();

        // Adding tasks
        taskQueue.addLast(new Task("Task 1"));
        taskQueue.addLast(new Task("Task 2"));
        taskQueue.addLast(new Task("Task 3"));

        // Processing tasks in real-time
        while (!taskQueue.isEmpty()) {
            Task current = taskQueue.removeFirst();
            System.out.println("Processing: " + current.name);
        }
    }
}

Disadvantge

1. These differences have consequences, both positive and negative.

2. On the positive side, as the nodes in a linked list don’t have to be allocated contiguously, we have more flexibility: we are not forced to allocate the whole list in advance, and we can add as many nodes as we want at any time, as long as there is enough memory to allocate a new node.

3. The negative consequence, however, is that since the addresses of the nodes are not predeter- mined, there is no formula to compute where a node will be given its index in the sequence of list elements. This means that, compared to arrays, we lose the ability to access any element by its index and are instead forced to read the linked list from its beginning, one node at a time, getting the address of the next node, and so on, until we get to the element we want to access.

Double Linked List

Twice as many links, twice as much fun?

• We can traverse a DLL in both directions, from its head to its tail, and from its tail to its head.

• If we have a link to a single node of the list, we can reach any other node in the list, both before and after it. We experienced how important this is when we discussed the delete method for SLLs.

• On the negative side, each node of a DLL takes up more space than the corresponding SLL variant. On large lists, the difference can affect your applications.

• Another negative consequence is that for each change we make to the list, we need to update two links—maintenance becomes more complicated and more expensive.

The important of retracing your steps

Abstract data types vs. data structures

🧠 As an Abstract Data Type:

You think about what operations are available:

• get(index) → get item at a specific index

• set(index, value) → update item at index

• Operations are fast (constant time)

You don’t care how it’s done—just that it works.

⚙️ As a Data Structure:

You care about how it works in memory:

• Array is a block of memory with fixed size

• Each cell holds one element of a specific type

• You access an element by computing its memory offset (base + index * size)

• You might implement it in C or JavaScript using native features

🧪 Real-World Example: Why Predictability Matters

Imagine you're processing incoming data packets from a network:

• They arrive in unpredictable order.

• You need to queue them quickly (insert at tail), and process oldest first (remove at head).

• You may be doing this thousands of times per second, and spikes in shift() cost would lead to dropped packets.

✅ Linked list = consistent performance
❌ Array = fast on average, but with costly spikes

StackOverview

Stack implementation

Problems with Dynamic Arrays

1. Memory Overhead:

   • When we resize, we allocate more memory than we immediately need (e.g., double the size), leading to wasted space.

   • On average, we use O(n) extra memory just to accommodate growth.

2. Fragmentation & Allocation Failure:

   • Since arrays are stored in contiguous memory, it gets harder to find large chunks of free memory as the array grows.

   • If memory allocation fails, the program crashes.

3. Worst-case Time Complexity:

   • Push (adding to the stack) is normally O(1).

   • But during resizing, a push becomes O(n) because we must copy n elements.

   • Similarly, popping may involve shrinking, which can also be O(n) in rare cases.

Linked-list implementation for

In addition, linked lists have fewer constraints on the allocation of the memory they require: a new node can be allocated anywhere (not necessarily next to or near the rest of the nodes). This makes it easier to allocate larger stacks compared to the array implementations

Use-case

• Browser History

• Undo/redo

• Balanced Parenthesis

Key to remember implementation for browser history and undo/redo feature

🧠 "Resetting the future because you’ve changed the present"

🔁 In a browser:

1. Visit: A → B → C

2. Go back to B

3. Visit new page D

Now the future (C) is gone, and history becomes:

cssCopyEditA → B → D

---

📝 In an editor (Undo/Redo):

1. Type: "Hello"

2. Undo → "Hell"

3. Type: "Help"

Now the redo (to "Hello") is lost. You’ve created a new timeline.

---

🧪 In Git (branches):

You checkout an old commit and make new changes → this creates a new branch.

🔧 In code:

// go back in browser

this.stack = this.stack.slice(0,currentIdx+1);

// Undo and redo
jsCopyEditthis.redoStack = []; // ✨ clears the future

You’re discarding invalid futures when the user changes the current state. That’s why the stack metaphor works so well — it’s a time machine with a single linear path unless you start branching.

Queue

Overview

Use-case

• Message system

• Web server (the web server may simply use a queue to store the incoming requests before processing them at its own pace)

• Operating systems

• Bread-first-search agg

Tree

Linked lists are based on the idea that each node has a single successor and a single predecessor—except for the head of the list, which has no predecessor, and the tail of the list, which has no successor

A generic tree is a composite data structure that con- sists of nodes connected by links. Each node con- tains a value and a variable number of links to other nodes, from zero to some number k

Normal tree

Use-case

Hashmap

Put a hash function and an array together,
and you get a data structure called a hash table.

A new way of indexing

Arrays don’t guarantee great performance for dictionary operations because, with key- based indexing, we lose their main advantage: constant-time access by index

The cost of indexing

Hash functions

Understanding what makes a good hash function is somewhat more complicated. In theory, a desirable property of hash functions is uniformity: each element should be equally likely to be hashed to any of the m slots in the hash table, regardless of where any other element has been or will be hashed. Unfortunately, uniformity is hard to obtain (elements are often not drawn independently) and hard to verify (because we usually don’t know the distribution of the keys).

Conflict resolution

When I introduced hash tables, I told you that the capacity of the array we are using is less than the number of possible keys, and therefore, we can no longer use keys as indexes because a key could be larger than the largest index of the hash table.

There is another consequence of this size difference that I have glossed over—the hash function will map at least two keys to the same index. This follows from the so-called pigeonhole principle.

If we have five pigeons and four holes, there will be at least one hole with two pigeons. There might also be more than one hole with two pigeons, or holes with more than two pigeons.

🔗 Chaining (linked list) in hash maps – how it works

class UserDirectory {
    constructor() {
        this.bucket = new Array(26).fill(null).map(()=>new LinkedList());
    }
    _hash(name) {
        const idx = name.toLowerCase().charCodeAt(0) - 'a'.charCodeAt(0)
        return idx >= 0 && idx <=26 ? idx : -1;
    }
    addUser(name) {
        const idx = this._hash(name);
        if(idx === -1) {
            console.warn("Invalid name",name);
            return;
        }
        this.bucket[idx].insert(name);
    }
    findUser(name) {
        const idx = this._hash(name);
        if(idx === -1) {
            console.warn("Invalid name",name);
            return;
        }
        return this.bucket[idx].find(name);
    }
    printBucket(name) {
        const index = this._hash(name);
        if (index === -1) {
            console.warn("Invalid name",name);
            return;
        }
        console.log(`Bucket for '${name.toUpperCase()}':`);
        this.bucket[index].print();
    }
    autocomplete(name) {
        const idx = this._hash(name);
        if (idx === -1) {
            console.warn("Invalid name", name);
            return;
        }
        const list = this.bucket[idx];
        const autoCompletionName = [];
        let curNode = list.head;
        while (curNode) {
            if (curNode.data.toLowerCase().startsWith(name.toLowerCase())) {
                autoCompletionName.push(curNode.data);
            }
            curNode = curNode.next;
        }
        return autoCompletionName;

    }
}

const directory = new UserDirectory();
directory.addUser("Adit B");
directory.addUser("Alice");
directory.addUser("Alina");
directory.addUser("Zoe");
directory.addUser("Zara");

console.log(directory.autocomplete("Al")); // ["Alice", "Alina"]
console.log(directory.autocomplete("Z"));  // ["Zoe", "Zara"]
console.log(directory.autocomplete("A"));  // ["Adit B", "Alice", "Alina"]

• Use-case

• Using hashtable for lookup (your phone is a hashtable, DNS resolution)

• Prevent duplicate entries (if you store it in an array, go and find duplicate items → 0(n)

• Use it as a cache (useMemo, website caching)

Performance

Hashtable are really fast in all 3 (search, insert and delete)

But you need to avoid collisions. To avoid collisions, you need

• A low load factor

• A good hash function

Tree

Tree is a version of linked list (random memories)

A generic tree is a composite data structure that con- sists of nodes connected by links. Each node con- tains a value and a variable number of links to other nodes, from zero to some number k

Why Tree for the DOM?

• HTML is inherently hierarchical

• Tree structure allows for efficient traversal, updates, and rendering

• No cycles makes logic simpler and safer

• Subtrees = natural componentization (e.g., React components)

Overview

And they have one important advantage over sorted arrays: insertion and deletion can be faster on a BST. What’s the catch, and what’s the tradeoff? Like linked lists, trees require more memory to implement, and their code is more complex, espe- cially if we want to guarantee that these operations are faster than on arrays.

Search tree

Implementation ideas

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

class BinaryTreeSearch {
  constructor(value) {
    /** Starting point of searching, always start with root
        that's why 0(logn) not 0(1) 
    **/
    this.root = new BinaryTreeNode(value);
  }
  insert(value) {
    const newNode = new BinaryTreeNode(value); // create a root
    if (!this.root) { // validations
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    /** I see a pattern,there is always a starter function to pass value to
    recursion function ( a job of starter function is to validate value in
    params, etc
    The recursion function will then call it again with dynamic value
    in this case currentNode **/
    }
  }
  _insertNode(currentNode, newNode) {
    if (currentNode.value > newNode.value) {
      if (currentNode.left === null) {
        currentNode.left = newNode;
      } else {
        this._insertNode(currentNode.left, newNode);
      }
    } else {
      if (currentNode.right === null) {
        currentNode.right = newNode;
      } else {
        this._insertNode(currentNode.right, newNode);
      }
    }
   containNode(value) {} // starter function call tranverseNode oc with validations
   tranverseNode(currentNode,value) {} // DFS  }

Worst-case scenerio for binary tree

If your root is not ideal, eventually you’re a linked list and can cause 0(n) for a search

Solution to this problem ?

Red-black-tree ( balanced-search-tree)

Each node has an extra bit for color: red or black, and the tree follows these rules:

1. Every node is either red or black.

2. The root is always black.

3. All leaves (NIL or null pointers) are considered black.

4. If a node is red, then both its children must be black. (No two red nodes in a row)

5. Every path from a node to its descendant NIL nodes must have the same number of black nodes (called black-height).

Decision Tree

               Is it raining?
               /           \
            Yes             No
          /     \
Do you have    Stay
an umbrella?   inside
  /    \
Yes   No
|      |
Go   Stay
outside inside

DFS with tree

// Add to an array to keep track of the node in DFS
const walk = (binaryTree, pathNumbers) => {
    if(binaryTree.left instanceof BinaryTree) {
        walk(binaryTree,pathNumbers); 
    }
    /** Back-tracking to collect value when there're no more path to walk **/
    pathNumbers.push(binaryTree.value);
    if(binaryTree.right instanceof BinaryTree) {
       walk(binaryTree,pathNumbers);
    }
};

// left node right (starter function)
const inOrderSearch = (binaryTree) => {
  const arr = [];
  if (!binaryTree.root) {
    console.log("Empty tree");
  } else {
    walk(binaryTree.root, arr);
    console.log(arr);
  }
};

Backtracking concept

Ideas

DFS for FE developers

• getElementByTagName

• deepEqual lodash

• Binary tree tranversal ( Pre-order, in-order, post-order)

• renderDOM reactJS (Pre-order)

function render(element, container) {
  const dom =
    element.type === "TEXT_ELEMENT"
      ? document.createTextNode("")
      : document.createElement(element.type);
  const isProperty = (key) => key !== children;
  /**
   * Assign key to the DOM
   */
  Object.keys(element.props)
    .filter(isProperty)
    .forEach((key) => {
      dom[key] = element.props[key];
    });
  /**
   * We recursively do the same for each-child
   */
  element.props.children.forEach((child) => {
    render(child, dom);
  });
  container.appendChild(dom);
}

BFS (breadth-first-search)

Breadth-First Search (BFS) is a way of exploring a graph or tree level by level, moving outward from the starting point in all possible directions before going deeper. Imagine BFS as if you’re exploring layers of a structure, like peeling an onion.

Imagine a Tree or Network of Friends

Let's say you have a tree or a social network where each person (node) is connected to others (friends or neighbors). BFS is like saying, “I want to meet all of my immediate friends first, then all of their friends, and so on.”

How BFS Works

1. Start at the Root: Begin at the starting node (root) and mark it as visited.

2. Explore Neighbors First: Visit all the direct neighbors (or children) of this starting node. Once you've seen them all, move to their neighbors.

3. Go Level by Level: Instead of diving deep down one path (like DFS), BFS explores all nodes at the current "level" before moving down to the next level. Think of it like spreading outward in circles.

4. Use a Queue: To keep track of the order to explore nodes, BFS uses a queue (first-in, first-out). This allows you to explore in layers: you add new nodes to the end of the queue and process nodes from the front of the queue.

Don’t limit your thinking of datastructure

In this case, it’s a tree node with { value:number, left?: NodeTree , right?: NodeTree }

Other’s cases

const graph = {
   fred: ["joe"], // this is a form of connections instead of just left and right
   joe: ["mary"],
   mary: ["fred", "bill"],
};

We need to know where we should start looking in a graph

• It could be a name (in hashmap)

• It could be a number (in matrix)

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (visited.has(node)) continue;

    console.log(node);
    visited.add(node);

    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
      }
    }
  }
}

The role of queue in BFS

First-In, First-Out (FIFO) Order: A queue is a data structure where the first element added is the first one to be removed (First-In, First-Out). This is perfect for BFS because BFS needs to explore nodes in the order they are discovered, one level at a time

Ideas

Compare two binary tree

Idea

Heap (a list of items in a priority order)

Overview

They are dynamic list, allowing insertions and retrievals to be intermixed. We need to be able to add and remove items from our prioritized task list

Finding the Highest or Lowest Priority Element

• Heap: In a heap, the largest (or smallest) element is always at the root (top) of the tree, so accessing it takes only O(1) time.

• Unsorted Array: If we store elements in an unsorted array, we would need to scan the entire array to find the highest or lowest priority element. This takes O(n) time, which is slow for large arrays.

• Sorted Array: If we keep the array sorted, then finding the highest or lowest element takes O(1) time, since it will be at one end of the array. However, maintaining this sorted order requires more work during insertion and deletion, as explained next.

  

  Best of both world, we want to limit the insert operation from 0(n) → 0(log(n))💡

And, in fact, property 1 of a binary heap is that each node of the tree can have at most two children.

Special thing about the heap

From the foundational properties of heaps, there follow some other very interesting properties. From property 3, we can infer that all paths from the root to any leaf of the tree are sorted.

Insert scenerio

• 💡

  Note if 200 is > 80, then probably it can be large > 125, and can potentially be the largest

Delete scenerio

Real-world example

The author uses a real-world version of this sorted-list approach to

organize his refrigerator, storing items front-to-back in order of increasing

expiration date. The closest item is always the highest priority, the one that

will expire the soonest. Retrieving the correct item is easy—just grab what-

ever is in front. This scheme is particularly beneficial when storing milk

or cream for morning coffee: no one wants to spend the first few bleary

moments of the morning reading expiration dates. However, inserting new

items behind old ones can take time and require an annoying amount of shifting

Heap-up

Manage binary tree in the state of array

Implementation idea

Passing a function to extract element priority

By using elementPriority and helper methods like hasLowerPriority, you separate the logic of comparison from the actual algorithm. This gives you:

• ✅ Flexibility (you can heapify anything: tasks, users, scores, etc.)

• ✅ Reusability (no rewriting comparison logic)

• ✅ Clean, readable code (heap logic doesn’t care what you're sorting)

Each element is a pair with the bug description and its priority. In the tree representa- tion, most of the descriptions are omitted due to space limitations. For the same reason, going forward, I’ll only display the descriptions in the array representation.

Now, suppose we want to add a new element. Like we said, we assume that the array has been allocated with enough space to append new elements, and we only show the portion of the array that is actually populated, leaving out the empty cells.

We want to add the tuple ("Broken Login", 9). First, we add the new element to the end of the array. But then we notice that the new element breaks the third property of heaps because its priority is higher than its parent!

Let’s insert the item in the last position of the array and walk back up(heapifyUp) the idx

Top

• Full ordering (like that in a sorted array or binary search tree) requires every element to be compared to every other element, which would be much less efficient for certain operations, such as insertion and deletion. The heap’s weak ordering makes it more efficient for specific use cases like priority queues, where only the minimum or maximum element is needed at any given time.

Build a heap from an array

   _heapify(elements) {
        this._elements = [...elements];
        for (let i = Math.floor(this._elements.length / 2) - 1; i >= 0; i--) {
            this._siftDown(i);
        }
    }

Why?

Array: [10, 20, 30, 40, 50, 60, 70]
Length n = 7

• Math.floor(7 / 2) = 3

• So: i = 2 is the last non-leaf node

• Indices 3, 4, 5, 6 are leaves (they have no children)

• 

Example of using Heap

1. 🔥 News Feeds (Social Media)

Goal: Show the top k trending posts or most liked tweets.

• Posts are added constantly (huge array).

• You want to show only the top 10 with the most likes.

• This function can track the top 10 posts efficiently without sorting the entire feed.

---

2. 🎧 Music Streaming Services

Goal: Display top 100 most played songs.

• Songs are streamed millions of times a day.

• Rather than re-sorting the whole catalog, just maintain a min-heap of the top 100 songs by play count.

---

3. 🕵️ Search Engines

Goal: Show the k most relevant results.

• You might have 10 million results for a query.

• You only need to show the top 20.

• Heap logic helps the backend pick the best k matches fast, without scanning and sorting all results.

---

4. 📈 Stock Trading Platforms

Goal: Display the k biggest stock gainers of the day.

• You track thousands of stocks.

• Only want to show top 5 performing.

• This function keeps those in real time.

⏱️ Why Not Just Sort?

// O(n log n)
posts.sort((a, b) => b.likes - a.likes);
return posts.slice(0, 10);

❌ Expensive: Sorting the whole list is O(n log n) every time new data comes in.
❌ Wasteful: You're sorting everything, even posts that will never make it into the top 10.

The heap-based solution lets you do it in O(n log k) instead of O(n log n) — much faster when k is small compared to n.

🧪 Real-World Analogy

Think of the heap as a VIP list with 10 seats:

• A new post shows up.

• If it has more likes than the current least liked VIP, it kicks them out.

• Otherwise, it's ignored.

• You never waste time ranking non-VIPs.

class MinHeap {
    constructor(k) {
        this.data = [];
        this.k = k;
    }
    parent(idx) {
        return Math.floor((idx-1)/2);
    }
    leftChild(idx) {
        return (idx*2) + 1;
    }
    rightChild(idx) {
        return (idx*2) + 2;
    }
    swap(i,j) {
        [this.data[i],this.data[j]] = [this.data[j],this.data[i]];
    }
    heapifyUp(idx) {
        const parentIdx = this.parent(idx);
        if(idx > 0 && this.data[idx].likes < this.data[parentIdx].likes) {
            this.swap(idx,parentIdx);
            this.heapifyUp(parentIdx);
        }
    }
    heapifyDown(idx) {
        const leftIdx = this.leftChild(idx);
        const rightIdx = this.rightChild(idx);
        let smallestIdx = idx;
        if(leftIdx < this.data.length && this.data[leftIdx].likes < this.data[smallestIdx].likes) {
            smallestIdx = leftIdx;
        }
        if(rightIdx < this.data.length && this.data[rightIdx].likes < this.data[smallestIdx].likes) {
            smallestIdx = rightIdx;
        }
        if(smallestIdx !== idx) {
            this.swap(idx,smallestIdx);
            this.heapifyDown(smallestIdx);
        }
    }
    insert(post) {
        if (this.data.length < this.k) {
            this.data.push(post);
            this.heapifyUp(this.data.length-1);
        } else {
            if (this.data[0].likes < post.likes) {
                this.data[0] = post;
                this.heapifyDown(0);
            }
        }
    }
    getTopPosts() {
            return [...this.data].sort((a, b) => b.likes - a.likes);
    }

}

const trending = new MinHeap(10);

// Simulate incoming posts
const posts = [
    { id: "p1", likes: 80 },
    { id: "p2", likes: 150 },
    { id: "p3", likes: 120 },
    { id: "p4", likes: 90 },
    { id: "p5", likes: 300 },
    { id: "p6", likes: 60 },
    { id: "p7", likes: 130 },
    { id: "p8", likes: 500 },
    { id: "p9", likes: 240 },
    { id: "p10", likes: 200 },
    { id: "p11", likes: 50 },
    { id: "p12", likes: 400 },
];

for (const post of posts) {
    trending.insert(post);
}
console.log(trending.getTopPosts());

Graph

Overview

A graph is a way to organize and represent data that involves connections between items. Think of it like a network where different points (called nodes or vertices) are linked by lines (called edges). These points can represent anything—like people, cities, or web pages—and the lines show how these points are related.

How We Represent Graphs

There are two common ways to represent graphs in a computer:

1. Adjacency Matrix: A table where each cell shows whether there is a connection between two nodes. This is like a large grid that says, "Yes, there is a connection" or "No, there isn't" between each pair of nodes. Array data structure

   

   Adjacency matrices can be faster than adjacency lists when we need to check whether there is an edge between two vertices: it takes only a single lookup in a 2D array, which is O(1). Thus, adjacency matrices give us an advantage for algorithms that require inten- sive connectivity checking.

   In contrast, an adjacency matrix requires memory proportional to the square of the number of vertices (that is, the maximum number of edges in a simple graph), even if the graph is sparse. Therefore, they are rarely used, and usually only when we are sure that we are dealing with dense graphs. Also, for this reason, we won’t dive into the code for the adjacency matrix implementation

// Linked list node
class ListNode {
    constructor(value, next = null) {
        this.value = value;
        this.next = next;
    }
}

// Custom singly linked list
class SinglyLinkedList {
    constructor() {
        this.head = null;
    }

    // Insert a node at the front
    insertInFront(value) {
        const newNode = new ListNode(value, this.head);
        this.head = newNode;
    }

    // Search for a node with a given value
    search(value) {
        let current = this.head;
        while (current !== null) {
            if (current.value === value) return current;
            current = current.next;
        }
        return null;
    }

    // Convert the list to an array (for display/debug)
    toArray() {
        const result = [];
        let current = this.head;
        while (current !== null) {
            result.push(current.value);
            current = current.next;
        }
        return result;
    }
}

// Vertex class — internal use only
class Vertex {
    constructor(key) {
        this.id = key;
        this._adjList = new SinglyLinkedList();
    }

    // Check if an edge already exists
    hasEdgeTo(destinationVertexId) {
        return this._adjList.search(destinationVertexId) !== null;
    }

    // Add an edge if it doesn't already exist
    addEdgeTo(destinationVertexId) {
        if (this.hasEdgeTo(destinationVertexId)) {
            throw new Error(`Edge already exists: ${this.id} -> ${destinationVertexId}`);
        }
        this._adjList.insertInFront(destinationVertexId);
    }

    // Get neighbors as array
    getNeighbors() {
        return this._adjList.toArray();
    }
}

// Graph class — public interface
class Graph {
    constructor() {
        this._adj = {}; // Map from key to Vertex
    }

    // Internal: Get or create Vertex instance
    _getVertex(key) {
        if (!(key in this._adj)) {
            this._adj[key] = new Vertex(key);
        }
        return this._adj[key];
    }

    // Public: Add a vertex if it doesn’t exist
    addVertex(key) {
        this._getVertex(key);
    }

    // Public: Add an edge from source to destination
    addEdge(sourceKey, destKey) {
        const sourceVertex = this._getVertex(sourceKey);
        this._getVertex(destKey); // ensure destination exists
        sourceVertex.addEdgeTo(destKey);
    }

    // Check if an edge exists
    hasEdge(sourceKey, destKey) {
        const sourceVertex = this._adj[sourceKey];
        return sourceVertex ? sourceVertex.hasEdgeTo(destKey) : false;
    }

    // Get list of neighbors for a given vertex
    getAdjacencyList(key) {
        const vertex = this._adj[key];
        return vertex ? vertex.getNeighbors() : [];
    }

    // Print the entire graph
    printGraph() {
        for (const key in this._adj) {
            const neighbors = this._adj[key].getNeighbors().join(', ');
            console.log(`${key} -> ${neighbors}`);
        }
    }
}

const graph = new Graph();

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");
graph.addVertex("D");

console.log(graph.hasEdge("A", "C")); // true
console.log(graph.getAdjacencyList("A")); // ['C', 'B']
console.log(graph.getAdjacencyList("D")); // []

graph.printGraph();
// Output:
// A -> C, B
// B -> C
// C ->
// D ->

1. Adjacency List: A list for each node that shows which other nodes it’s connected to. This list is usually more efficient for large graphs with fewer connections. Linked List data structure

   

   ✅ Pros:

   • More space-efficient (O(V + E)) — great for sparse graphs → less memories, slower to search

   • Easier to iterate through neighbors

❌ Cons:

• Slower to check if edge exists (O(n) in worst case) → loop from an array

2. Hash map can be used as graph

Adjacent list
const graph = [
  [1, 2],    // Node 0 is connected to Node 1 and Node 2
  [0, 3],    // Node 1 is connected to Node 0 and Node 3
  [0, 3],    // Node 2 is connected to Node 0 and Node 3
  [1, 2]     // Node 3 is connected to Node 1 and Node 2
];


Adjacent Matrix
const graph = [
  [0, 1, 1, 0], // Node 0 is connected to Node 1 and Node 2
  [1, 0, 0, 1], // Node 1 is connected to Node 0 and Node 3
  [1, 0, 0, 1], // Node 2 is connected to Node 0 and Node 3
  [0, 1, 1, 0]  // Node 3 is connected to Node 1 and Node 2
];

Hashmap
const graph = {
  0: [1, 2],  // Node 0 is connected to Node 1 and Node 2 (this can be name)
  1: [0, 3],  // Node 1 is connected to Node 0 and Node 3
  2: [0, 3],  // Node 2 is connected to Node 0 and Node 3
  3: [1, 2]   // Node 3 is connected to Node 1 and Node 2
};

Already walked concept

• Graphs often contain cycles, unlike tree structures where each node (except the root) has only one parent. In a graph, nodes can have multiple edges leading back to themselves (self-loops) or cycles through other nodes.

• Without marking nodes as "visited," traversal algorithms like BFS and DFS would re-visit nodes endlessly in cyclic graphs, resulting in an infinite loop. The alreadyWalked set prevents this by ensuring each node is processed only once.

Back-tracking

1. DFS Backtracking (pop):

   • In DFS, when the path being explored doesn't lead to the target, we remove the last node added (path.pop()).

   • It actively undoes steps in the current path and tries alternatives.

2. BFS Tracking (previous):

   • BFS doesn't backtrack during the traversal. Instead, it tracks the path in the previous array and constructs it later after reaching the target.

   • The queue ensures all paths are explored level by level, making backtracking unnecessary.

BFS on Adjacent Matrix

Purpose of the previous Array

• Tracks the Path: It keeps track of which node led to the current node. By doing so, it allows us to trace back from the target node to the source node after BFS has finished.

• Path Reconstruction: Once the target is found, the previous array is used to reconstruct the shortest path by following the breadcrumbs (links from each node to its predecessor).

Parent → children relationship in prev structure

[1] = 0;

[2] = 0;

[3] = 0; // All of 1,2,3 has a parent node 0

[4] = 1

[5] = 1

[6] = 1

console.log(bfs(graph, 0, 4));
// [ 0, 1, 2, 3, 4 ]

More complex scenes

DFS on the Adjacent-List

Represent graph in Adjacent-List

Backtracking

Dijkstra

LRU (Least Recent Used)

Ideas

The LRU data structure refers to the Least Recently Used cache — a data structure and algorithm used to manage limited-size storage (like a cache) by discarding the least recently used items first when space is needed.

Common LRU Implementation

An efficient LRU cache typically uses:

1. Hash map (dictionary) → for O(1) lookups.

2. Doubly linked list → to keep track of usage order.

How they work together:

• The hash map stores keys and points to nodes in the linked list.

• The linked list keeps the order: head = most recently used, tail = least recently used.

• On access or update, you move the node to the head.

• When adding a new item and the cache is full, you remove the tail (least recently used).

Example Usage

Real-life examples:

• CPU caches

• Browser caches (keeping recently visited pages)

• Database query caches

• Image or file caching in apps

Implementation

In your LRUCache implementation, the tail is a dummy node, and its position never changes. You do not insert new elements after the tail — you always insert before it, meaning new elements go between the head and the first real node, not at the tail.

HEAD <-> [B:2] <-> [A:1] <-> TAIL

class Node {
    constructor(key,value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map();
        this.head = new Node(null,null);
        this.tail = new Node(null,null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    _insertAtFront(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }
    _remove(node) {
        // garbage collection
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    get(key) {
        if(!this.map.get(key)) return -1;
        const node = this.map.get(key);
        this._remove(node);
        this._insertAtFront(node);
        return node.value;
    }
    put(key,value) {
        if(this.map.has(key)) {
            const node = this.map.get(key);
            node.value = value;
            this._remove(node);
            this._insertAtFront(node);
        } else {
            if(this.map.size >= this.capacity) {
                const lru = this.tail.prev;
                this._remove(lru);
                this.map.delete(lru.key);
            }
            const newNode = new Node(key,value);
            this._insertAtFront(newNode);
            this.map.set(key,newNode);
        }
    }
    getList() {
        const arr = [];
        let curNode = this.head.next; // Skip dummy head
        while (curNode !== this.tail) { // Stop before dummy tail
            arr.push({ key: curNode.key, value: curNode.value });
            curNode=curNode.next;
        }
        return arr;
    }
}

const cache = new LRUCache(3);

cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
//c b a
console.log(cache.get("a")); // 1 (a becomes most recently used)
// a c b
cache.put("d", 4); // evicts "b" (least recently used)
// d a c
console.log(cache.getList());
// [
//  { key: 'd', value: 4 },
//  { key: 'a', value: 1 },
//  { key: 'c', value: 3 }
// ]

Set

This pattern — hash map + doubly linked list — is also what powers other performant data structures like:

• LRU Cache (for fast eviction of least recently used items)

• OrderedSet / OrderedMap

• React's internal fiber tree uses similar pointer-based structures for reconciliation

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

class Set {
    constructor() {
        this.head = new Node(null);
        this.tail = new Node(null);
        this.map = new Map();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // 0(1)
    add(value) {
        if(this.map.has(value)) return; // return in case of duplicated
        const node = new Node(value);
        this.tail.prev.next = node;
        node.prev = this.tail.prev;
        this.tail.prev = node;
        node.next = this.tail;
        this.map.set(value,node);
    }
    // 0(1)
    has(value) {
        return this.map.has(value);
    }
    _remove(node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
    }
    // 0(1)
    delete(value) {
        if(!this.map.has(value)) return false;
        const node = this.map.get(value);
        this._remove(node);
        this.map.delete(value);
        return true;
    }

   *[Symbol.iterator]() {
        let curNode = this.head.next;
        while(curNode !== this.tail) {
            yield curNode.value;
            curNode = curNode.next;
        }
   }
}

const mySet = new Set();

mySet.add("apple");
mySet.add("banana");
mySet.add("cherry");

console.log(mySet.has("banana")); // true
console.log(mySet.has("grape"));  // false

mySet.delete("banana");

console.log(mySet.has("banana")); // false

// Iterate using for...of
for (const value of mySet) {
    console.log(value);
}
// Output:
// apple
// cherry

// Spread into array
console.log([...mySet]); // ["apple", "cherry"]

Trie

A Trie is a tree-based data structure used to efficiently store and retrieve strings, especially for:

• Auto-complete

• Spell checking

• Prefix search

• Dictionary implementation

(root)
  └─ a
      └─ p
          └─ p
              └─ l
                  └─ e (isEndOfWord = true)

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false;
    }
}

  "children": {
            "j": {
                "children": {
                    "o": {
                        "children": {
                            "h": {
                                "children": {
                                    "n": {
                                        "children": {},
                                        "isEndOfWord": true,
                                        "count": 0
                                    }
                                },
}

a) Prefix Sharing (Space Optimization)

Words like "apple", "app", and "april" share the "ap" prefix — stored only once, not duplicated like in an array of strings.

a
└── p
    ├── p*     (end of "app")
    │   └── l
    │       └── e*  (end of "apple")
    └── r
        └── i
            └── l*  (end of "april")

b) Fast Search Time

• Insert/Search/StartsWith take O(L) time where L = length of the word or prefix.

• No need to loop through all words like with arrays or sets.

Example:

• trie.startsWith("ap") finds the prefix in 2 steps, regardless of how many words are in the Trie.

c) Auto-completion

const allWords = ["apple", "banana", "car", "cat", "dog", ... 999,995 more];

const result = [];
for (let word of allWords) {
  if (word.startsWith("ca")) {
    result.push(word);
  }
}

Why This Checks All 1M Strings

Because there’s no structure or index helping you jump to relevant words.

This approach:

• Looks at each word one by one

• Calls startsWith("ca") on every string => 0(n)

• Even if only 100 words start with "ca", it still checks all 1,000,000

That’s O(N × P) time:

• N = number of words (1 million)

• P = length of prefix ("ca" = 2)

👉 You're doing 1 million comparisons.

With Trie(DFS’s approach)

    autoComplete(prefix) {
        const results = [];
        // filter first and then DFS
        const node = this._traverse(prefix);
        if (!node) return results;

        function dfs(node, path) {
            if (node.isEndOfWord) {
                results.push(path);
            }
            for (let char in node.children) {
                dfs(node.children[char], path + char);
            }
        }

        dfs(node, prefix);
        return results;
    }

Even with 1 million words**, if only 100 start with ** "ca", it explores just those 100 — skipping the rest entirely.

That’s O(P + M) time:

• P = length of prefix

• M = number of matches

Compare string vs array

const contacts = ["john", "jane", "jordan", "joanna", "jim", "jack", "alice"];

function autoCompleteArray(prefix) {
    const result = [];
    for (const name of contacts) {
        if (name.startsWith(prefix)) {
            result.push(name);
        }
    }
    return result;
}

console.log(autoCompleteArray("jo")); // ["john", "jordan", "joanna"]

// Setup
const contactTrie = new Trie();
const contacts = ["john", "jane", "jordan", "joanna", "jim", "jack", "alice"];
for (const contact of contacts) {
    contactTrie.insert(contact);
}

console.log(contactTrie.autoComplete("jo")); // ["john", "jordan", "joanna"]