Data Structures and Associated Algorithms
Introductions
We are going to cover some of the data structures which are commonly used in algorithms, and which are not the super common ones like arrays, strings, and objects. We will also cover some of the algorithms that are associated with these data structures.
Linked lists
Definition: A series of nodes, where each node contains data and a reference to the next node.
Key Operations: Insertion/Deletion (O(1)), Access (O(n))
Use Cases: Implementing dynamic data structures, like stacks and queues.
Code Sample:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Insert at the beginning
insertAtBeginning(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
// Insert at the end
insertAtEnd(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// Delete by value
deleteByValue(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
// Traverse and print the list
printList() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
// Usage example
const list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtEnd(30);
list.printList(); // Output: 20 10 30
list.deleteByValue(10);
list.printList(); // Output: 20 30
Stacks and Queues
Stacks and queues are abstract data types built on arrays or linked lists, used for handling collections in a specific order.
Stacks
Definition: A collection following Last-In-First-Out (LIFO) principle.
The simplest way to implement a stack is using an array, add to it with push() and remove from it with pop().
Queues
Definition: A collection following First-In-First-Out (FIFO) principle.
Key Operations: Enqueue (O(1)), Dequeue (O(1))
Use Cases: Task scheduling, breadth-first search.
The simplest way to implement a queue is an array, add to it with push() and remove from it with shift().
Binary Trees, Binary Search Trees (BST)
Binary trees are hierarchical structures, with each node having at most two children. Binary search trees (BSTs) are a specialized form where each node's left subtree contains values less than the node, and the right subtree contains values greater.
Binary Trees
Definition: A tree where each node has up to two children.
Key Operations: Traversal (O(n)), Insertion/Deletion (O(log n) in balanced trees)
Use Cases: Hierarchical data representation, expression parsing.
Code Sample:
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
// Insert a node in the binary tree
insert(data) {
const newNode = new Node(data);
if (!this.root) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.data < node.data) {
if (!node.left) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (!node.right) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
// In-order traversal (Left, Root, Right)
inOrderTraversal(node) {
if (node) {
this.inOrderTraversal(node.left);
console.log(node.data);
this.inOrderTraversal(node.right);
}
}
// Pre-order traversal (Root, Left, Right)
preOrderTraversal(node) {
if (node) {
console.log(node.data);
this.preOrderTraversal(node.left);
this.preOrderTraversal(node.right);
}
}
// Post-order traversal (Left, Right, Root)
postOrderTraversal(node) {
if (node) {
this.postOrderTraversal(node.left);
this.postOrderTraversal(node.right);
console.log(node.data);
}
}
// Find a node
find(data) {
return this.findNode(this.root, data);
}
findNode(node, data) {
if (!node) {
return null;
}
if (data < node.data) {
return this.findNode(node.left, data);
} else if (data > node.data) {
return this.findNode(node.right, data);
} else {
return node;
}
}
}
// Usage example
const binaryTree = new BinaryTree();
binaryTree.insert(15);
binaryTree.insert(25);
binaryTree.insert(10);
binaryTree.insert(7);
binaryTree.insert(22);
binaryTree.insert(17);
binaryTree.insert(13);
binaryTree.insert(5);
binaryTree.insert(9);
binaryTree.insert(27);
console.log('In-order Traversal:');
binaryTree.inOrderTraversal(binaryTree.root); // Output: 5 7 9 10 13 15 17 22 25 27
console.log('Pre-order Traversal:');
binaryTree.preOrderTraversal(binaryTree.root); // Output: 15 10 7 5 9 13 25 22 17 27
console.log('Post-order Traversal:');
binaryTree.postOrderTraversal(binaryTree.root); // Output: 5 9 7 13 10 17 22 27 25 15
console.log('Find Node with data 22:');
const foundNode = binaryTree.find(22);
if (foundNode) {
console.log('Node found:', foundNode.data); // Output: Node found: 22
} else {
console.log('Node not found');
}
Binary Search Trees (BST)
Definition: A binary tree with ordered nodes.
Key Operations: Search (O(log n)), Insertion/Deletion (O(log n))
Use Cases: Efficient searching and sorting.
Code Sample:
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// Insert a node in the BST
insert(data) {
const newNode = new Node(data);
if (!this.root) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.data < node.data) {
if (!node.left) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (!node.right) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
// Search for a node with a given data
search(node, data) {
if (!node) {
return null;
}
if (data < node.data) {
return this.search(node.left, data);
} else if (data > node.data) {
return this.search(node.right, data);
} else {
return node;
}
}
// Delete a node with a given data
delete(data) {
this.root = this.deleteNode(this.root, data);
}
deleteNode(node, data) {
if (!node) {
return null;
}
if (data < node.data) {
node.left = this.deleteNode(node.left, data);
return node;
} else if (data > node.data) {
node.right = this.deleteNode(node.right, data);
return node;
} else {
// Node to be deleted found
// Case 1: No children (leaf node)
if (!node.left && !node.right) {
node = null;
return node;
}
// Case 2: One child
if (!node.left) {
return node.right;
} else if (!node.right) {
return node.left;
}
// Case 3: Two children
const aux = this.findMinNode(node.right);
node.data = aux.data;
node.right = this.deleteNode(node.right, aux.data);
return node;
}
}
// Find the minimum node in the tree/subtree
findMinNode(node) {
while (node.left) {
node = node.left;
}
return node;
}
// In-order traversal (Left, Root, Right)
inOrderTraversal(node) {
if (node) {
this.inOrderTraversal(node.left);
console.log(node.data);
this.inOrderTraversal(node.right);
}
}
}
// Usage example
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);
console.log('In-order Traversal:');
bst.inOrderTraversal(bst.root); // Output: 5 7 9 10 13 15 17 22 25 27
console.log('Search for 22:');
const foundNode = bst.search(bst.root, 22);
if (foundNode) {
console.log('Node found:', foundNode.data); // Output: Node found: 22
} else {
console.log('Node not found');
}
console.log('Delete 22:');
bst.delete(22);
bst.inOrderTraversal(bst.root); // Output: 5 7 9 10 13 15 17 25 27
Heaps and Priority Queues
Heaps are a special tree-based structure satisfying the heap property, where each parent node is greater (max-heap) or lesser (min-heap) than its children. Priority queues are abstract data types built on heaps.
Heaps
Definition: A complete binary tree maintaining the heap property.
JavaScript does not have a built in heap data structure, but you can implement one using arrays. There are also libraries like heap.js that provide heap implementations.
Key Operations: Insertion (O(log n)), Extract Max/Min (O(log n))
Use Cases: Implementing priority queues, heap sort.
Code Sample:
class MinHeap {
constructor() {
this.heap = [];
}
// Get the parent index of a node
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
// Get the left child index of a node
getLeftChildIndex(index) {
return 2 * index + 1;
}
// Get the right child index of a node
getRightChildIndex(index) {
return 2 * index + 2;
}
// Swap two nodes in the heap
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [
this.heap[index2],
this.heap[index1],
];
}
// Insert a node into the heap (O(log n))
insert(data) {
this.heap.push(data);
this.heapifyUp(this.heap.length - 1);
}
// Heapify up to maintain the heap property
heapifyUp(index) {
let currentIndex = index;
let parentIndex = this.getParentIndex(currentIndex);
while (
currentIndex > 0 &&
this.heap[currentIndex] < this.heap[parentIndex]
) {
this.swap(currentIndex, parentIndex);
currentIndex = parentIndex;
parentIndex = this.getParentIndex(currentIndex);
}
}
// Extract the minimum element (O(log n))
extractMin() {
if (this.heap.length === 0) {
console.log('Heap is empty');
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown(0);
return min;
}
// Heapify down to maintain the heap property
heapifyDown(index) {
let smallest = index;
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
if (
leftChildIndex < this.heap.length &&
this.heap[leftChildIndex] < this.heap[smallest]
) {
smallest = leftChildIndex;
}
if (
rightChildIndex < this.heap.length &&
this.heap[rightChildIndex] < this.heap[smallest]
) {
smallest = rightChildIndex;
}
if (smallest !== index) {
this.swap(index, smallest);
this.heapifyDown(smallest);
}
}
// Print the heap
printHeap() {
console.log(this.heap);
}
}
// Usage example
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(5);
minHeap.insert(6);
minHeap.insert(1);
minHeap.insert(8);
minHeap.insert(9);
minHeap.printHeap(); // Output: [ 1, 6, 5, 20, 10, 8, 9 ]
console.log('Extracted Min:', minHeap.extractMin()); // Output: Extracted Min: 1
minHeap.printHeap(); // Output: [ 5, 6, 8, 20, 10, 9 ]
Priority Queues
Definition: An abstract data type where each element has a priority.
Key Operations: Insert (O(log n)), Extract Max/Min (O(log n))
Use Cases: Scheduling algorithms, Dijkstra's algorithm.
Code Sample:
class MinHeap {
constructor() {
this.heap = [];
}
// Get the parent index of a node
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
// Get the left child index of a node
getLeftChildIndex(index) {
return 2 * index + 1;
}
// Get the right child index of a node
getRightChildIndex(index) {
return 2 * index + 2;
}
// Swap two nodes in the heap
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [
this.heap[index2],
this.heap[index1],
];
}
// Insert a node into the heap (O(log n))
insert(data) {
this.heap.push(data);
this.heapifyUp(this.heap.length - 1);
}
// Heapify up to maintain the heap property
heapifyUp(index) {
let currentIndex = index;
let parentIndex = this.getParentIndex(currentIndex);
while (
currentIndex > 0 &&
this.heap[currentIndex].priority < this.heap[parentIndex].priority
) {
this.swap(currentIndex, parentIndex);
currentIndex = parentIndex;
parentIndex = this.getParentIndex(currentIndex);
}
}
// Extract the minimum element (O(log n))
extractMin() {
if (this.heap.length === 0) {
console.log('Heap is empty');
return null;
}
if (this.heap.length === 1) {
return this.heap.pop();
}
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown(0);
return min;
}
// Heapify down to maintain the heap property
heapifyDown(index) {
let smallest = index;
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
if (
leftChildIndex < this.heap.length &&
this.heap[leftChildIndex].priority < this.heap[smallest].priority
) {
smallest = leftChildIndex;
}
if (
rightChildIndex < this.heap.length &&
this.heap[rightChildIndex].priority < this.heap[smallest].priority
) {
smallest = rightChildIndex;
}
if (smallest !== index) {
this.swap(index, smallest);
this.heapifyDown(smallest);
}
}
// Print the heap
printHeap() {
console.log(this.heap);
}
}
class PriorityQueue {
constructor() {
this.minHeap = new MinHeap();
}
// Insert an element with a priority
insert(element, priority) {
this.minHeap.insert({element, priority});
}
// Extract the element with the highest priority (minimum priority value)
extractMin() {
return this.minHeap.extractMin();
}
// Print the priority queue
printQueue() {
this.minHeap.printHeap();
}
}
// Usage example
const pq = new PriorityQueue();
pq.insert('Task 1', 3);
pq.insert('Task 2', 1);
pq.insert('Task 3', 2);
pq.printQueue(); // Output: [ { element: 'Task 2', priority: 1 }, { element: 'Task 1', priority: 3 }, { element: 'Task 3', priority: 2 } ]
console.log('Extracted Min:', pq.extractMin()); // Output: Extracted Min: { element: 'Task 2', priority: 1 }
pq.printQueue(); // Output: [ { element: 'Task 3', priority: 2 }, { element: 'Task 1', priority: 3 } ]
Hash Tables
Hash tables are powerful data structures that map keys to values using a hash function. They provide average-case constant-time complexity for search, insertion, and deletion.
In JavaScript, Hash Tables are implemented using Objects or Maps.
Definition: A data structure that uses a hash function to map keys to buckets.
Key Operations: Insertion/Deletion/Lookup (O(1) average case)
Use Cases: Fast data retrieval, implementing associative arrays.
Graphs
Graphs represent networks of nodes (vertices) connected by edges. They are versatile structures used to model relationships and paths.
Adjacency Matrix
Definition: A 2D array representing graph connections.
Key Operations: Edge Check (O(1)), Space Complexity (O(V^2))
Use Cases: Dense graphs, algorithms requiring quick edge checks.
Code Sample:
class Graph {
constructor(size) {
this.size = size;
this.adjacencyMatrix = Array.from({length: size}, () =>
Array(size).fill(0),
);
}
// Add an edge to the graph
addEdge(vertex1, vertex2) {
if (vertex1 < this.size && vertex2 < this.size) {
this.adjacencyMatrix[vertex1][vertex2] = 1;
this.adjacencyMatrix[vertex2][vertex1] = 1; // For undirected graph
}
}
// Remove an edge from the graph
removeEdge(vertex1, vertex2) {
if (vertex1 < this.size && vertex2 < this.size) {
this.adjacencyMatrix[vertex1][vertex2] = 0;
this.adjacencyMatrix[vertex2][vertex1] = 0; // For undirected graph
}
}
// Check if there is an edge between two vertices
hasEdge(vertex1, vertex2) {
if (vertex1 < this.size && vertex2 < this.size) {
return this.adjacencyMatrix[vertex1][vertex2] === 1;
}
return false;
}
// Print the adjacency matrix
printMatrix() {
console.log(this.adjacencyMatrix);
}
}
// Usage example
const graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
console.log('Adjacency Matrix:');
graph.printMatrix();
// Output:
// [
// [0, 1, 1, 0, 0],
// [1, 0, 1, 1, 0],
// [1, 1, 0, 0, 1],
// [0, 1, 0, 0, 0],
// [0, 0, 1, 0, 0]
// ]
console.log('Edge between 0 and 1:', graph.hasEdge(0, 1)); // Output: true
console.log('Edge between 0 and 3:', graph.hasEdge(0, 3)); // Output: false
graph.removeEdge(0, 1);
console.log('Adjacency Matrix after removing edge between 0 and 1:');
graph.printMatrix();
// Output:
// [
// [0, 0, 1, 0, 0],
// [0, 0, 1, 1, 0],
// [1, 1, 0, 0, 1],
// [0, 1, 0, 0, 0],
// [0, 0, 1, 0, 0]
// ]
Adjacency List
Definition: An array of lists, where each list represents connections of a node.
Key Operations: Edge Check (O(V)), Space Complexity (O(V + E))
Use Cases: Sparse graphs, algorithms focusing on traversal.
Code Sample:
class Graph {
constructor() {
this.adjacencyList = new Map();
}
// Add a vertex to the graph
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
// Add an edge to the graph
addEdge(vertex1, vertex2) {
if (!this.adjacencyList.has(vertex1)) {
this.addVertex(vertex1);
}
if (!this.adjacencyList.has(vertex2)) {
this.addVertex(vertex2);
}
this.adjacencyList.get(vertex1).push(vertex2);
this.adjacencyList.get(vertex2).push(vertex1); // For undirected graph
}
// Remove an edge from the graph
removeEdge(vertex1, vertex2) {
if (this.adjacencyList.has(vertex1)) {
this.adjacencyList.set(
vertex1,
this.adjacencyList.get(vertex1).filter((v) => v !== vertex2),
);
}
if (this.adjacencyList.has(vertex2)) {
this.adjacencyList.set(
vertex2,
this.adjacencyList.get(vertex2).filter((v) => v !== vertex1),
);
}
}
// Check if there is an edge between two vertices
hasEdge(vertex1, vertex2) {
if (this.adjacencyList.has(vertex1)) {
return this.adjacencyList.get(vertex1).includes(vertex2);
}
return false;
}
// Print the adjacency list
printGraph() {
const keys = this.adjacencyList.keys();
for (let key of keys) {
const values = this.adjacencyList.get(key);
console.log(`${key} -> ${values.join(', ')}`);
}
}
}
// Usage example
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
console.log('Adjacency List:');
graph.printGraph();
// Output:
// A -> B, C
// B -> A, D
// C -> A, D
// D -> B, C
console.log('Edge between A and B:', graph.hasEdge('A', 'B')); // Output: true
console.log('Edge between A and D:', graph.hasEdge('A', 'D')); // Output: false
graph.removeEdge('A', 'B');
console.log('Adjacency List after removing edge between A and B:');
graph.printGraph();
// Output:
// A -> C
// B -> D
// C -> A, D
// D -> B, C
Union-Find (Disjoint Set)
The Union-Find data structure manages a partition of a set into disjoint subsets, supporting efficient union and find operations. It's crucial in network connectivity and Kruskal's algorithm for minimum spanning trees.
Definition: A data structure for tracking a set of elements split into disjoint subsets.
Key Operations: Find (O(α(n))), Union (O(α(n)))
Use Cases: Network connectivity, Kruskal's algorithm.
Code Sample:
class UnionFind {
constructor(size) {
this.parent = Array.from({length: size}, (_, index) => index);
this.rank = Array(size).fill(0);
}
// Find the root of the set containing element x with path compression
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
// Union two sets by rank
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
// Union by rank
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
// Check if two elements are in the same set
connected(x, y) {
return this.find(x) === this.find(y);
}
}
// Usage example
const uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
uf.union(6, 7);
console.log('1 and 3 connected?', uf.connected(1, 3)); // Output: true
console.log('1 and 4 connected?', uf.connected(1, 4)); // Output: false
uf.union(3, 4);
console.log('1 and 5 connected?', uf.connected(1, 5)); // Output: true
Explanation:
- Initialization:
- parent: An array where parent[i] is the parent of i. Initially, each element is its own parent.
- rank: An array to keep track of the rank (approximate depth) of each tree.
- Find:
This method finds the root of the set containing x and applies path compression, which flattens the structure of the tree whenever find is called. This helps in speeding up future operations.
- Union:
This method unites the sets containing x and y by connecting the roots of the trees. Union by rank attaches the shorter tree under the root of the taller tree to keep the tree as flat as possible.
- Connected:
This method checks if two elements are in the same set by comparing their roots.
Comments
Recent Work
Basalt
basalt.softwareFree desktop AI Chat client, designed for developers and businesses. Unlocks advanced model settings only available in the API. Includes quality of life features like custom syntax highlighting.
BidBear
bidbear.ioBidbear is a report automation tool. It downloads Amazon Seller and Advertising reports, daily, to a private database. It then merges and formats the data into beautiful, on demand, exportable performance reports.