Data Structures
Lists, trees, graphs, hash tables, heaps, tries, sorting algorithms, and algorithm analysis in Java.
Introduction to Data Structures
What is a Data Structure? A data structure is a way of organizing data in memory so that it can be used efficiently. It is NOT just an implementation detail - it is a design decision that determines...
What is a Data Structure?
A data structure is a way of organizing data in memory so that it can be used efficiently. It is NOT just an implementation detail - it is a design decision that determines what operations are fast, what operations are slow, and how much memory you need.
Every program performs operations on data:
- Insert: add a new element
- Delete: remove an element
- Search: find an element
- Iterate: visit all elements in order
- Sort: arrange elements in some order
Different data structures make different operations fast or slow.
The Central Trade-off: Time vs Space
There is no perfect data structure. Every choice is a trade-off:
- Arrays are compact (no extra memory) and allow O(1) access by index, but inserting in the middle is O(n).
- Linked lists allow O(1) insert at the head, but accessing the k-th element requires O(k) traversal.
- Hash tables give O(1) average lookup, but use extra memory for the hash table itself.
- Trees give O(log n) insert/search in balanced form, but require pointers.
Asymptotic Analysis Preview
The standard way to compare data structures is Big-O notation:
- O(1): constant time (same regardless of n)
- O(log n): logarithmic (very fast even for huge n)
- O(n): linear (proportional to n)
- O(n log n): typical for good sorting
- O(n^2): quadratic (slow for large n)
A Concrete Example
Suppose you need to store 1,000,000 customer records:
Array:
- Memory: 1,000,000 x 100 bytes = ~100 MB
- Look up by ID: O(n) if unsorted, O(log n) if sorted
- Insert new customer: O(n) (must shift later elements)
Hash table:
- Memory: 1,000,000 x 100 bytes + 30% overhead = ~130 MB
- Look up by ID: O(1) average
- Insert new customer: O(1) average
The hash table is 30% bigger but ~1,000,000x faster on lookups. For most applications, this is the right trade-off.
Key Takeaways
- Data structures are about trade-offs, not universal solutions
- The choice can change O(n^2) into O(n log n)
- Always ask: what operations do I need to be FAST?
- Big-O is the language we use to compare them
Arrays and Linked Lists
Arrays An array is a contiguous block of memory holding elements of the same type: int[] a = new int[10]; // allocates 10 integers a[0] = 42; // O(1) access Indexing is O(1) - the JV...
Arrays
An array is a contiguous block of memory holding elements of the same type:
int[] a = new int[10]; // allocates 10 integers
a[0] = 42; // O(1) access
Indexing is O(1) - the JVM computes base + index * element_size.
Advantages:
- Extremely fast random access
- Compact memory layout (no pointers)
- Cache-friendly (contiguous memory)
Disadvantages:
- Fixed size (Java arrays cannot grow)
- Insertion/deletion in the middle is O(n)
Implementing a Dynamic Array (ArrayList)
To grow, we allocate a bigger array and copy. The trick is doubling:
public class ArrayList {
private int[] data;
private int size;
public ArrayList() {
data = new int[10];
size = 0;
}
public void add(int value) {
if (size == data.length) grow();
data[size++] = value;
}
private void grow() {
int[] bigger = new int[data.length * 2];
System.arraycopy(data, 0, bigger, 0, size);
data = bigger;
}
public int get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
return data[index];
}
}
Linked Lists
A linked list stores each element in a node with a reference to the next node:
class Node {
int value;
Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
public class LinkedList {
private Node head;
private int size;
public void addFirst(int value) {
head = new Node(value, head);
size++;
}
public int get(int index) {
Node cur = head;
for (int i = 0; i < index; i++) cur = cur.next;
return cur.value;
}
}
The Trade-off in Practice
Operation | ArrayList | LinkedList
-----------------|----------------|----------------
get(i) | O(1) | O(n)
add at end | O(1) amortized | O(1) with tail
add at front | O(n) | O(1)
remove at front | O(n) | O(1)
Memory per item | 4 bytes | 4 + 8 bytes
When to Use Which
Use ArrayList when:
- You mostly read/access by index
- You add/remove at the end
- Memory matters
Use LinkedList when:
- You add/remove frequently at the front
- You need a queue or stack (both O(1) at head)
- Random access is rare
Key Takeaways
- ArrayList = fast random access, slow middle insert
- LinkedList = fast front insert, slow random access
- Doubling strategy gives O(1) amortized add
- Always measure before optimizing
Stacks and Queues
Abstract Data Types: Stack and Queue A Stack is Last-In-First-Out (LIFO). A Queue is First-In-First-Out (FIFO). These are abstract data types - they define behavior, not implementation. Stack...
Abstract Data Types: Stack and Queue
A Stack is Last-In-First-Out (LIFO). A Queue is First-In-First-Out (FIFO). These are abstract data types - they define behavior, not implementation.
Stack operations:
- push(x) - add x on top
- pop() - remove and return top
- peek() - return top without removing
- isEmpty() - true if empty
Queue operations:
- enqueue(x) - add x to back
- dequeue() - remove and return front
- peek() - return front
- isEmpty() - true if empty
Array-Backed Stack
public class ArrayStack {
private int[] data;
private int top;
public ArrayStack() { data = new int[10]; top = 0; }
public void push(int value) {
if (top == data.length) grow();
data[top++] = value;
}
public int pop() {
if (top == 0) throw new RuntimeException("Empty stack");
return data[--top];
}
public int peek() { return data[top - 1]; }
public boolean isEmpty() { return top == 0; }
private void grow() {
int[] bigger = new int[data.length * 2];
System.arraycopy(data, 0, bigger, 0, top);
data = bigger;
}
}
All operations are O(1) amortized.
Linked-List Stack
public class LinkedStack {
private Node top;
public void push(int value) { top = new Node(value, top); }
public int pop() {
int v = top.value;
top = top.next;
return v;
}
}
Linked-List Queue
Keep pointers to BOTH head and tail:
public class LinkedQueue {
private Node head, tail;
public void enqueue(int value) {
Node n = new Node(value, null);
if (head == null) {
head = tail = n;
} else {
tail.next = n;
tail = n;
}
}
public int dequeue() {
int v = head.value;
head = head.next;
if (head == null) tail = null;
return v;
}
}
All operations O(1).
Real-World Applications
Stacks:
- Function call stack (recursion)
- Undo/redo in editors
- Balanced parentheses checking
- Depth-First Search (DFS)
- Expression evaluation
Queues:
- Print spooler
- Task schedulers
- Breadth-First Search (BFS)
- Message queues (RabbitMQ, Kafka)
- Request buffering in web servers
Balanced Parentheses - Classic Stack Problem
public boolean isBalanced(String s) {
ArrayStack stack = new ArrayStack();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char open = stack.pop();
if (c == ')' && open != '(') return false;
if (c == ']' && open != '[') return false;
if (c == '}' && open != '{') return false;
}
}
return stack.isEmpty();
}
Key Takeaways
- Stack = LIFO, Queue = FIFO
- Both can be array-backed or list-backed
- O(1) for all core operations
- Queue needs both head AND tail pointers
- Circular arrays give better cache locality
Binary Search Trees
The BST Invariant A Binary Search Tree is a binary tree where for every node: All values in the left subtree are LESS than the node All values in the right subtree are GREATER than the node This...
The BST Invariant
A Binary Search Tree is a binary tree where for every node:
- All values in the left subtree are LESS than the node
- All values in the right subtree are GREATER than the node
This gives a powerful guarantee: in-order traversal visits nodes in sorted order.
Node Structure
class BSTNode {
int value;
BSTNode left, right;
BSTNode(int value) { this.value = value; }
}
public class BST {
private BSTNode root;
private int size;
}
Insert
public void insert(int value) {
root = insert(root, value);
}
private BSTNode insert(BSTNode node, int value) {
if (node == null) {
size++;
return new BSTNode(value);
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
}
return node;
}
Time complexity: O(h) where h is the height.
Search
public boolean contains(int value) {
BSTNode cur = root;
while (cur != null) {
if (value == cur.value) return true;
cur = value < cur.value ? cur.left : cur.right;
}
return false;
}
Also O(h).
Delete - The Hard Case
Three cases:
Case 1: Leaf node - just remove it.
Case 2: One child - replace node with its child.
Case 3: Two children - find the in-order successor (smallest value in right subtree), copy its value into this node, then delete the successor.
private BSTNode delete(BSTNode node, int value) {
if (node == null) return null;
if (value < node.value) {
node.left = delete(node.left, value);
} else if (value > node.value) {
node.right = delete(node.right, value);
} else {
if (node.left == null) return node.right;
if (node.right == null) return node.left;
BSTNode successor = findMin(node.right);
node.value = successor.value;
node.right = delete(node.right, successor.value);
}
return node;
}
private BSTNode findMin(BSTNode node) {
while (node.left != null) node = node.left;
return node;
}
In-Order Traversal
public void inOrder(BSTNode node) {
if (node == null) return;
inOrder(node.left);
System.out.println(node.value);
inOrder(node.right);
}
Visits nodes in sorted order. Time: O(n).
The Imbalance Problem
Insert values in sorted order: 1, 2, 3, 4, 5, 6, 7.
1
\
2
\
3
\
4
This tree has height n, not log n! Every operation is O(n) instead of O(log n). The tree has degenerated into a linked list.
Real-world data is often nearly sorted:
- Time series data
- User IDs
- Auto-incrementing keys
- Sorted file names
BST vs Hash Table
Operation | BST (balanced) | Hash Table
--------------------|----------------|------------
Insert | O(log n) | O(1) avg
Search | O(log n) | O(1) avg
Delete | O(log n) | O(1) avg
In-order traversal | O(n) | not possible
Min/Max | O(log n) | O(n)
Range query | O(log n + k) | O(n)
Use BSTs when you need ORDERED operations.
Use hash tables when you only need lookup.
Key Takeaways
- BST gives O(log n) operations when balanced
- Delete has three cases; two-children is tricky
- In-order traversal produces sorted output
- Sorted insertion degenerates to O(n)
- Self-balancing variants fix this
Balanced Trees: AVL and Red-Black
Why Balance Matters In the previous lecture, we saw that an unbalanced BST can degenerate to O(n). AVL trees were the first self-balancing BST, invented in 1962 by Adelson-Velsky and Landis. The AVL...
Why Balance Matters
In the previous lecture, we saw that an unbalanced BST can degenerate to O(n). AVL trees were the first self-balancing BST, invented in 1962 by Adelson-Velsky and Landis.
The AVL invariant: for every node, the heights of the left and right subtrees differ by at most 1.
The balance factor: height(left) - height(right) is in {-1, 0, 1}.
AVL Tree Height
Claim: an AVL tree with n nodes has height <= 1.44 log2(n).
Proof sketch: the minimum number of nodes in an AVL tree of height h follows the Fibonacci recurrence N(h) = N(h-1) + N(h-2) + 1. Solving gives N(h) ~ phi^h where phi = 1.618. So h ~ 1.44 log2(n).
Rotations
To restore the AVL property after insert/delete, we use rotations - local restructuring operations that preserve the BST invariant.
Right Rotation:
y x
/ \ / \
x T3 -> T1 y
/ \ / \
T1 T2 T2 T3
x becomes the parent, y becomes x's right child, and x's old right subtree T2 becomes y's new left subtree.
Left Rotation (mirror):
x y
/ \ / \
T1 y -> x T3
/ \ / \
T2 T3 T1 T2
Insertion Algorithm
- Insert as in a normal BST.
- Walk back up the path, updating heights.
- At each node, compute the balance factor.
- If |balance| > 1, apply one of four rotation cases:
LL case (Left-Left): single right rotation
RR case (Right-Right): single left rotation
LR case (Left-Right): left rotation on left child, then right rotation
RL case (Right-Left): right rotation on right child, then left rotation
Insert Example
Insert 30, 20, 10 in order:
Step 1: 30
Step 2: 30 (no rotation)
/
20
Step 3: 30 (balance factor at 30 is +2)
/ -> Right rotate at 30
20
/
10
Result:
20
/ \
10 30
Delete Algorithm
Delete is trickier: after deleting a node, we may need to rebalance multiple levels up the tree. In the worst case, O(log n) rotations.
AVL vs Red-Black
Both guarantee O(log n) height, but with different trade-offs:
Aspect | AVL | Red-Black
--------------------|----------------|------------
Height (worst) | 1.44 log n | 2 log n
Faster for... | Lookups | Inserts/Deletes
Implementation | Simpler | More complex
Rotation frequency | More | Fewer
AVL is better when reads dominate.
Red-Black is better when writes dominate.
Java's TreeMap and TreeSet use Red-Black trees.
C++'s std::map typically uses Red-Black.
Real-World Uses
- Database indexes - B-trees (generalization)
- File systems - NTFS, ext4, HFS+ use B-trees
- Language standard libraries - std::map, TreeMap
- In-memory sorted sets - Redis sorted sets
Key Takeaways
- AVL invariant: |height(L) - height(R)| <= 1
- Height is bounded by 1.44 log2(n)
- Rotations are O(1) and preserve the BST property
- Four rotation cases: LL, RR, LR, RL
- Insert/delete/search are all O(log n)
- Choose Red-Black over AVL when writes dominate
Hash Tables
The Hashing Idea A hash table stores key-value pairs and provides O(1) average-case insert, search, and delete. The idea: use a hash function to map keys to array indices. hash("apple")...
The Hashing Idea
A hash table stores key-value pairs and provides O(1) average-case insert, search, and delete. The idea: use a hash function to map keys to array indices.
hash("apple") -> 42
hash("banana") -> 17
hash("cherry") -> 42 // collision with apple!
Hash Functions
A good hash function should:
- Be deterministic (same key -> same hash)
- Be fast to compute
- Distribute keys uniformly
- Minimize collisions
Java's hashCode():
Integer.hashCode(42) // 42
"hello".hashCode() // 99162322
Arrays.hashCode(new int[]{1,2}) // 994
For custom classes:
@Override
public int hashCode() {
int result = 17;
result = 31 * result + name.hashCode();
result = 31 * result + age;
return result;
}
Why 31? It's a prime, and 31 * x can be optimized to (x << 5) - x.
Collision Resolution Strategy 1: Chaining
Each array slot holds a linked list of entries with the same hash.
class ChainHashTable {
private Node[] buckets;
private int size;
private int capacity;
private static class Node {
Object key, value;
Node next;
}
public void put(Object key, Object value) {
int idx = Math.floorMod(key.hashCode(), capacity);
for (Node n = buckets[idx]; n != null; n = n.next) {
if (n.key.equals(key)) {
n.value = value;
return;
}
}
Node newNode = new Node();
newNode.key = key;
newNode.value = value;
newNode.next = buckets[idx];
buckets[idx] = newNode;
size++;
if ((double) size / capacity > 0.75) resize();
}
public Object get(Object key) {
int idx = Math.floorMod(key.hashCode(), capacity);
for (Node n = buckets[idx]; n != null; n = n.next) {
if (n.key.equals(key)) return n.value;
}
return null;
}
private void resize() {
Node[] old = buckets;
capacity *= 2;
buckets = new Node[capacity];
size = 0;
for (Node head : old) {
for (Node n = head; n != null; n = n.next) {
put(n.key, n.value);
}
}
}
}
Strategy 2: Open Addressing
No linked lists. On collision, probe for the next empty slot.
Linear probing: try idx+1, idx+2, idx+3...
Quadratic probing: try idx+1^2, idx+2^2, idx+3^2...
Double hashing: use a second hash function
Linear probing is fastest due to cache locality but suffers from clustering (runs of occupied slots).
Load Factor
The load factor is size / capacity. Java's HashMap resizes when it exceeds 0.75.
- Too low (< 0.5): wastes memory
- Too high (> 0.9): many collisions, slow
- Sweet spot: 0.7 - 0.75
Why O(1) Average?
Assume simple uniform hashing (each key equally likely to hash to any slot). The expected length of a chain is n/m = load factor alpha.
With alpha = 0.75, expected search time is O(1 + alpha) = O(1).
Worst-Case O(n)
If all keys hash to the same bucket, the table becomes a linked list: O(n). Adversaries can craft keys that all collide (hash flooding attack).
Java 8+ mitigates this by converting long chains into red-black trees, giving O(log n) worst case.
Real-World Applications
- Databases: hash indexes for equality queries
- Compilers: symbol tables
- Caches: memcached, Redis
- Deduplication: finding duplicate files
- Set membership: Bloom filters
- Cryptographic hashing: SHA-256, bcrypt
Hash Tables in Java
Map<String, Integer> map = new HashMap<>();
map.put("apple", 42);
map.put("banana", 17);
int x = map.get("apple"); // 42
Set<String> set = new HashSet<>();
set.add("hello");
boolean has = set.contains("hello"); // true
Key Takeaways
- Hash tables give O(1) average performance
- Hash functions must be deterministic and uniform
- Collisions handled by chaining or open addressing
- Load factor around 0.75 is optimal
- Worst case is O(n) but rarely hit
- Java 8+ uses Red-Black trees for long chains
Heaps and Priority Queues
What is a Heap? A binary heap is a complete binary tree that satisfies the heap property: Min-heap: every parent is <= its children Max-heap: every parent is >= its children A complete binary...
What is a Heap?
A binary heap is a complete binary tree that satisfies the heap property:
- Min-heap: every parent is <= its children
- Max-heap: every parent is >= its children
A complete binary tree has all levels full except possibly the last, which is filled left-to-right.
Because it's complete, we can store it in an array without pointers:
10
/ \
20 30
/ \ /
40 50 60
Array: [10, 20, 30, 40, 50, 60]
For a node at index i:
- Left child: 2i + 1
- Right child: 2i + 2
- Parent: (i - 1) / 2
Insert (bubble up)
- Add the new element at the end
- While it's smaller than its parent, swap
- Continue until the heap property is restored
public void insert(int value) {
data[size] = value;
int i = size++;
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) break;
swap(i, parent);
i = parent;
}
}
Time: O(log n).
Extract Min (bubble down)
- Save the root value
- Move the last element to the root
- Bubble it down until it's smaller than both children
- Decrease size
public int extractMin() {
int min = data[0];
data[0] = data[--size];
int i = 0;
while (true) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < size && data[left] < data[smallest]) smallest = left;
if (right < size && data[right] < data[smallest]) smallest = right;
if (smallest == i) break;
swap(i, smallest);
i = smallest;
}
return min;
}
Time: O(log n).
Peek Min
public int peekMin() { return data[0]; }
Time: O(1).
Heapify (build from array in O(n))
Given an arbitrary array, we can build a heap in O(n) by bubbling down from the middle to the start:
public static void heapify(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
bubbleDown(arr, i);
}
}
Why O(n) and not O(n log n)? Because most nodes are leaves and don't need to sink.
Heapsort
- Build a max-heap from the array (O(n))
- Repeatedly swap root with last, shrink, bubble down (O(n log n))
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) bubbleDown(arr, i, n);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
bubbleDown(arr, 0, i);
}
}
O(n log n) worst case, O(1) extra space.
Priority Queue
Task scheduling, Dijkstra's algorithm, A* search, Huffman coding.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5); pq.add(1); pq.add(3);
pq.poll(); // returns 1
pq.peek(); // returns 3
Dijkstra's Algorithm Using a Heap
int[] dijkstra(Graph g, int start) {
int[] dist = new int[g.n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[1] > dist[cur[0]]) continue;
for (Edge e : g.edges[cur[0]]) {
int nd = cur[1] + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
pq.add(new int[]{e.to, nd});
}
}
}
return dist;
}
Heap vs Sorted Array
Operation | Heap | Sorted Array
-------------|------------|--------------
Insert | O(log n) | O(n)
Extract min | O(log n) | O(1)
Peek min | O(1) | O(1)
Build | O(n) | O(n log n)
Heaps win when you have a mix of insert and extract.
Key Takeaways
- Heap = complete binary tree with heap property
- Stored as array - no pointers needed
- Insert/extract = O(log n)
- Peek = O(1)
- Heapify in O(n)
- Powers priority queues, heapsort, Dijkstra
Graphs: Representations and Traversals
Graph Representations A graph G = (V, E) consists of vertices V and edges E. Two standard representations: Adjacency Matrix A 2D array adj[i][j] = weight if there's an edge from i to j. 0 1...
Graph Representations
A graph G = (V, E) consists of vertices V and edges E. Two standard representations:
Adjacency Matrix
A 2D array adj[i][j] = weight if there's an edge from i to j.
0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 1 ]
3 [ 0 1 1 0 ]
Pros: O(1) edge lookup, simple
Cons: O(V^2) space (bad for sparse graphs)
Adjacency List
Array of lists: adj[i] = list of neighbors of i.
List<Integer>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
adj[0].add(1); adj[0].add(2);
adj[1].add(0); adj[1].add(3);
Pros: O(V + E) space
Cons: Edge lookup is O(degree)
For most applications, use adjacency lists.
Breadth-First Search (BFS)
BFS explores level by level - all neighbors of start, then all neighbors of those, etc.
void bfs(Graph g, int start) {
boolean[] visited = new boolean[g.n];
Queue<Integer> q = new LinkedList<>();
q.add(start);
visited[start] = true;
while (!q.isEmpty()) {
int u = q.poll();
System.out.println(u);
for (int v : g.adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.add(v);
}
}
}
}
Time: O(V + E), Space: O(V)
BFS Finds Shortest Paths in Unweighted Graphs
Track parents during BFS:
int[] bfs(int start, int goal) {
int[] parent = new int[g.n];
Arrays.fill(parent, -1);
parent[start] = start;
Queue<Integer> q = new LinkedList<>();
q.add(start);
while (!q.isEmpty()) {
int u = q.poll();
if (u == goal) break;
for (int v : g.adj[u]) {
if (parent[v] == -1) {
parent[v] = u;
q.add(v);
}
}
}
if (parent[goal] == -1) return null;
List<Integer> path = new ArrayList<>();
for (int cur = goal; cur != start; cur = parent[cur]) {
path.add(cur);
}
path.add(start);
Collections.reverse(path);
return path.stream().mapToInt(i -> i).toArray();
}
Depth-First Search (DFS)
DFS goes as deep as possible before backtracking.
Recursive:
void dfs(Graph g, int u, boolean[] visited) {
visited[u] = true;
System.out.println(u);
for (int v : g.adj[u]) {
if (!visited[v]) dfs(g, v, visited);
}
}
Iterative (with explicit stack):
void dfsIter(Graph g, int start) {
boolean[] visited = new boolean[g.n];
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int u = stack.pop();
if (visited[u]) continue;
visited[u] = true;
System.out.println(u);
for (int v : g.adj[u]) {
if (!visited[v]) stack.push(v);
}
}
}
Time: O(V + E)
Connected Components
int countComponents(Graph g) {
boolean[] visited = new boolean[g.n];
int count = 0;
for (int u = 0; u < g.n; u++) {
if (!visited[u]) {
dfs(g, u, visited);
count++;
}
}
return count;
}
Cycle Detection
Undirected: DFS with parent tracking
boolean hasCycle(Graph g, int u, int parent, boolean[] visited) {
visited[u] = true;
for (int v : g.adj[u]) {
if (!visited[v]) {
if (hasCycle(g, v, u, visited)) return true;
} else if (v != parent) {
return true;
}
}
return false;
}
Directed: DFS with three colors (white/gray/black). Cycle exists if we see a gray node.
Topological Sort
For a DAG (directed acyclic graph), produce a linear ordering where every edge goes from earlier to later.
Kahn's algorithm (BFS-based):
List<Integer> topologicalSort(Graph g) {
int[] inDegree = new int[g.n];
for (int u = 0; u < g.n; u++) {
for (int v : g.adj[u]) inDegree[v]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < g.n; i++) if (inDegree[i] == 0) q.add(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : g.adj[u]) {
if (--inDegree[v] == 0) q.add(v);
}
}
if (order.size() != g.n) throw new RuntimeException("Cycle detected");
return order;
}
Applications: build systems (Make), course prerequisites, package managers (npm, pip).
Key Takeaways
- Adjacency list: O(V+E) space, most common
- BFS uses a queue - finds shortest paths in unweighted graphs
- DFS uses a stack - natural for cycles, topological sort
- Both O(V+E) time
- Topological sort orders DAGs; fails if cycle exists
📝 Problem Set 1: Arrays and Linked Lists
Q1. Implement an `ArrayList` in Java with methods `add(int)`, `get(int)`, `size()`. Explain the amortized cost of `add` when doubling capacity.
Show Solution
Amortized O(1): each doubling costs O(n), but happens only every n inserts. Sum over n inserts = n + n/2 + n/4 + ... = 2n operations = O(n) total = O(1) amortized per insert.
Q2. Compare ArrayList vs LinkedList for the operations: get(i), add at end, add at beginning, remove at beginning. Give Big-O for each.
Show Solution
ArrayList: get O(1), add end O(1) amortized, add begin O(n), remove begin O(n). LinkedList: get O(n), add end O(1) (with tail pointer), add begin O(1), remove begin O(1).
🎯 Midterm 1: Arrays, Lists, Trees
Q1. Given a binary search tree with values 5, 3, 7, 1, 4, 6, 8, draw the tree and give its in-order, pre-order, and post-order traversals.
Show Solution
Tree: 5 is root, 3 left, 7 right, 1 left of 3, 4 right of 3, 6 left of 7, 8 right of 7. In-order: 1 3 4 5 6 7 8. Pre-order: 5 3 1 4 7 6 8. Post-order: 1 4 3 6 8 7 5.
Q2. What is the worst-case time complexity for insert in an unbalanced BST? Why?
Show Solution
O(n). If the BST becomes a linked list (e.g., insert 1, 2, 3, 4, 5 in that order), each insert traverses from root to leaf.
Q3. Implement a hash table with chaining in pseudocode. What is the average-case lookup time?
Show Solution
Array of buckets (linked lists). hash(key) gives bucket index; search scans that bucket. Average O(1 + load_factor), typically O(1) if load_factor < 1. Worst-case O(n) if all keys hash to same bucket.
Q4. Explain the difference between a heap and a BST. Give one use case for each.
Show Solution
Heap: parent is always smaller (or larger) than children. Structure is complete binary tree. O(log n) insert, O(1) peek-min. No ordering between siblings. Use case: priority queue. BST: left < node < right. O(log n) insert/search (if balanced). In-order traversal gives sorted sequence. Use case: ordered dictionary.