JavaScript offers powerful data structures that extend far beyond simple arrays and objects. When I first started working with complex algorithms, I quickly realized that choosing the right data structure makes the difference between elegant, efficient code and performance bottlenecks that plague applications.
Map and WeakMap for Advanced Key-Value Storage
The Map data structure revolutionizes how we handle key-value pairs in JavaScript. Unlike regular objects, Maps accept any data type as keys, including functions, objects, and primitives. This flexibility proves invaluable when implementing complex algorithms.
I frequently use Maps for caching expensive operations. The ability to use objects as keys allows me to create sophisticated memoization patterns that would be impossible with regular objects.
class FibonacciCalculator {
constructor() {
this.cache = new Map();
}
calculate(n) {
if (this.cache.has(n)) {
return this.cache.get(n);
}
let result;
if (n <= 1) {
result = n;
} else {
result = this.calculate(n - 1) + this.calculate(n - 2);
}
this.cache.set(n, result);
return result;
}
getCacheSize() {
return this.cache.size;
}
}
const fib = new FibonacciCalculator();
console.log(fib.calculate(40)); // Fast execution due to caching
WeakMap provides garbage collection benefits that prevent memory leaks. When objects used as keys are no longer referenced elsewhere, WeakMap automatically removes them. This feature becomes crucial when managing temporary associations between objects.
const objectMetadata = new WeakMap();
function attachMetadata(obj, data) {
objectMetadata.set(obj, data);
}
function processObject(obj) {
const metadata = objectMetadata.get(obj);
if (metadata) {
// Process with metadata
return { ...obj, processed: true, meta: metadata };
}
return obj;
}
// Objects and their metadata are automatically cleaned up
// when objects go out of scope
Set and WeakSet for Unique Collections
Sets excel at maintaining collections of unique values. I find them particularly useful for implementing algorithms that require duplicate detection or set operations like union, intersection, and difference.
class SetOperations {
static union(setA, setB) {
return new Set([...setA, ...setB]);
}
static intersection(setA, setB) {
return new Set([...setA].filter(x => setB.has(x)));
}
static difference(setA, setB) {
return new Set([...setA].filter(x => !setB.has(x)));
}
static symmetricDifference(setA, setB) {
const diff1 = this.difference(setA, setB);
const diff2 = this.difference(setB, setA);
return this.union(diff1, diff2);
}
}
// Finding unique elements in arrays
function removeDuplicates(arr) {
return [...new Set(arr)];
}
// Checking for common elements
function hasCommonElements(arr1, arr2) {
const set1 = new Set(arr1);
return arr2.some(item => set1.has(item));
}
WeakSet works similarly to WeakMap but stores only objects and allows automatic garbage collection. I use it for tracking object states without preventing garbage collection.
const processedObjects = new WeakSet();
function markAsProcessed(obj) {
processedObjects.add(obj);
}
function isProcessed(obj) {
return processedObjects.has(obj);
}
function processIfNeeded(obj) {
if (!isProcessed(obj)) {
// Perform processing
obj.processedAt = Date.now();
markAsProcessed(obj);
}
return obj;
}
Stack Implementation for LIFO Operations
Stacks follow the Last-In-First-Out principle and prove essential for many algorithmic solutions. While JavaScript arrays provide push() and pop() methods, implementing a dedicated Stack class offers better abstraction and additional functionality.
class Stack {
constructor() {
this.items = [];
this.maxSize = null;
}
push(item) {
if (this.maxSize && this.items.length >= this.maxSize) {
throw new Error('Stack overflow');
}
this.items.push(item);
return this.size();
}
pop() {
if (this.isEmpty()) {
throw new Error('Stack underflow');
}
return this.items.pop();
}
peek() {
if (this.isEmpty()) {
return null;
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
setMaxSize(size) {
this.maxSize = size;
}
}
// Expression evaluation using stack
function evaluatePostfix(expression) {
const stack = new Stack();
const tokens = expression.split(' ');
for (const token of tokens) {
if (!isNaN(token)) {
stack.push(parseFloat(token));
} else {
const b = stack.pop();
const a = stack.pop();
switch (token) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(a - b);
break;
case '*':
stack.push(a * b);
break;
case '/':
stack.push(a / b);
break;
}
}
}
return stack.pop();
}
// Parentheses matching
function isBalanced(str) {
const stack = new Stack();
const pairs = { '(': ')', '[': ']', '{': '}' };
for (const char of str) {
if (pairs[char]) {
stack.push(char);
} else if (Object.values(pairs).includes(char)) {
if (stack.isEmpty() || pairs[stack.pop()] !== char) {
return false;
}
}
}
return stack.isEmpty();
}
Queue Implementation for FIFO Operations
Queues implement First-In-First-Out behavior and are fundamental for breadth-first search, task scheduling, and buffering operations. A naive array-based implementation can suffer from performance issues due to shifting elements.
class Queue {
constructor() {
this.items = [];
this.front = 0;
this.rear = 0;
}
enqueue(item) {
this.items[this.rear] = item;
this.rear++;
return this.size();
}
dequeue() {
if (this.isEmpty()) {
return null;
}
const item = this.items[this.front];
delete this.items[this.front];
this.front++;
// Reset when queue becomes empty
if (this.front === this.rear) {
this.front = 0;
this.rear = 0;
this.items = [];
}
return item;
}
peek() {
return this.isEmpty() ? null : this.items[this.front];
}
isEmpty() {
return this.front === this.rear;
}
size() {
return this.rear - this.front;
}
clear() {
this.items = [];
this.front = 0;
this.rear = 0;
}
}
// Breadth-first search implementation
function breadthFirstSearch(graph, startNode, targetNode) {
const queue = new Queue();
const visited = new Set();
const parent = new Map();
queue.enqueue(startNode);
visited.add(startNode);
parent.set(startNode, null);
while (!queue.isEmpty()) {
const currentNode = queue.dequeue();
if (currentNode === targetNode) {
// Reconstruct path
const path = [];
let node = targetNode;
while (node !== null) {
path.unshift(node);
node = parent.get(node);
}
return path;
}
for (const neighbor of graph[currentNode] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
parent.set(neighbor, currentNode);
queue.enqueue(neighbor);
}
}
}
return null; // Path not found
}
Linked Lists for Dynamic Data Management
Linked lists provide dynamic memory allocation and efficient insertion/deletion operations. While JavaScript arrays are dynamic, linked lists offer better performance for frequent insertions and deletions at arbitrary positions.
class LinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(data) {
const newNode = new LinkedListNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
prepend(data) {
const newNode = new LinkedListNode(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
insertAt(index, data) {
if (index < 0 || index > this.length) {
throw new Error('Index out of bounds');
}
if (index === 0) {
return this.prepend(data);
}
if (index === this.length) {
return this.append(data);
}
const newNode = new LinkedListNode(data);
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.length++;
return this;
}
remove(data) {
if (!this.head) {
return null;
}
if (this.head.data === data) {
const removedData = this.head.data;
this.head = this.head.next;
if (!this.head) {
this.tail = null;
}
this.length--;
return removedData;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
const removedData = current.next.data;
current.next = current.next.next;
if (!current.next) {
this.tail = current;
}
this.length--;
return removedData;
}
return null;
}
find(data) {
let current = this.head;
let index = 0;
while (current) {
if (current.data === data) {
return { node: current, index };
}
current = current.next;
index++;
}
return null;
}
toArray() {
const result = [];
let current = this.head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
}
reverse() {
let prev = null;
let current = this.head;
this.tail = this.head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
return this;
}
}
// Usage example for implementing LRU Cache
class LRUCache {
constructor(maxSize) {
this.maxSize = maxSize;
this.cache = new Map();
this.list = new LinkedList();
}
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
// Move to front (most recently used)
this.list.remove(key);
this.list.prepend(key);
return value;
}
return null;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.set(key, value);
this.list.remove(key);
this.list.prepend(key);
return;
}
if (this.cache.size >= this.maxSize) {
// Remove least recently used
const lru = this.list.tail.data;
this.list.remove(lru);
this.cache.delete(lru);
}
this.cache.set(key, value);
this.list.prepend(key);
}
}
Binary Trees for Hierarchical Data
Binary trees organize data hierarchically and provide efficient searching, insertion, and deletion operations with logarithmic time complexity in balanced trees.
class BinaryTreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new BinaryTreeNode(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = newNode;
break;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
break;
}
current = current.right;
}
}
return this;
}
search(value) {
let current = this.root;
while (current) {
if (value === current.value) {
return current;
} else if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return null;
}
inOrderTraversal(node = this.root, result = []) {
if (node) {
this.inOrderTraversal(node.left, result);
result.push(node.value);
this.inOrderTraversal(node.right, result);
}
return result;
}
preOrderTraversal(node = this.root, result = []) {
if (node) {
result.push(node.value);
this.preOrderTraversal(node.left, result);
this.preOrderTraversal(node.right, result);
}
return result;
}
postOrderTraversal(node = this.root, result = []) {
if (node) {
this.postOrderTraversal(node.left, result);
this.postOrderTraversal(node.right, result);
result.push(node.value);
}
return result;
}
findMin(node = this.root) {
if (!node) return null;
while (node.left) {
node = node.left;
}
return node.value;
}
findMax(node = this.root) {
if (!node) return null;
while (node.right) {
node = node.right;
}
return node.value;
}
delete(value) {
this.root = this.deleteNode(this.root, value);
return this;
}
deleteNode(node, value) {
if (!node) return null;
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
} else {
// Node to delete found
if (!node.left && !node.right) {
return null;
}
if (!node.left) {
return node.right;
}
if (!node.right) {
return node.left;
}
// Node has two children
const minRight = this.findMin(node.right);
node.value = minRight;
node.right = this.deleteNode(node.right, minRight);
}
return node;
}
getHeight(node = this.root) {
if (!node) return -1;
const leftHeight = this.getHeight(node.left);
const rightHeight = this.getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
Hash Tables for Constant-Time Access
Hash tables provide average constant-time access to key-value pairs. While JavaScript objects and Maps serve as hash tables, implementing custom hash tables helps understand the underlying mechanics and provides customization options.
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
this.size = size;
}
_hash(key) {
let total = 0;
const PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
const char = key[i];
const value = char.charCodeAt(0) - 96;
total = (total * PRIME + value) % this.size;
}
return total;
}
set(key, value) {
const index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
const bucket = this.keyMap[index];
const existingPair = bucket.find(pair => pair[0] === key);
if (existingPair) {
existingPair[1] = value;
} else {
bucket.push([key, value]);
}
return this;
}
get(key) {
const index = this._hash(key);
const bucket = this.keyMap[index];
if (bucket) {
const pair = bucket.find(pair => pair[0] === key);
return pair ? pair[1] : undefined;
}
return undefined;
}
has(key) {
return this.get(key) !== undefined;
}
delete(key) {
const index = this._hash(key);
const bucket = this.keyMap[index];
if (bucket) {
const pairIndex = bucket.findIndex(pair => pair[0] === key);
if (pairIndex !== -1) {
return bucket.splice(pairIndex, 1)[0];
}
}
return undefined;
}
keys() {
const keys = [];
for (const bucket of this.keyMap) {
if (bucket) {
for (const pair of bucket) {
keys.push(pair[0]);
}
}
}
return keys;
}
values() {
const values = [];
for (const bucket of this.keyMap) {
if (bucket) {
for (const pair of bucket) {
values.push(pair[1]);
}
}
}
return values;
}
entries() {
const entries = [];
for (const bucket of this.keyMap) {
if (bucket) {
entries.push(...bucket);
}
}
return entries;
}
}
Heaps for Priority Operations
Heaps implement priority queues where elements are served based on priority rather than insertion order. They’re essential for algorithms like Dijkstra’s shortest path and heap sort.
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
getLeftChildIndex(index) {
return 2 * index + 1;
}
getRightChildIndex(index) {
return 2 * index + 2;
}
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
insert(value) {
this.heap.push(value);
this.heapifyUp();
return this;
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] <= this.heap[index]) {
break;
}
this.swap(parentIndex, index);
index = parentIndex;
}
}
extractMin() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return min;
}
heapifyDown() {
let index = 0;
while (this.getLeftChildIndex(index) < this.heap.length) {
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
let smallestIndex = leftChildIndex;
if (rightChildIndex < this.heap.length &&
this.heap[rightChildIndex] < this.heap[leftChildIndex]) {
smallestIndex = rightChildIndex;
}
if (this.heap[index] <= this.heap[smallestIndex]) {
break;
}
this.swap(index, smallestIndex);
index = smallestIndex;
}
}
peek() {
return this.heap.length > 0 ? this.heap[0] : null;
}
size() {
return this.heap.length;
}
isEmpty() {
return this.heap.length === 0;
}
}
// Priority Queue implementation using heap
class PriorityQueue {
constructor() {
this.heap = new MinHeap();
}
enqueue(item, priority) {
this.heap.insert({ item, priority });
}
dequeue() {
const node = this.heap.extractMin();
return node ? node.item : null;
}
peek() {
const node = this.heap.peek();
return node ? node.item : null;
}
isEmpty() {
return this.heap.isEmpty();
}
}
// Dijkstra's algorithm using priority queue
function dijkstra(graph, start) {
const distances = {};
const previous = {};
const pq = new PriorityQueue();
// Initialize distances
for (const vertex in graph) {
distances[vertex] = vertex === start ? 0 : Infinity;
previous[vertex] = null;
pq.enqueue(vertex, distances[vertex]);
}
while (!pq.isEmpty()) {
const current = pq.dequeue();
if (graph[current]) {
for (const neighbor in graph[current]) {
const distance = distances[current] + graph[current][neighbor];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
previous[neighbor] = current;
pq.enqueue(neighbor, distance);
}
}
}
}
return { distances, previous };
}
Graphs for Network Representation
Graphs represent relationships between entities and enable algorithms for pathfinding, network analysis, and connectivity problems. They can be implemented using adjacency lists or adjacency matrices.
class Graph {
constructor(directed = false) {
this.adjacencyList = {};
this.directed = directed;
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
return this;
}
addEdge(vertex1, vertex2, weight = 1) {
this.addVertex(vertex1);
this.addVertex(vertex2);
this.adjacencyList[vertex1].push({ node: vertex2, weight });
if (!this.directed) {
this.adjacencyList[vertex2].push({ node: vertex1, weight });
}
return this;
}
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
edge => edge.node !== vertex2
);
if (!this.directed) {
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
edge => edge.node !== vertex1
);
}
return this;
}
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop().node;
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
return this;
}
depthFirstSearch(start, visited = new Set(), result = []) {
visited.add(start);
result.push(start);
this.adjacencyList[start].forEach(neighbor => {
if (!visited.has(neighbor.node)) {
this.depthFirstSearch(neighbor.node, visited, result);
}
});
return result;
}
breadthFirstSearch(start) {
const queue = new Queue();
const visited = new Set();
const result = [];
queue.enqueue(start);
visited.add(start);
while (!queue.isEmpty()) {
const vertex = queue.dequeue();
result.push(vertex);
this.adjacencyList[vertex].forEach(neighbor => {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
queue.enqueue(neighbor.node);
}
});
}
return result;
}
hasPath(start, end) {
const visited = new Set();
const stack = [start];
while (stack.length > 0) {
const vertex = stack.pop();
if (vertex === end) return true;
if (visited.has(vertex)) continue;
visited.add(vertex);
this.adjacencyList[vertex].forEach(neighbor => {
if (!visited.has(neighbor.node)) {
stack.push(neighbor.node);
}
});
}
return false;
}
findShortestPath(start, end) {
const queue = new Queue();
const visited = new Set();
const parent = new Map();
queue.enqueue(start);
visited.add(start);
parent.set(start, null);
while (!queue.isEmpty()) {
const vertex = queue.dequeue();
if (vertex === end) {
// Reconstruct path
const path = [];
let current = end;
while (current !== null) {
path.unshift(current);
current = parent.get(current);
}
return path;
}
this.adjacencyList[vertex].forEach(neighbor => {
if (!visited.has(neighbor.node)) {
visited.add(neighbor.node);
parent.set(neighbor.node, vertex);
queue.enqueue(neighbor.node);
}
});
}
return null;
}
}
Trie for Efficient String Operations
Tries excel at string-related operations like autocomplete, spell checkers, and dictionary implementations. They provide efficient prefix matching and string storage with shared prefixes.
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
this.frequency = 0;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let current = this.root;
for (const char of word.toLowerCase()) {
if (!current.children[char]) {
current.children[char] = new TrieNode();
}
current = current.children[char];
}
current.isEndOfWord = true;
current.frequency++;
return this;
}
search(word) {
let current = this.root;
for (const char of word.toLowerCase()) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return current.isEndOfWord;
}
startsWith(prefix) {
let current = this.root;
for (const char of prefix.toLowerCase()) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return true;
}
getAllWordsWithPrefix(prefix) {
let current = this.root;
const words = [];
// Navigate to prefix end
for (const char of prefix.toLowerCase()) {
if (!current.children[char]) {
return [];
}
current = current.children[char];
}
// Collect all words from this point
this._collectWords(current, prefix.toLowerCase(), words);
return words;
}
_
