Data structure in JS

I've covered the basic data structure that has been provided by JS in this blog. You can find more about it here. In this blog, I'll focus on DS, that we have to write from scratch that JS doesn't give it to us

Array

Implement flat without recursion

Array vs Linked-List

Binary search

We have two ways to store data in memory

• In sequence (array)

• In random places (linked list)

• 

Linked List

API

Concept

Advantages

Stack

Overview

Valid parentheses problem?

Queue

Overview

Tree

Normal tree

Use-case

Binary tree

Tree is a version of linked list (random memories)

Overview

Search tree

Implementation ideas

DFS (depth-first-search)

Overview

Depth-First Search (DFS) is a way of exploring a graph or a tree by going as deep as possible along each branch before backtracking.

1. Start at a Node: You pick a starting point (often called the "root" in trees) and visit it. In a maze, this would be like starting at the entrance.

2. Explore as Deep as Possible: From that starting point, choose one of the possible directions and go down it. Keep moving forward until you can’t go any further — either you reach a dead end or a point you've already visited.

3. Backtrack: If you hit a dead end, backtrack to the last decision point and choose a different path. Keep track of where you've already been, so you don’t repeat work.

   💡

   In DFS, we explore the path until we hit dead-end and back-track and try other options

4. Repeat Until Complete: Continue this process of going deep, hitting a dead end, backtracking, and trying a new path until you've explored every possible path in the maze.

Ideas

DFS for FE developers

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.

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.

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

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

• 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.

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

2. 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

3. 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
  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
};

First degrees of Connection

First-degree and second-degree connections refer to the levels of relationships between nodes (or people, in a social network).

First-Degree Connections

• First-degree connections (also called direct connections or friends) are the nodes directly connected to a given node by an edge.

• For example, in a social network, if Alice is connected to Bob, Charlie, and Diane, then Bob, Charlie, and Diane are Alice’s first-degree connections (or friends).

Second-Degree Connections

• Second-degree connections are nodes that are connected to the first-degree connections, but not directly connected to the original node.

• Using the example above, if Bob is connected to Eve and Frank, then Eve and Frank are second-degree connections of Alice (friends of friends). Alice can reach them through Bob but doesn’t have a direct connection to them.

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

Dijkstra

LRU (Least Recent Used)

Ideas

Implementation