SyntaxPilot
Courses/Java/Lesson 48
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Java · Lesson 48 of 51

DSA 2: linked lists, stacks, queues, trees, graphs

queued

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
  • ArrayDeque is the recommended stack (and queue) in Java; the old Stack class 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/pop is 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.

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

  1. Reverse a linked list of coaches.
  2. Undo/redo with two stacks.
  3. Count the leaves of a BST.
  4. 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

  1. 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.
  2. Stack vs queue? LIFO vs FIFO. Stacks: undo, brackets, recursion, DFS. Queues: scheduling, buffering, BFS.
  3. Which class for a stack or queue in Java? ArrayDeque.
  4. What makes a BST a BST? Every node's left subtree holds smaller values and its right subtree bigger values.
  5. 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.
  6. 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).
  7. 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.
  8. Adjacency list vs adjacency matrix? List: O(V + E) space, good for sparse graphs. Matrix: O(V²) space, O(1) edge lookup.
  9. 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; walk while (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/TreeSet balance 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.