Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsJunior20 min read

Linear data structures: arrays, linked lists, stacks and queues

Review 16 cards
On this page

Data structures series: 1. Arrays, linked lists, stacks, queues · 2. List, Set, Map · 3. TreeMap, Comparator, iterators · 4. Inside ArrayList and HashMap

A data structure is a way of organizing data in memory together with the operations it supports (insert, update, delete, search). Pick the wrong one and your code is still correct, but it can be hundreds of times slower once the data grows. After this post you can explain how arrays, linked lists, stacks and queues sit in memory, what each operation costs and when to pick which.

If O(1) and O(n) aren’t familiar yet, skim Big-O first. Parts 2 and 3 move on to the Java Collections Framework API (List, Set and Map, then TreeMap, Comparator and iterators); part 4 opens up the JDK to show how ArrayList, ArrayDeque and HashMap really work.

1. Arrays

Key idea: an array is a sequence of elements of the same type, in order, stored in adjacent memory cells. Because the cells are adjacent, index access is O(1).

Say you need the sum of 10 numbers: declaring ten variables a0, a1, … doesn’t scale; one array does. The address of element i is just base + i * elementSize.

int[] scores = new int[10];          // 10 elements, all default to 0
for (int i = 0; i < scores.length; i++) {
    scores[i] = i * 10;
}
int sum = 0;
for (int s : scores) sum += s;

1.1. Static vs dynamic arrays

Static array Dynamic array
Size Fixed once created Grows automatically when full
Java example int[], String[] ArrayList<E>
How it works One contiguous block Wraps a static array; when full, allocates a bigger one and copies over

2. Linked lists

Key idea: each element is a separate node that can live anywhere in memory, linked to the next by a reference. Insert/delete is just rewiring references; the price is losing index access.

It fixes two weak spots of arrays:

  1. An array needs one contiguous block big enough for everything. For very large data that can be hard to get.
  2. Inserting or deleting in the middle of an array means shifting everything after that point.

A node has two parts: the value (data) and a reference (next) to the following node. The list keeps a head (first node), usually a tail (last node), and a size.

flowchart LR
  H([head]) --> A
  A["data: 10 | next"] --> B["data: 20 | next"]
  B --> C["data: 30 | next"]
  C --> N((null))
  T([tail]) --> C

2.1. Singly vs doubly linked lists

  • Singly linked list: each node points only to the next one. You can only walk forward, from head to tail.
  • Doubly linked list: each node points to both the previous (prev) and the next node. You can walk both ways and unlink a known node in O(1), at the cost of one extra reference per node.

java.util.LinkedList is a doubly linked list.

Circular variants: circular and circular doubly linked lists
  • Circular linked list: the last node points back to the first. Handy for round-robin scheduling.
  • Circular doubly linked list: combines both. The last node’s next points to the first node and the first node’s prev points to the last, so you can loop around in either direction and reach every node from any node.
  • It fits playlists (next/previous track, wrapping around at the end), round-robin scheduling, and an LRU cache built around a single sentinel: sentinel.next is the most recently used entry, sentinel.prev the one to evict.

2.2. Basic operations

  • get(index): walk from head one node at a time, so O(n).
  • insert(index, value): find the node before that position (O(n)), then rewire two references (O(1)). Inserting at the head is O(1); at the tail it’s O(1) if you keep a tail pointer.
  • delete(index): find the node before it and make it “skip over” the removed node. Removing the head is O(1). Removing the tail of a singly linked list is still O(n), even with a tail pointer, because you need the second-to-last node.
flowchart LR
  subgraph "Insert X between A and B"
    A1[A] -. "old next" .-> B1[B]
    A1 -- "1. A.next = X" --> X1[X]
    X1 -- "2. X.next = B" --> B1
  end

The order of assignments matters: grab A.next (that is, B) before you overwrite it, or you lose the rest of the list.

2.3. Array vs linked list

2.4. Sentinel nodes and doubly linked list operations

When you write your own linked list, most bugs hide in the edge cases (the empty list, inserting at the front, removing the last element), each with its own if (head == null).

A sentinel node (also called a dummy node) is a fake node that holds no real data and always exists, even when the list is empty. With a sentinel head and a sentinel tail, every real element sits between them, so every real node has a non-null prev and next. Insert and delete then run the same code path. Think of the two bookends on a shelf: every book has a neighbour on both sides.

The slides’ example: a list holding 2 (index 0) and 3 (index 1), framed by two sentinels with value 0 (the value doesn’t matter, nobody reads it).

flowchart LR
  H["head (sentinel)"] <--> A["2 (index 0)"]
  A <--> B["3 (index 1)"]
  B <--> T["tail (sentinel)"]

The three operations on a doubly linked list with sentinels:

  • get(i): if i < size/2, walk forward from head.next; otherwise walk backward from tail.prev. At most size/2 steps: still O(n), but twice as fast.
  • insert(i, v): let succ be the node currently at position i (or the tail sentinel when i == size) and pred = succ.prev. Create the node and set four references: node.prev, node.next, pred.next, succ.prev.
  • delete(i): take the node at position i, pred = node.prev, succ = node.next, then pred.next = succ; succ.prev = pred;. Once you hold the node it’s O(1); unlike a singly list you don’t have to hunt for the previous node.
Full MyDoublyLinkedList code with two sentinels, a walk-through of each operation and a test run

Examples on the slides’ list 2 ⇄ 3:

  • get(1): one step back from the tail sentinel.
  • insert(1, 5): pred is 2, succ is 3, and you get 2 ⇄ 5 ⇄ 3.
  • delete(1) (node 3) from 2 ⇄ 3: node 2 links straight to the tail sentinel.
public class MyDoublyLinkedList {
    private static final class Node {
        int val;
        Node prev, next;
        Node(int val) { this.val = val; }
    }

    private final Node head = new Node(0); // sentinel, holds no real data
    private final Node tail = new Node(0); // sentinel
    private int size;

    public MyDoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    // Walk from whichever end is closer: at most size/2 steps.
    private Node node(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
        if (index < size / 2) {
            Node cur = head.next;
            for (int i = 0; i < index; i++) cur = cur.next;
            return cur;
        }
        Node cur = tail.prev;
        for (int i = size - 1; i > index; i--) cur = cur.prev;
        return cur;
    }

    public int get(int index) { return node(index).val; }

    // index == size means append. No special case for empty list, head or tail.
    public void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
        Node succ = (index == size) ? tail : node(index);
        Node pred = succ.prev;
        Node n = new Node(value);
        n.prev = pred;
        n.next = succ;
        pred.next = n;
        succ.prev = n;
        size++;
    }

    public int delete(int index) {
        Node n = node(index);
        Node pred = n.prev, succ = n.next;
        pred.next = succ;
        succ.prev = pred;
        n.prev = n.next = null; // drop stale links: helps GC and prevents misuse
        size--;
        return n.val;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node cur = head.next; cur != tail; cur = cur.next) {
            if (cur != head.next) sb.append(", ");
            sb.append(cur.val);
        }
        return sb.append(']').toString();
    }
}

A quick run: insert(0, 2); insert(1, 3) gives [2, 3] and get(1) returns 3; insert(1, 5) gives [2, 5, 3]; delete(2) returns 3 and leaves [2, 5]; deleting everything and then calling insert(0, 7) still works, with no “empty list” branch anywhere.

Sentinels vs null, and java.util.LinkedList internals

3. Stacks

Key idea: a stack is LIFO (Last In, First Out): the last element pushed is the first one out, like a pile of plates. You can only touch the top.

Operation Meaning Complexity
push(x) Put x on top O(1)
pop() Remove and return the top O(1)
peek() Return the top without removing it O(1)
isEmpty() Is the stack empty? O(1)
isFull() Is it full? (only meaningful for a bounded stack) O(1)
size() Number of elements O(1)

Typical uses: the function call stack, undo/redo, bracket matching, infix-to-postfix conversion, DFS, the browser’s Back button.

Limitation: a stack has no random access. Conceptually there is no “i-th element” to loop over with an index; to look at everything you pop until it’s empty:

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");
while (!stack.isEmpty()) {
    System.out.println(stack.pop());   // c, b, a
}

Note: because java.util.Stack extends Vector, it actually does have get(i). That’s a design flaw, covered in part 4 of this series.

4. Queues

Key idea: a queue is FIFO (First In, First Out): first come, first served, like a line at a ticket counter. You add at the rear and remove from the front.

Operation Meaning Complexity
enqueue(x) Add x at the rear O(1)
dequeue() Remove and return the front O(1)
peek() Look at the front without removing it O(1)
size() Number of elements O(1)

Typical uses: BFS, job queues, buffers between producers and consumers, message brokers (Kafka and RabbitMQ are “queues” at the system level), thread pools (ThreadPoolExecutor is built around a BlockingQueue).

Like a stack, a queue doesn’t support random access; you process it one element at a time.

Interactive visualisations

Key idea: these animation pages (from Y. Daniel Liang’s textbook) show every step, so they’re worth clicking through while you review.

Exercises

Exercises 1 and 2: Stack and queue quizzes

Stack: create an empty stack, push 18, 2, 6; pop and print; push 17; pop and print; print peek; print size.

Queue: enqueue 11, 2, 16; dequeue and print; enqueue 17; dequeue and print; print peek; print size.

Solution to exercises 1 and 2: step by step

Stack:

  • After three pushes: [18, 2, 6] (6 on top). Pop → 6.
  • Push 17: [18, 2, 17]. Pop → 17.
  • Peek → 2. Size → 2.
  • Answer: 6, 17, 2, 2, i.e. option B.

Queue:

  • After three enqueues: [11, 2, 16] (11 at the front). Dequeue → 11.
  • Enqueue 17: [2, 16, 17]. Dequeue → 2.
  • Peek → 16. Size → 2.
  • Answer: 11, 2, 16, 2, i.e. option C.

I re-ran both with ArrayDeque to double-check.

Exercise 3: Reverse a string with a stack

Write reverse(String s) that reverses a string using a stack. This is LIFO practice; in real code just use new StringBuilder(s).reverse().

Solution to exercise 3 and the emoji trap
static String reverse(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) stack.push(c);
    StringBuilder sb = new StringBuilder(s.length());
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.toString();
}

Exercise 4: Print numbers in input order with a queue

Read n, then n integers, and use a queue to print them back in the order they were entered.

Solution to exercise 4
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) queue.offer(in.nextInt());
while (!queue.isEmpty()) System.out.print(queue.poll() + " ");

FIFO, so the output order matches the input order.

Exercise 5: Check that brackets are balanced

Task: given a string with (), [], {} mixed with other characters, check that every bracket is closed by the right kind, in the right order. For example "([]{})" is balanced; "(]", "(()", "())" and "}{" are not. It’s the classic stack interview question.

Solution to exercise 5: isBalanced with a stack, complexity and the single-bracket variant

The idea: push every opening bracket; a closing bracket must match the most recent bracket that’s still open, which is exactly the top of the stack (LIFO).

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
            case '(', '[', '{' -> stack.push(c);
            case ')', ']', '}' -> {
                if (stack.isEmpty()) return false;            // closing with nothing open: "())"
                if (stack.pop() != matching(c)) return false; // wrong kind: "(]"
            }
            default -> { }                                     // ignore other characters
        }
    }
    return stack.isEmpty();                                    // something left open: "(()"
}

private static char matching(char close) {
    return switch (close) {
        case ')' -> '(';
        case ']' -> '[';
        default -> '{';
    };
}
// "" -> true, "([]{})" -> true, "if (a[i] == b) { x(); }" -> true
// "(]" -> false, "(()" -> false, "())" -> false, "}{" -> false
  • O(n) time and, in the worst case (all opening brackets), O(n) memory.
  • The three false branches catch three different kinds of mistakes, so in an interview, say out loud which branch catches what.
  • With only one kind of bracket you don’t need a stack at all: a depth counter is enough (increment on (, decrement on ), fail if it goes negative).

I ran the solution against the 8 strings above.

Remember

  • Explain why reading the i-th element is O(1) for an array but O(n) for a linked list.
  • Know when insert/delete on a linked list is really O(1), and why removing the tail of a singly list is still O(n).
  • Explain why ArrayList usually beats LinkedList despite the same Big-O.
  • Name the four references you set when inserting into a doubly linked list, and which branches sentinels remove.
  • Know whether a problem needs a stack or a queue (brackets, DFS, BFS, job queues).

Interview questions

Junior

What’s the difference between an array and an ArrayList?

An array has a fixed length and can hold primitives; an ArrayList is a dynamic array that grows on its own and only holds objects.

ArrayList wraps an Object[], so int gets boxed to Integer. In return it is generic and comes with lots of convenience methods.

How do a stack and a queue differ? Give a use case for each.

A stack is LIFO and you only work at the top; a queue is FIFO, adding at the rear and removing at the front.

Stack: call stacks, undo, bracket matching, DFS. Queue: BFS, job queues, producer/consumer buffers.

Why is reading the i-th element O(1) for an array but O(n) for a linked list?

An array is contiguous, so the address is just base + i * size; a linked list has no address formula.

With a linked list you follow next from head through i nodes.

What’s the difference between a singly and a doubly linked list?

A singly linked node only has next; a doubly linked node also has prev, so you can walk both ways and removing a node you hold is O(1).

A singly list only walks forward, and to remove a node you need the node before it; removing the last element is still O(n) even with a tail. A doubly list removes the last one in O(1), at the price of one extra reference per node. java.util.LinkedList is doubly linked.

Mid

What’s the difference between offer/poll/peek and add/remove/element?

offer/poll/peek report failure through the return value (false/null); add/remove/element throw.

The exceptions are IllegalStateException (full) and NoSuchElementException (empty). Use the first group when a bounded queue or an empty queue is a normal situation.

How do you build a queue out of two stacks, and what does it cost?

Use an in stack to receive and an out stack to hand out; when out is empty, pour all of in into out. The amortized cost is O(1) per operation.

offer pushes onto in. When you poll and out is empty, pour everything from in into out; pouring reverses the order, so the top of out is the oldest element. A single poll can cost O(n), but every element moves from in to out exactly once. The question checks that you understand LIFO versus FIFO and amortized analysis.

What is a sentinel (dummy) node and why does it simplify linked list code?

A sentinel is a fake node that holds no real data and always exists, so every real node has a non-null prev and next and insert/delete become a single code path.

Insert is pred.next = node; succ.prev = node, delete is pred.next = succ; succ.prev = pred. There are no separate branches for the empty list, the first element or the last element. The cost is one or two extra nodes and remembering to stop traversals at cur != tail. A real-world use: a hand-written LRU cache built from a HashMap plus a doubly linked list with sentinels.

Senior

Why can cache locality matter more than Big-O?

Because Big-O ignores constants, and a cache miss costs around 100 ns versus about 1 ns for an L1 hit.

Scanning a contiguous array uses whole 64-byte cache lines and the prefetcher; walking a linked list is pointer chasing where each step can miss. That’s why ArrayList’s O(n) middle insert (one contiguous arraycopy) often beats the O(n) walk to the insertion point in a LinkedList, even though both are O(n).

Useful phrases for interviews

  • “The main trade-off here is random access versus cheap insertion: arrays give you O(1) reads, linked lists give you O(1) inserts once you have the node.”
  • “On paper both are O(n), but in practice the array wins because of cache locality.”
  • “I’d default to ArrayList and only switch if profiling shows a real problem.”
  • “A singly linked list can only walk forward, so deleting the tail is still linear even if I keep a tail pointer.”
  • “A closing bracket has to match the most recent one that’s still open, and that’s exactly what a stack gives me.”
  • “Each element is moved between the two stacks at most once, so the queue is amortized O(1).”
  • “The array’s strength is that the address of element i is just arithmetic: base plus i times the element size.”
  • “Stacks and queues trade random access for a narrow interface: you only touch the ends.”
  • “I’d put sentinel nodes at both ends, so every real node has neighbours and insert and delete need no null checks.”

Notes based on the Fundamentals of Backend course (Ronin Engineer) and the Hỏi Dân IT Java Core material, plus my own research, rewritten in my own words.