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:
- An array needs one contiguous block big enough for everything. For very large data that can be hard to get.
- 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
nextpoints to the first node and the first node’sprevpoints 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.nextis the most recently used entry,sentinel.prevthe one to evict.
2.2. Basic operations
- get(index): walk from
headone 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
tailpointer. - 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
tailpointer, 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 fromhead.next; otherwise walk backward fromtail.prev. At mostsize/2steps: still O(n), but twice as fast. - insert(i, v): let
succbe the node currently at positioni(or thetailsentinel wheni == size) andpred = succ.prev. Create the node and set four references:node.prev,node.next,pred.next,succ.prev. - delete(i): take the
nodeat positioni,pred = node.prev,succ = node.next, thenpred.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
tailsentinel. - insert(1, 5):
predis 2,succis 3, and you get2 ⇄ 5 ⇄ 3. - delete(1) (node 3) from
2 ⇄ 3: node 2 links straight to thetailsentinel.
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.StackextendsVector, it actually does haveget(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.
- ArrayList: https://liveexample.pearsoncmg.com/dsanimation13ejava/ArrayListeBook.html
- LinkedList: https://liveexample.pearsoncmg.com/dsanimation/LinkedListeBook.html
- Stack: https://liveexample.pearsoncmg.com/dsanimation/StackeBook.html
- Queue: https://liveexample.pearsoncmg.com/dsanimation/QueueeBook.html
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
falsebranches 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
depthcounter 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
ArrayListusually beatsLinkedListdespite 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.