Reference Note25 min readChathura Devinda

Data Structures & Algorithms: The Complete Foundation Reference

Comprehensive architectural reference covering memory layout, asymptotic analysis, essential data structures, traversal algorithms, and optimal problem-solving patterns.

Data Structures & Algorithms: The Complete Foundation Reference
DSAAlgorithmsTime ComplexityTreesGraphsDynamic Programming

Data Structures & Algorithms: The Complete Foundation Reference

A comprehensive, beginner-friendly handbook covering algorithmic foundations, time complexities, linear and non-linear memory structures, graph traversals, and modern problem-solving patterns with JavaScript (ES6+).

1. Asymptotic Analysis & Foundations

Algorithm efficiency measures runtime and memory scaling relative to input size N.

Performance Hierarchy

Faster / Better <-------------------------------------------------> Slower / Worse

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)

Constant < Logarithmic < Linear < Linearithmic < Quadratic < Exponential

Asymptotic Notations

•
Big-O (O): Upper bound, representing worst-case performance (e.g. element is at the end of the collection).
•
Big-Omega (Ω): Lower bound, representing best-case performance (e.g. element found on the first step).
•
Big-Theta (Θ): Tight bound, representing exact average and typical scaling.

Master Complexity Comparison Table

Data Structure / AlgorithmAccessSearchInsertDeleteSpace Complexity
ArrayO(1)O(N)O(N)O(N)O(N)
Singly Linked ListO(N)O(N)O(1)O(1)O(N)
Doubly Linked ListO(N)O(N)O(1)O(1)O(N)
Stack / QueueO(N)O(N)O(1)O(1)O(N)
Hash Table (Map / Object)N/AO(1) avgO(1) avgO(1) avgO(N)
Binary Search Tree (BST)O(log N)O(log N)O(log N)O(log N)O(N)
Binary Heap (Priority Queue)O(1) min/maxO(N)O(log N)O(log N)O(N)
Merge Sort————O(N)
Quick Sort————O(log N)

2. Linear Data Structures

Static & Dynamic Arrays

Arrays allocate continuous blocks in computer memory, offering immediate O(1) indexing through memory offsets: address = base + index * element_size.

Index:       [ 0 ]      [ 1 ]      [ 2 ]      [ 3 ]
Memory:     0x1000     0x1004     0x1008     0x100C
Values:     [  12   |   45   |   78   |   90   ]
javascriptCode Snippet
// Array Operations in JavaScript
const numbers = [12, 45, 78, 90];

// O(1) Instant Access
const firstItem = numbers[0];

// O(1) Fast append at tail
numbers.push(105);

// O(N) Linear shift when modifying beginning
numbers.unshift(5);

Singly & Doubly Linked Lists

Nodes store values and explicit memory references (pointers) to subsequent nodes, eliminating the need for contiguous memory allocation.

Architecture / Visual Diagram
Monospace Alignment
Singly:  [ Val: 10 | Next ] ---> [ Val: 25 | Next ] ---> [ Val: 40 | null ]
Doubly:  null <--- [ Prev | 10 | Next ] <===> [ Prev | 25 | Next ] ---> null
javascriptCode Snippet
// Node Class
class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Reverse a Singly Linked List in O(N) time and O(1) space
function reverseLinkedList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const nextNode = curr.next; // 1. Store next node
    curr.next = prev;           // 2. Reverse pointer
    prev = curr;                // 3. Advance prev
    curr = nextNode;            // 4. Advance curr
  }

  return prev; // New head of the reversed list
}

Stacks & Queues

•
Stack (LIFO — Last In, First Out): Used for execution call stacks, undo/redo buffers, and syntax parsing.
•
Queue (FIFO — First In, First Out): Used for task scheduling pipelines, breadth-first search traversals, and message buffers.

Stack (Push / Pop at Top):

|   30   |  <-- Top (Pop / Push)
|   20   |
|   10   |
+--------+

Queue (Enqueue at Rear, Dequeue at Front):

Front (Dequeue) [ 10 ] <--- [ 20 ] <--- [ 30 ] Rear (Enqueue)
javascriptCode Snippet
// Stack Implementation
class Stack {
  constructor() {
    this.items = [];
  }
  push(val) { this.items.push(val); }
  pop() { return this.items.pop(); }
  peek() { return this.items[this.items.length - 1]; }
  isEmpty() { return this.items.length === 0; }
}

// Queue Implementation
class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(val) {
    this.items[this.tail] = val;
    this.tail++;
  }
  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }
  isEmpty() { return this.tail - this.head === 0; }
}

3. Hash Tables & Collision Resolution

Hash functions compute an integer hash code mapped to bucket indices via hash(key) % capacity.

Key ("user_a") ---> [ Hash Function ] ---> Index: 3 ---> [ ("user_a", data) ]
Key ("user_k") ---> [ Hash Function ] ---> Index: 3 (Collision!)
•
Chaining: Stores collisions in linked lists or balanced search trees at each array index.
•
Open Addressing: Probes adjacent slots (linear: i+1, quadratic: i²) within the primary array upon collision.
javascriptCode Snippet
// JavaScript Native Hash Table (Map)
const userCache = new Map();

// O(1) Average Insertion & Lookup
userCache.set('usr_101', { name: 'Chathura', role: 'Engineer' });

if (userCache.has('usr_101')) {
  console.log(userCache.get('usr_101').name); // 'Chathura'
}

4. Trees & Binary Search Trees (BST)

A Binary Tree contains nodes with at most two children. In a Binary Search Tree (BST):

1.
The Left Subtree contains values strictly smaller than the parent.
2.
The Right Subtree contains values strictly greater than the parent.
Architecture / Visual Diagram
Monospace Alignment
          ( 20 )
         /      \
      ( 10 )    ( 35 )
      /    \       \
    ( 5 )  ( 15 )  ( 42 )

Tree Traversals

•
In-Order (Left → Root → Right): Visits BST nodes in ascending sorted sequence (5, 10, 15, 20, 35, 42).
•
Pre-Order (Root → Left → Right): Used to serialize and clone tree structures.
•
Post-Order (Left → Right → Root): Bottom-up dependency resolution and tree node deletion.
javascriptCode Snippet
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// In-Order Traversal (Returns sorted array)
function inOrderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;
    traverse(node.left);   // 1. Visit Left
    result.push(node.val); // 2. Visit Root
    traverse(node.right);  // 3. Visit Right
  }

  traverse(root);
  return result;
}

5. Priority Queues & Binary Heaps

A Min-Heap is a complete binary tree where every parent node is smaller than or equal to its children, mapped directly to an array:

•
Parent index: Math.floor((i - 1) / 2)
•
Left child index: 2 * i + 1
•
Right child index: 2 * i + 2
Architecture / Visual Diagram
Monospace Alignment
Tree Form:                 Array Indices:
     [ 2 ]                 [ 0 | 1 | 2 | 3 | 4 ]
    /     \                ---------------------
  [ 5 ]   [ 8 ]            [ 2 | 5 | 8 | 9 | 7 ]
  /   \
[ 9 ] [ 7 ]
javascriptCode Snippet
class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleUp(idx) {
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[idx] >= this.heap[parentIdx]) break;
      [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]];
      idx = parentIdx;
    }
  }

  bubbleDown(idx) {
    const length = this.heap.length;
    while (true) {
      let smallest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;

      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === idx) break;

      [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
      idx = smallest;
    }
  }
}

6. Graphs & Network Traversals

Graphs consist of Vertices (V) connected by Edges (E).

Architecture / Visual Diagram
Monospace Alignment
(0) ---- (1)
 |      /
 |    /
(2) ---- (3)

Adjacency List:
0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]

Breadth-First Search (BFS) & Depth-First Search (DFS)

javascriptCode Snippet
// Breadth-First Search (Layer by layer - Shortest path)
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);

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

  return order;
}

// Depth-First Search (Branch exploration)
function dfs(graph, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);

  for (const neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, order);
    }
  }

  return order;
}

7. Essential Algorithmic Patterns

1. Binary Search (O(log N))

Repeatedly divides the search range in half on ordered collections.

javascriptCode Snippet
function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] === target) return mid;
    else if (sortedArr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // Not found
}

2. Two Pointers Pattern (O(N))

Iterates through arrays using dual indices to reduce brute-force O(N²) checks down to linear O(N).

javascriptCode Snippet
// Two-Sum on Sorted Array
function twoSumSorted(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const currentSum = numbers[left] + numbers[right];
    if (currentSum === target) return [left, right];
    else if (currentSum < target) left++;
    else right--;
  }

  return [];
}

3. Sliding Window Pattern (O(N))

Maintains a moving window over a sequence to track running maximums, sums, or substrings.

javascriptCode Snippet
// Maximum sum of any contiguous subarray of size K
function maxSubarraySum(arr, k) {
  if (arr.length < k) return null;
  let maxSum = 0;
  let windowSum = 0;

  for (let i = 0; i < k; i++) windowSum += arr[i];
  maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

4. Dynamic Programming

Resolves complex optimization problems containing overlapping subproblems and optimal substructures.

javascriptCode Snippet
// Fibonacci sequence with Memoization: O(N) Time, O(N) Space
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}
Back to All NotesExplore Projects & Case Studies →