Data Structures

Why Data Structures Matter

A data structure is an organised way to store and manage data so that operations on it — inserting, deleting, searching, accessing — can be performed efficiently. Choosing the right structure is one of the highest-leverage decisions in software engineering. The difference between O(1) and O(n) access can mean the gap between a system that scales to millions of users and one that crashes under load.

Every data structure makes trade-offs: fast reads often mean slow writes, and low memory overhead often means complex code. Understanding these trade-offs lets you choose the right tool for each problem.

Arrays

An array stores elements in contiguous memory, each accessible by index in O(1). It is the most fundamental structure — almost every other structure is built on arrays or analogous concepts.

Key Properties

Common Patterns

// Two-pointer technique — O(n) time, O(1) space
function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}

// Sliding window — max sum subarray of size k
function maxSumSubarray(arr, k) {
  let sum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let max = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    max = Math.max(max, sum);
  }
  return max;
}

// Prefix sums — range sum in O(1) after O(n) build
function buildPrefix(arr) {
  const prefix = [0];
  for (const n of arr) prefix.push(prefix.at(-1) + n);
  return prefix;
}
// Sum from index l to r (inclusive):
// prefix[r+1] - prefix[l]

Linked Lists

A linked list stores elements in nodes scattered across memory. Each node holds a value and a pointer (reference) to the next node. Unlike arrays, linked lists have no index — you must traverse from the head to reach any element.

Singly linked: each node points to the next. Doubly linked: each node also points to the previous — enabling O(1) deletion with a node reference.

class ListNode {
  constructor(val) {
    this.val  = val;
    this.next = null;
  }
}

// Build: 1 → 2 → 3
const head = new ListNode(1);
head.next  = new ListNode(2);
head.next.next = new ListNode(3);

// Traverse
let curr = head;
while (curr) {
  console.log(curr.val);
  curr = curr.next;
}

// Reverse a linked list — classic interview question
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next  = prev;
    prev       = curr;
    curr       = next;
  }
  return prev; // new head
}

// Detect cycle — Floyd's fast/slow pointers
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Stacks & Queues

These are abstract data types — they define behaviour, not implementation. Both can be backed by an array or a linked list.

Stack — LIFO (Last In, First Out)

Push to the top; pop from the top. Used for undo/redo, call stack tracking, expression parsing, and DFS traversal.

// In JavaScript, use an array as a stack
const stack = [];
stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.push(3);   // [1, 2, 3]
stack.pop();     // returns 3, stack = [1, 2]
stack.at(-1);    // peek: 2 (no remove)

// Classic: valid parentheses
function isValid(s) {
  const stack = [], map = { ')': '(', '}': '{', ']': '[' };
  for (const c of s) {
    if ('({['.includes(c)) { stack.push(c); continue; }
    if (stack.pop() !== map[c]) return false;
  }
  return stack.length === 0;
}

Queue — FIFO (First In, First Out)

Enqueue at the back; dequeue from the front. Used for BFS traversal, task scheduling, and rate limiting.

// Simple queue with array (shift is O(n) — use a deque/linked list for large queues)
const queue = [];
queue.push('a');   // enqueue
queue.push('b');
queue.shift();     // dequeue → 'a'

// O(1) deque using two arrays (amortised O(1) per operation)
class Queue {
  #front = [];
  #back  = [];
  enqueue(v) { this.#back.push(v); }
  dequeue()  {
    if (!this.#front.length) this.#front = this.#back.reverse(), this.#back = [];
    return this.#front.pop();
  }
  get size() { return this.#front.length + this.#back.length; }
}

Hash Maps

A hash map (hash table, dictionary) maps keys to values in O(1) average time for get, set, and delete. Under the hood it uses a hash function to compute an array index from the key, with collision handling (chaining or open addressing).

In JavaScript, Map and plain objects {} serve this role. Use Map when keys are non-strings or order matters.

// Frequency count — O(n) time, O(n) space
function charFrequency(s) {
  const freq = new Map();
  for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1);
  return freq;
}

// Two-sum — classic O(n) solution using a hash map
function twoSum(nums, target) {
  const seen = new Map(); // value → index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return [];
}

// Anagram check — compare frequency maps
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = {};
  for (const c of s) freq[c] = (freq[c] ?? 0) + 1;
  for (const c of t) {
    if (!freq[c]) return false;
    freq[c]--;
  }
  return true;
}

Trees

A tree is a hierarchical structure of nodes connected by edges, with a single root and no cycles. Every node has at most one parent. Trees are used for file systems, DOM, compilers (AST), databases (B-trees), and more.

Binary Tree & BST

A binary tree allows at most two children per node. A binary search tree (BST) adds an invariant: every left descendant is smaller than the node, and every right descendant is larger. This gives O(log n) search on a balanced tree.

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

// DFS traversals (recursive)
function inorder(root, result = []) {       // left → root → right
  if (!root) return result;                  // sorted order for BST
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

function preorder(root, result = []) {      // root → left → right
  if (!root) return result;                 // good for copying a tree
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

// BFS — level order traversal
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    for (let i = queue.length; i > 0; i--) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// Tree height
function height(root) {
  if (!root) return 0;
  return 1 + Math.max(height(root.left), height(root.right));
}

// BST insert
function insert(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left  = insert(root.left,  val);
  else                root.right = insert(root.right, val);
  return root;
}

Heaps

A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is ≤ its children (so the minimum is always at the root). In a max-heap, every parent is ≥ its children. Heaps are typically stored as arrays using the formulas: left child = 2i+1, right child = 2i+2, parent = ⌊(i-1)/2⌋.

Heaps power priority queues. JavaScript doesn't have a built-in heap — the standard approach is to implement one or use a sorted array for small inputs.

class MinHeap {
  #heap = [];
  push(val) {
    this.#heap.push(val);
    this.#bubbleUp(this.#heap.length - 1);
  }
  pop() {
    const min = this.#heap[0];
    const last = this.#heap.pop();
    if (this.#heap.length) { this.#heap[0] = last; this.#siftDown(0); }
    return min;
  }
  peek() { return this.#heap[0]; }
  get size() { return this.#heap.length; }

  #bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.#heap[p] <= this.#heap[i]) break;
      [this.#heap[p], this.#heap[i]] = [this.#heap[i], this.#heap[p]];
      i = p;
    }
  }
  #siftDown(i) {
    const n = this.#heap.length;
    while (true) {
      let smallest = i;
      const [l, r] = [2*i+1, 2*i+2];
      if (l < n && this.#heap[l] < this.#heap[smallest]) smallest = l;
      if (r < n && this.#heap[r] < this.#heap[smallest]) smallest = r;
      if (smallest === i) break;
      [this.#heap[i], this.#heap[smallest]] = [this.#heap[smallest], this.#heap[i]];
      i = smallest;
    }
  }
}

// Use case: k-th smallest element, median maintenance, Dijkstra's algorithm

Graphs

A graph is a set of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, disconnected components, and edges in either direction. Graphs model social networks, maps, dependency chains, and web pages.

Key terminology: directed vs undirected; weighted vs unweighted; cyclic vs acyclic (DAG = Directed Acyclic Graph).

Representation

// Adjacency list — most common, efficient for sparse graphs
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B'],
};

// BFS — shortest path in unweighted graph
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue   = [start];
  const order   = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbour of graph[node] || []) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push(neighbour);
      }
    }
  }
  return order;
}

// DFS — explore deep, detect cycles, topological sort
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (const neighbour of graph[node] || []) dfs(graph, neighbour, visited);
}

// Count connected components
function countComponents(n, edges) {
  const adj = Array.from({length: n}, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  const visited = new Set();
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) { dfs(adj, i, visited); count++; }
  }
  return count;
}

Choosing the Right Structure

Practice Exercises

1. Implement a stack using only two queues.
2. Find the longest subarray with sum equal to k (use prefix sums + hash map).
3. Implement an LRU Cache with O(1) get and put (hash map + doubly linked list).
4. Find the k-th largest element in an unsorted array (use a min-heap of size k).
5. Given a binary tree, check if it is height-balanced (O(n) solution using a helper that returns height or -1 on imbalance).
6. Find the number of islands in a 2D grid (graph connected components via DFS/BFS).