These are the notes for Java episode 48, part 2 of the DSA series. A data structure is a way to arrange data so that some operation becomes fast. We meet five problems arrays handle badly and invent the structure that fixes each: coaches joining a train at the front (linked list), brackets that must close in order (stack), a fair token line (queue), finding a price by asking "less or more?" (binary search tree), and the fewest hops across a colony map (graph and breadth-first search). Every example was run with javac 21.
Timings depend on the machine. The outputs below are real runs; your millisecond numbers will differ.
Linked lists
Real-life problem: coaches joining at the front. An ArrayList stores items like an array: one block of slots side by side in memory. Adding at the front means every other item shifts back one slot.
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 200_000; // coaches added at the FRONT
long t0 = System.currentTimeMillis();
List<Integer> array = new ArrayList<>();
for (int i = 0; i < n; i++) array.add(0, i); // shift everything right, every time
long t1 = System.currentTimeMillis();
LinkedList<Integer> linked = new LinkedList<>();
for (int i = 0; i < n; i++) linked.addFirst(i); // just relink the front
long t2 = System.currentTimeMillis();
System.out.println("ArrayList add(0, x): " + (t1 - t0) + " ms");
System.out.println("LinkedList addFirst(x): " + (t2 - t1) + " ms");
}
}
Output (one run):
ArrayList add(0, x): 1837 ms
LinkedList addFirst(x): 31 ms
Each add(0, x) on an ArrayList is O(n) (shift everything), so 2 lakh of them are O(n²). LinkedList.addFirst is O(1).
Real-life example: coaches joined by couplings.
| On the railway | In Java | Meaning |
|---|---|---|
| a coach | node | a small object holding one item of data |
| the coupling to the next coach | next |
a reference to the next node |
| the last coach, nothing behind | next = null |
the end of the list |
| the engine at the front | head | the first node; the list is reached through it |
class Coach {
String name;
Coach next; // the coupling to the next coach
Coach(String name, Coach next) { this.name = name; this.next = next; }
}
public class Main {
public static void main(String[] args) {
Coach train = new Coach("S1", new Coach("S2", new Coach("S3", null)));
train = new Coach("Engine", train); // add at the front: O(1)
for (Coach c = train; c != null; c = c.next)
System.out.print(c.name + " -> ");
System.out.println("end");
}
}
Output:
Engine -> S1 -> S2 -> S3 -> end
Adding at the front creates one node whose next is the old head: nothing moves. Walking ("traversing") the list follows next until null. The price: there is no index. Reaching the 100th node means walking past 99 others: O(n). Java's LinkedList is a doubly linked list (each node also links to the previous one), so it is O(1) at both ends.
Walking off the end
class Coach {
String name;
Coach next;
Coach(String name, Coach next) { this.name = name; this.next = next; }
}
public class Main {
public static void main(String[] args) {
Coach train = new Coach("Engine", new Coach("S1", new Coach("S2", null)));
Coach c = train;
for (int i = 0; i < 4; i++) { // 4 steps, but only 3 coaches
System.out.println("At " + c.name);
c = c.next;
}
}
}
Output:
At Engine
At S1
At S2
Exception in thread "main" java.lang.NullPointerException: Cannot read field "name" because "<local2>" is null
at Main.main(Main.java:12)
After S2, c became null, and null has no name. <local2> is how Java names the local variable c when the class is compiled without debug names (javac -g keeps the real names). Fix: loop while (c != null), never a fixed count.
Stacks
The obvious way: count the brackets
public class Main {
static boolean balanced(String s) {
int open = 0, close = 0;
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') open++;
else close++;
}
return open == close;
}
public static void main(String[] args) {
for (String s : new String[]{"([]{})", "(]", "([)]"})
System.out.println(s + " balanced? " + balanced(s));
}
}
Output:
([]{}) balanced? true
(] balanced? true
([)] balanced? true
All three say true, but (] and ([)] are not balanced. Counting ignores the order: the last bracket opened must be the first one closed.
Real-life example: plates and a token line.
| In the kitchen | In Java | Meaning |
|---|---|---|
| a stack of plates: put on top, take from the top | stack, LIFO | last in, first out: push, pop, peek |
| undo in an editor: the last change goes first | stack uses | undo, brackets, the method call stack |
| the chai token line: first come, first served | queue, FIFO | first in, first out: offer, poll, peek |
import java.util.*;
public class Main {
static boolean balanced(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') stack.push(ch); // remember the opener
else {
if (stack.isEmpty()) return false;
char open = stack.pop(); // the LAST opener
if ("([{".indexOf(open) != ")]}".indexOf(ch)) return false; // must match
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
for (String s : new String[]{"([]{})", "(]", "([)]", "(("})
System.out.println(s + " balanced? " + balanced(s));
}
}
Output:
([]{}) balanced? true
(] balanced? false
([)] balanced? false
(( balanced? false
ArrayDequeis the recommended stack (and queue) in Java; the oldStackclass is synchronized and slower (episode 33)."([{".indexOf(open) != ")]}".indexOf(ch): the opener and closer must sit at the same position in the two strings.- Every
push/popis O(1), so the check is O(n) time, O(n) space for the stack.
Queues
A queue is first in, first out, like a token line. With Deque<String> q = new ArrayDeque<>():
| Method | Meaning | If empty |
|---|---|---|
offer(x) |
add at the back | |
poll() |
remove from the front | returns null |
peek() |
look at the front | returns null |
Queues power breadth-first search (below), task schedulers and print queues. PriorityQueue (episode 33) serves the smallest item first instead of the oldest.
Binary search trees
Real-life problem: twenty questions about a price. Checking a list item by item is O(n). Asking "less or more than 150?" throws away half the items each time.
| Term | Meaning |
|---|---|
| tree | nodes connected in levels, with no loops |
| root | the top node |
| child / parent | a node directly below / above another |
| leaf | a node with no children |
| binary tree | each node has up to two children, left and right |
| binary search tree (BST) | for every node: smaller values in the left subtree, bigger in the right |
| height | the number of levels from the root to the deepest node |
class Node { int price; Node left, right; Node(int p) { price = p; } } // smaller left, bigger right
public class Main {
static Node insert(Node n, int p) {
if (n == null) return new Node(p); // empty spot: put it here
if (p < n.price) n.left = insert(n.left, p); // smaller: go left
else n.right = insert(n.right, p); // bigger: go right
return n;
}
static void inOrder(Node n) { // left, me, right
if (n == null) return;
inOrder(n.left); System.out.print(n.price + " "); inOrder(n.right);
}
public static void main(String[] args) {
Node root = null;
for (int p : new int[]{150, 60, 300, 40, 120, 200, 350}) root = insert(root, p);
inOrder(root);
}
}
Output:
40 60 120 150 200 300 350
In-order traversal (left, node, right) of a BST always prints the values sorted. Searching walks down one path, so it takes at most height steps.
The trap: sorted input
class Node { int price; Node left, right; Node(int p) { price = p; } }
public class Main {
static Node insert(Node n, int p) {
if (n == null) return new Node(p);
if (p < n.price) n.left = insert(n.left, p); else n.right = insert(n.right, p);
return n;
}
static int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }
public static void main(String[] args) {
Node mixed = null, sorted = null;
for (int p : new int[]{150, 60, 300, 40, 120, 200, 350}) mixed = insert(mixed, p);
for (int p = 1; p <= 7; p++) sorted = insert(sorted, p * 50); // already sorted!
System.out.println("height, mixed order: " + height(mixed));
System.out.println("height, sorted order: " + height(sorted));
}
}
Output:
height, mixed order: 3
height, sorted order: 7
Inserting already-sorted values sends every new value right: the tree becomes a linked list leaning right, and search is O(n) again. Self-balancing trees fix this by rotating nodes to keep the height near log n: Java's TreeMap and TreeSet (episodes 31 and 32) are red-black trees, with O(log n) search, insert and remove.
Graphs and breadth-first search
Real-life problem: the fewest stops across the colony. Places joined by roads in any pattern form a graph: places are vertices (nodes), roads are edges. Roads that go both ways make an undirected graph; one-way streets would make it directed.
An adjacency list stores a graph as a map from each vertex to the list of its neighbours.
import java.util.*;
public class Main {
public static void main(String[] args) {
String roads = "Home-Market Home-School Market-Temple School-Park Temple-Park Park-Station";
Map<String, List<String>> map = new HashMap<>(); // stop -> neighbours
for (String r : roads.split(" ")) {
String[] ab = r.split("-"); // roads go both ways
map.computeIfAbsent(ab[0], k -> new ArrayList<>()).add(ab[1]);
map.computeIfAbsent(ab[1], k -> new ArrayList<>()).add(ab[0]);
}
Map<String, Integer> hops = new HashMap<>(Map.of("Home", 0));
Deque<String> queue = new ArrayDeque<>();
for (String here = "Home"; here != null; here = queue.poll()) // next in line
for (String next : map.get(here))
if (hops.putIfAbsent(next, hops.get(here) + 1) == null) queue.offer(next);
System.out.println("Home to Station: " + hops.get("Station") + " hops");
}
}
Output:
Home to Station: 3 hops
Breadth-first search (BFS) explores in ripples: everything 1 hop away, then 2 hops, and so on. The queue (FIFO) makes vertices come out in order of distance, so the first time we reach a place is the fewest hops. hops.putIfAbsent(...) returns null only for a place not seen yet, which is the visited check; without it, the search would bounce between neighbours forever. queue.poll() returns null when the queue is empty, which ends the for loop. Time: O(V + E) (every vertex and edge once).
The other classic traversal, depth-first search (DFS), goes as deep as possible first (using recursion or a stack). It's good for "is there any path?", cycles and mazes, but doesn't give the fewest hops.
Big-O of each structure
| Structure | Fast | Slow |
|---|---|---|
array / ArrayList |
get by index O(1), add at end O(1) on average | insert/remove at front O(n), search O(n) |
| linked list | add/remove at front (and back, if doubly linked) O(1) | get by index O(n), search O(n) |
stack / queue (ArrayDeque) |
push/pop, offer/poll O(1) | search O(n) |
balanced BST (TreeMap) |
search/insert/remove O(log n), sorted order | |
hash table (HashMap) |
get/put O(1) on average | no order |
| graph BFS | fewest hops, O(V + E) |
Pick the structure that makes your main operation fast.
Common mistakes (and what you see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| a fixed number of steps along a linked list | java.lang.NullPointerException: Cannot read field "name" because "<local2>" is null |
walked past the last node | while (c != null) |
| counting brackets | no error: ([)] balanced? true, which is wrong |
order matters | a stack |
pop() on an empty ArrayDeque |
java.util.NoSuchElementException |
nothing to pop | check isEmpty() first (or use poll()) |
| sorted data into a plain BST | no error: height 7 instead of 3, slow searches | the tree became a list | TreeMap / TreeSet |
| BFS without a visited check | no error: the program never ends | roads go both ways | skip places already seen |
ArrayList.add(0, x) in a loop |
no error: seconds of work | O(n) shift each time | ArrayDeque.addFirst / LinkedList |
Mini project: print the route, not just the hop count
BFS can also remember where each place was reached from. Walking those links back from the station gives the route.
import java.util.*;
public class Main {
public static void main(String[] args) {
String roads = "Home-Market Home-School Market-Temple School-Park Temple-Park Park-Station";
Map<String, List<String>> map = new HashMap<>();
for (String r : roads.split(" ")) {
String[] ab = r.split("-");
map.computeIfAbsent(ab[0], k -> new ArrayList<>()).add(ab[1]);
map.computeIfAbsent(ab[1], k -> new ArrayList<>()).add(ab[0]);
}
Map<String, String> cameFrom = new HashMap<>(); // place -> the place we reached it from
cameFrom.put("Home", null);
Deque<String> queue = new ArrayDeque<>(List.of("Home"));
while (!queue.isEmpty()) {
String here = queue.poll();
for (String next : map.get(here))
if (!cameFrom.containsKey(next)) { cameFrom.put(next, here); queue.offer(next); }
}
LinkedList<String> route = new LinkedList<>();
for (String at = "Station"; at != null; at = cameFrom.get(at)) route.addFirst(at); // walk back
System.out.println("Route: " + String.join(" -> ", route));
}
}
Output:
Route: Home -> School -> Park -> Station
addFirst on a LinkedList builds the route in the right order while we walk backwards.
Practice
- Reverse a linked list of coaches.
- Undo/redo with two stacks.
- Count the leaves of a BST.
- BFS: list every place exactly 2 hops from home.
Solution 1
class Coach {
String name; Coach next;
Coach(String name, Coach next) { this.name = name; this.next = next; }
}
public class Main {
static Coach reverse(Coach head) {
Coach prev = null;
while (head != null) {
Coach next = head.next; // remember the rest of the train
head.next = prev; // turn this coupling around
prev = head;
head = next;
}
return prev;
}
public static void main(String[] args) {
Coach train = new Coach("Engine", new Coach("S1", new Coach("S2", new Coach("S3", null))));
for (Coach c = reverse(train); c != null; c = c.next) System.out.print(c.name + " -> ");
System.out.println("end");
}
}
Output:
S3 -> S2 -> S1 -> Engine -> end
Three references: prev, head and next. O(n) time, O(1) space.
Solution 2
import java.util.*;
public class Main {
static Deque<String> undo = new ArrayDeque<>(), redo = new ArrayDeque<>();
static String text = "";
static void type(String s) { undo.push(text); redo.clear(); text = text + s; }
static void undo() { if (!undo.isEmpty()) { redo.push(text); text = undo.pop(); } }
static void redo() { if (!redo.isEmpty()) { undo.push(text); text = redo.pop(); } }
public static void main(String[] args) {
type("Chai "); type("is "); type("hot");
System.out.println(text);
undo(); System.out.println(text);
undo(); System.out.println(text);
redo(); System.out.println(text);
}
}
Output:
Chai is hot
Chai is
Chai
Chai is
Typing pushes the old text on undo and clears redo; undo moves the current text to redo.
Solution 3
class Node { int price; Node left, right; Node(int p) { price = p; } }
public class Main {
static Node insert(Node n, int p) {
if (n == null) return new Node(p);
if (p < n.price) n.left = insert(n.left, p); else n.right = insert(n.right, p);
return n;
}
static int leaves(Node n) {
if (n == null) return 0;
if (n.left == null && n.right == null) return 1; // no children: a leaf
return leaves(n.left) + leaves(n.right);
}
public static void main(String[] args) {
Node root = null;
for (int p : new int[]{150, 60, 300, 40, 120, 200, 350}) root = insert(root, p);
System.out.println("Leaves: " + leaves(root));
}
}
Output:
Leaves: 4
The leaves are 40, 120, 200 and 350.
Solution 4
import java.util.*;
public class Main {
public static void main(String[] args) {
String roads = "Home-Market Home-School Market-Temple School-Park Temple-Park Park-Station";
Map<String, List<String>> map = new HashMap<>();
for (String r : roads.split(" ")) {
String[] ab = r.split("-");
map.computeIfAbsent(ab[0], k -> new ArrayList<>()).add(ab[1]);
map.computeIfAbsent(ab[1], k -> new ArrayList<>()).add(ab[0]);
}
Map<String, Integer> hops = new HashMap<>(Map.of("Home", 0));
Deque<String> queue = new ArrayDeque<>(List.of("Home"));
while (!queue.isEmpty()) {
String here = queue.poll();
for (String next : map.get(here))
if (hops.putIfAbsent(next, hops.get(here) + 1) == null) queue.offer(next);
}
List<String> two = new ArrayList<>();
hops.forEach((place, h) -> { if (h == 2) two.add(place); });
Collections.sort(two);
System.out.println("Exactly 2 hops from Home: " + two);
}
}
Output:
Exactly 2 hops from Home: [Park, Temple]
Quick quiz
Deque<Integer> s = new ArrayDeque<>();
s.push(1); s.push(2); s.push(3);
s.pop();
System.out.println(s.peek());
A. 1 B. 2 C. 3 D. null
Answer
B. 2. A stack is last in, first out: 3 is on top, pop removes it, and peek shows the new top, 2.
Interview questions
- Array vs linked list? Arrays: O(1) index access, contiguous memory, costly inserts in the middle/front. Linked lists: O(1) insert/remove at a known node, O(n) access by position, extra memory for links.
- Stack vs queue? LIFO vs FIFO. Stacks: undo, brackets, recursion, DFS. Queues: scheduling, buffering, BFS.
- Which class for a stack or queue in Java?
ArrayDeque. - What makes a BST a BST? Every node's left subtree holds smaller values and its right subtree bigger values.
- Why can a BST degrade to O(n)? Unbalanced insertion order (e.g. sorted data) makes it a chain; self-balancing trees (red-black, AVL) prevent this.
- In-order, pre-order, post-order? Left-node-right (sorted for a BST), node-left-right (copying a tree), left-right-node (deleting a tree).
- BFS vs DFS? BFS uses a queue and finds the fewest edges in an unweighted graph; DFS uses a stack/recursion and goes deep first.
- Adjacency list vs adjacency matrix? List: O(V + E) space, good for sparse graphs. Matrix: O(V²) space, O(1) edge lookup.
- How do you detect a cycle in a linked list? Two pointers at different speeds (Floyd's tortoise and hare): if they meet, there is a cycle.
Glossary
| Term | Meaning |
|---|---|
| Data structure | a way to arrange data so certain operations are fast |
| Linked list | nodes where each holds data and a reference to the next |
| Node | one element of a linked structure |
next |
the reference to the following node |
| Head | the first node of a linked list |
| Traverse | visit every element in turn |
| Doubly linked list | each node also links to the previous one |
NullPointerException |
using a field or method through a null reference |
| Stack | LIFO collection: push, pop, peek |
| LIFO | last in, first out |
| Queue | FIFO collection: offer, poll, peek |
| FIFO | first in, first out |
ArrayDeque |
Java's resizable double-ended queue, used as a stack or queue |
| Tree | nodes in levels with no loops |
| Root / leaf | the top node / a node with no children |
| Binary tree | each node has at most two children |
| Binary search tree | left subtree smaller, right subtree bigger |
| Height | levels from the root to the deepest node |
| In-order traversal | left subtree, node, right subtree |
| Balanced tree | height kept near log n |
| Red-black tree | the self-balancing tree inside TreeMap and TreeSet |
| Graph | vertices joined by edges |
| Vertex / edge | a place / a connection between two places |
| Directed / undirected | one-way / two-way edges |
| Adjacency list | a map from each vertex to its neighbours |
| BFS | breadth-first search: explore by distance, with a queue |
| DFS | depth-first search: go deep first, with recursion or a stack |
| Visited set | the places already seen, so they aren't processed again |
| O(V + E) | time proportional to vertices plus edges |
Summary
- Arrays: fast index, slow front inserts. Linked lists: nodes +
next, fast at the front, no index; walkwhile (c != null). - Stacks (LIFO) check brackets and power undo; queues (FIFO) keep things in arrival order. Use
ArrayDeque. - A BST keeps smaller left and bigger right: in-order is sorted, search is O(log n) if balanced. Sorted input makes a plain BST a list;
TreeMap/TreeSetbalance themselves. - A graph is vertices and edges, stored as an adjacency list. BFS with a queue and a visited check finds the fewest hops in O(V + E).
- Next episode: sorting, binary search and dynamic programming.