Stage 5: Data structures and algorithms, lesson 3 of 5

Linked lists, stacks and queues

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

A linked list stores nodes that point to the next node. Inserting or removing at a known node is O(1), but reaching position i is O(n).

A stack is last in, first out: undo, the browser's back button, matching brackets. A queue is first in, first out: print jobs, breadth-first search, task queues. In Java, ArrayDeque implements both.

Classic interview problems:

  • Reverse a linked list with three pointers.
  • Detect a cycle with fast and slow pointers (Floyd's algorithm).
  • Find the middle node: the fast pointer moves two steps for every one.
  • Check balanced brackets with a stack.

Build these yourself once to understand them; in production, use the JDK's collections.

Example

Java
class Node {
    int value;
    Node next;
    Node(int value, Node next) { this.value = value; this.next = next; }
}

static Node reverse(Node head) {
    Node prev = null, current = head;
    while (current != null) {
        Node next = current.next;      // save the rest of the list first
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

static boolean hasCycle(Node head) {              // Floyd: tortoise and hare
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

static boolean balanced(String s) {               // a stack of open brackets
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if ("([{".indexOf(c) >= 0) stack.push(c);
        else if (")]}".indexOf(c) >= 0) {
            if (stack.isEmpty() || "([{".indexOf(stack.pop()) != ")]}".indexOf(c)) return false;
        }
    }
    return stack.isEmpty();
}
System.out.println(balanced("{[()()]}"));          // true

Common mistake

Losing the rest of the list while reversing it by overwriting current.next before saving it. Always keep a reference to the next node first.

Under the hood

Java's LinkedList is doubly linked and implements both List and Deque, but every node is a separate object scattered in memory, so iterating it is much slower than ArrayList or ArrayDeque in practice. Linked structures still matter conceptually: HashMap buckets, LinkedHashMap's ordering and many concurrent queues use linked nodes.

Check yourself

Which data structure checks balanced brackets?

How this connects

Where this leads

Part of Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.