Essential Data Structures and Algorithms Reference

Arrays and ArrayLists

Definition: A contiguous block of memory holding same-type elements, accessed by index.

• Fixed-size array vs. dynamic ArrayList: ArrayLists auto-resize.
• Operations: Access O(1), search O(n), insert/delete at end O(1) amortized, insert/delete at middle O(n) due to shifting.
• When to use: Known size, frequent random access reads.
• When NOT to use: Frequent insertions/deletions in the middle.
• Worked example: ArrayList ops add("A"), add(1,"B"), add("C") → Array state: ["A"] → ["A", "B"] → ["A", "B", "C"].

Linked Lists

Definition: Nodes containing a value and a pointer to the next node (and previous for doubly linked).

• Operations: Access O(n), insert at head O(1), insert at tail O(1) if tail pointer is kept, search O(n).
• Why insert at head is O(1): Requires only rewiring two pointers; no shifting needed.
• Worked example: Insert 5, 3, 7 at head → [5] → [3, 5] → [7, 3, 5].

Stacks (LIFO)

Definition: A linear structure where insertions and deletions occur at the same end (the top).

• Operations: push(x) O(1), pop() O(1), peek() O(1), isEmpty() O(1).
• Real-world analogies: Stack of plates, undo/redo, browser back button, function call stack, expression evaluation, balanced parentheses.
• Worked trace: push 1, push 2, push 3, pop, push 4, pop, pop → [1] → [1, 2] → [1, 2, 3] → [1, 2] → [1, 2, 4] → [1, 2] → [1].

Common mistake: Trying to access elements in the middle of a stack is not allowed.

Queues (FIFO)

Definition: Insertions occur at the rear, removals from the front.

• Operations: enqueue(x) O(1), dequeue() O(1), peek() O(1).
• Real-world analogies: Ticket line, printer queue, BFS traversal, OS process scheduling.
• Worked trace: enqueue 1, 2, 3, dequeue, enqueue 4, dequeue → [1] → [1, 2] → [1, 2, 3] → [2, 3] → [2, 3, 4] → [3, 4].

Deque and Priority Queue

Deque (double-ended queue): Can add/remove from both ends. Used for sliding windows.

Priority Queue: Each element has a priority; highest priority is processed first. Implemented with a heap. Used in Dijkstra/A*.

Stack vs. Queue Comparison

Searching and Sorting

Linear Search

function linearSearch(arr, target): for i from 0 to length(arr) - 1: if arr[i] == target: return i return -1

Complexity: O(n) time, O(1) space. Works on unsorted data.

Binary Search

Requires a sorted array.

function binarySearch(arr, target): low = 0, high = length(arr) - 1 while low <= high: mid = (low + high) / 2 if arr[mid] == target: return mid else if arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1

Worked example: Search for 14 in [2,5,8,10,13,14,16,21]. low=0, high=7, mid=3 → arr[3]=10 < 14 → low=4. low=4, high=7, mid=5 → arr[5]=14 → FOUND at index 5. Complexity: O(log n).

Sorting Algorithms

• Bubble Sort: Best O(n) with flag, avg/worst O(n²), space O(1), stable.
• Selection Sort: Find min in unsorted portion, swap to front. O(n²) all cases, space O(1), not stable.
• Insertion Sort: Shift each element back into sorted prefix. Best O(n), avg/worst O(n²), space O(1), stable, adaptive.

Merge Sort (Divide and Conquer)

function mergeSort(arr): if length(arr) <= 1: return arr mid = length(arr) / 2 left = mergeSort(arr[0..mid]) right = mergeSort(arr[mid..end]) return merge(left, right)

Complexity: O(n log n) all cases, space O(n), stable.

Quick Sort

function quickSort(arr, low, high): if low < high: p = partition(arr, low, high) quickSort(arr, low, p - 1) quickSort(arr, p + 1, high)

Complexity: Avg O(n log n), worst O(n²), space O(log n), not stable, in-place.

Sorting Comparison

Recursion

• Factorial: function fact(n): if n <= 1: return 1; return n * fact(n - 1)
• Sum of array: function arraySum(arr, i): if i == length(arr): return 0; return arr[i] + arraySum(arr, i + 1)

Binary Search Tree (BST)

Property: For every node, left subtree values < node value < right subtree values.

Traversals

• Inorder (L-Root-R): Gives sorted order.
• Preorder (Root-L-R): Used for copying/cloning a tree.
• Postorder (L-R-Root): Used for deleting nodes (children before parent).
• Level-order (BFS): Uses a queue; visits level by level.

Deletion Cases

1. Leaf node: Simply remove it.
2. One child: Replace the node with its child.
3. Two children: Find the inorder successor, copy its value, then delete the successor.

Graph Modeling

Graph = (V, E). V = vertices, E = edges.

• Directed: Edges have direction.
• Undirected: Edges go both ways.
• Weighted: Each edge has a cost.

Dijkstra's Algorithm

Goal: Shortest path from a source to all other nodes in a weighted graph with non-negative weights. It is a greedy algorithm.

Complexity: O((V + E) log V) with a binary heap.

A* Algorithm

Formula: f(n) = g(n) + h(n) where g(n) is the cost from start and h(n) is the estimated cost to the goal.

Heuristic: Must be admissible (never overestimate the actual cost) to guarantee the shortest path.