Data structures series: 1. Arrays, linked lists, stacks, queues · 2. List, Set, Map · 3. TreeMap, Comparator, iterators · 4. Inside ArrayList and HashMap
Everyone knows how to use ArrayList and HashMap; senior interviews ask how they work inside the JDK. After this post you can explain what add costs when the array is full, why LinkedList and Stack are rarely right, how HashMap handles a crowded bucket, and you can build ArrayList and LinkedList yourself. Read part 1 (arrays, linked lists, stacks and queues as concepts), part 2 (the List, Set and Map APIs) and part 3 (TreeMap, Comparator, iterators) first.
1. Inside the JDK (what senior interviews ask about)
Key idea: each collection is a concrete data structure (array, circular array, linked list, hash table). Know the structure and you can derive the cost of every operation and its traps.
1.1. How ArrayList grows
Key idea: ArrayList is an array; when it’s full it allocates one ~1.5× bigger and copies over. Because growth is geometric, appending is O(1) amortized.
new ArrayList<>()does not allocate 10 slots right away. It points at a shared empty array; the firstaddcreates the real array with capacity 10. The slides’ “default is 10” is right about the number, but the allocation is lazy.- When full: new capacity =
old + (old >> 1)(≈ 1.5×), thenArrays.copyOfmoves the elements over. - Amortized means the average cost over a whole sequence of operations. Total copying over n appends is still O(n), so each append averages O(1). The one
addthat triggers a resize costs O(n): in latency-sensitive code that’s a visible spike. - If you know the size up front, say so:
new ArrayList<>(expectedSize)orensureCapacity(n)avoids repeated resizing. ArrayListis not thread-safe. For concurrent use, considerCollections.synchronizedList,CopyOnWriteArrayList(many reads, very few writes), or a design where the list isn’t shared.
ArrayList: trimToSize, remove and the fail-fast modCount
trimToSize()shrinks the backing array to exactlysizeto save memory.remove(index)shifts the later elements left withSystem.arraycopy, then sets the last slot tonullso the GC can reclaim the object. Forgetting thatnullis a textbook memory leak when you write your own data structure.ArrayListkeeps amodCountof structural changes. Its iterators check it to detect modification during iteration and throwConcurrentModificationException. That’s a fail-fast mechanism (fail early to expose a bug), not a synchronization mechanism: don’t rely on it for thread safety.- For lots of
ints, anArrayList<Integer>costs several times more than anint[]because of boxing (wrapping a primitive in an object; eachIntegeris ~16 bytes). Number-crunching code should use primitive arrays orIntStream.
1.2. LinkedList in the JDK
Key idea: LinkedList is a doubly linked list; index access is still O(n) and every element costs an extra node object. Its one real strength is O(1) insert/remove through a ListIterator already positioned there.
- It’s a doubly linked list (each node points to both the previous and the next node) that implements both
ListandDeque. get(i)starts from whichever end is closer: fromfirstifi < size/2, otherwise fromlast. Still O(n).- Every element is a
Nodeobject (item, next, prev): about 24 bytes per node with compressed oops (the JVM squeezing 64-bit references into 4 bytes), not counting the element itself.ArrayListspends just a 4-byte reference per element. More small objects also means more work for the GC. - Nodes are scattered across the heap, so the CPU cache helps little; an
ArrayList’s array is contiguous (good cache locality). For queues and stacks,ArrayDequeis better.
1.3. Don’t use Stack, use ArrayDeque
Key idea: Stack is a legacy class that locks for nothing and exposes index operations. ArrayDeque works as both stack and queue with O(1) amortized operations, no locking and no nodes.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // addFirst
stack.pop(); // removeFirst
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // addLast
queue.poll(); // pollFirst
Concurrent code has its own queues. Backpressure means that when consumers fall behind, producers are forced to slow down instead of piling work into memory.
1.4. How HashMap works
Key idea: HashMap is an array of buckets; the key’s hash picks the bucket, and keys in the same bucket are chained in a list (a tree once it gets long). Past 75% full, the array doubles.
flowchart LR
K["key.hashCode()"] --> M["h ^ (h >>> 16)"]
M --> I["index = hash & (n - 1)"]
I --> T["table[index]"]
T --> B1["Node(k1,v1)"] --> B2["Node(k2,v2)"]
T -. "bucket >= 8 nodes and table >= 64" .-> RB["Red-black tree"]
- An array
tableof buckets (slots). The default capacity is 16 and always a power of two, so the index is a cheap bitwise AND,hash & (n - 1), instead of%. - Collisions (two keys in the same bucket) are chained in a linked list. Since Java 8, once a bucket reaches 8 nodes and the table has at least 64 slots, the bucket becomes a red-black tree (treeify): the worst case drops from O(n) to O(log n). If the table is still smaller than 64, HashMap resizes instead of treeifying.
- The default load factor is 0.75: when
size > capacity * 0.75, the table doubles and entries are redistributed. get/putare O(1) on average, providedhashCodespreads well. AhashCode()that returns a constant piles every key into one bucket.- Not thread-safe: concurrent
puts can lose data. UseConcurrentHashMap. - Never use a mutable object as a key: change a field that feeds
hashCodeafter theputand you’ll nevergetit back. Records andStringmake good keys because they’re immutable. LinkedHashMapkeeps insertion order; construct it withaccessOrder = trueand overrideremoveEldestEntryand you have a simple LRU cache.TreeMapis a red-black tree with O(log n) operations plusfloorKey,ceilingKey,subMap.
HashMap details: hash spreading, splitting on resize, null keys, HashSet
- The hash is “spread” with
h ^ (h >>> 16)so the high bits also influence the index (& (n - 1)only looks at the low bits). - When the table doubles, each entry either keeps its index or moves by exactly
oldCapacity. No full rehash is needed. - A treeified bucket that shrinks to 6 nodes turns back into a linked list.
- It allows one
nullkey (stored in bucket 0) and any number ofnullvalues. - Before Java 8, a concurrent resize could even create an infinite loop in a bucket.
HashSetis really aHashMapwhose values are a dummy object.
1.5. Java 21: Sequenced Collections
Key idea: since Java 21, List, Deque and LinkedHashSet share getFirst(), getLast(), reversed() and friends, so no more list.get(list.size() - 1).
1.6. Big-O cheat sheet
Key idea: arrays win at index access, ArrayDeque at both ends, HashMap at lookup by key, TreeMap when you need order. LinkedList is only cheap when you’re already standing where you want to change it.
| Structure | Index access | Search by value | Add first | Add last | Insert/remove middle | Remove first | Remove last |
|---|---|---|---|---|---|---|---|
int[] |
O(1) | O(n) | n/a | n/a | n/a | n/a | n/a |
ArrayList |
O(1) | O(n) | O(n) | O(1)* | O(n) | O(n) | O(1) |
LinkedList |
O(n) | O(n) | O(1) | O(1) | O(n) find + O(1) link | O(1) | O(1) |
ArrayDeque |
n/a | O(n) | O(1)* | O(1)* | n/a | O(1) | O(1) |
PriorityQueue |
n/a | O(n) | offer O(log n) |
poll O(log n) |
|||
HashMap/HashSet |
n/a | O(1) avg, O(log n) worst (Java 8+) | put O(1) avg |
remove O(1) avg |
|||
TreeMap/TreeSet |
n/a | O(log n) | put O(log n) |
remove O(log n) |
* amortized.
Exercises
Exercise 1: Build your own ArrayList and add more methods
Task: starting from the hand-written ArrayList in the lesson, add clear, contains, get, indexOf, lastIndexOf, set, trimToSize, addFirst, addLast, removeFirst, removeLast, getFirst, getLast.
Exercise 1 solution: growth factor and a generic MyArrayList (tested)
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Objects;
public class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] data;
private int size;
public MyArrayList() { this(DEFAULT_CAPACITY); }
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException("capacity < 0");
data = new Object[initialCapacity];
}
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
private void growIfFull() {
if (size == data.length) {
// grow ~1.5x like the JDK; max(...) handles capacity 0 or 1
int newCap = Math.max(DEFAULT_CAPACITY, data.length + (data.length >> 1));
data = Arrays.copyOf(data, newCap);
}
}
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
}
public void add(E e) { add(size, e); }
public void add(int index, E e) {
if (index < 0 || index > size) // index == size means append
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
growIfFull();
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E) data[index];
}
public E set(int index, E e) {
E old = get(index);
data[index] = e;
return old;
}
public E remove(int index) {
E old = get(index);
System.arraycopy(data, index + 1, data, index, size - index - 1);
data[--size] = null; // drop the stale reference -> no leak
return old;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++)
if (Objects.equals(o, data[i])) return i; // null-safe
return -1;
}
public int lastIndexOf(Object o) {
for (int i = size - 1; i >= 0; i--)
if (Objects.equals(o, data[i])) return i;
return -1;
}
public boolean contains(Object o) { return indexOf(o) >= 0; }
public void clear() {
data = new Object[DEFAULT_CAPACITY]; // the task asks to reset to the default size
size = 0;
}
public void trimToSize() {
if (data.length > size) data = Arrays.copyOf(data, size);
}
public void addFirst(E e) { add(0, e); } // O(n)
public void addLast(E e) { add(size, e); } // O(1) amortized
public E removeFirst() { requireNotEmpty(); return remove(0); }
public E removeLast() { requireNotEmpty(); return remove(size - 1); }
public E getFirst() { requireNotEmpty(); return get(0); }
public E getLast() { requireNotEmpty(); return get(size - 1); }
private void requireNotEmpty() {
if (size == 0) throw new NoSuchElementException("list is empty");
}
@Override
public String toString() { // slide 1.3 "show()": [a, b, c]
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
if (i > 0) sb.append(", "); // comma only BETWEEN elements
sb.append(data[i]);
}
return sb.append(']').toString();
}
}
Quick notes:
System.arraycopyhandles overlapping source and destination correctly, so use it to shift right (insert) and left (remove) instead of a hand-writtenforloop.getFirston an empty list throwsNoSuchElementException, matchingArrayList.getFirst()in Java 21.Objects.equalsmakesindexOf(null)work.toString()replaces the slides’show()(prints[a, b, c]): the comma goes before every element except the first, so there’s no trailing comma. An empty list prints[]. OverridingtoStringbeats a method that prints toSystem.out, because the string works in logs, tests and the debugger.
Exercise 2: Build your own LinkedList and add more methods
Task: starting from the LinkedList in the lesson (singly linked, with head, tail, size), add clear, contains, indexOf, lastIndexOf, set, getFirst, getLast.
Exercise 2 solution: bugs in the slides’ sample code and MyLinkedList
Smaller things still worth knowing: the method name removeFist is a typo; get(n) with an out-of-range n silently returns null instead of throwing; add(i, e) with i > size silently appends instead of failing; remove(i) with i >= size corrupts the list. The solution below checks the index and throws IndexOutOfBoundsException in all of these cases.
import java.util.NoSuchElementException;
import java.util.Objects;
public class MyLinkedList<E> {
private static final class Node<E> {
E data;
Node<E> next;
Node(E data) { this.data = data; }
}
private Node<E> head;
private Node<E> tail;
private int size;
public int size() { return size; }
private Node<E> node(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
Node<E> cur = head;
for (int i = 0; i < index; i++) cur = cur.next;
return cur;
}
public void addFirst(E e) {
Node<E> n = new Node<>(e);
n.next = head;
head = n;
if (tail == null) tail = n; // the list was empty
size++;
}
public void addLast(E e) { // O(1) thanks to tail
Node<E> n = new Node<>(e);
if (tail == null) {
head = tail = n;
} else {
tail.next = n;
tail = n;
}
size++;
}
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
if (index == 0) { addFirst(e); return; }
if (index == size) { addLast(e); return; }
Node<E> prev = node(index - 1);
Node<E> n = new Node<>(e);
n.next = prev.next; // link the new node to the rest FIRST
prev.next = n; // then repoint prev
size++;
}
public E removeFirst() {
if (head == null) throw new NoSuchElementException();
E val = head.data;
head = head.next;
if (head == null) tail = null; // we just removed the only element
size--;
return val;
}
public E removeLast() { // still O(n): a singly list must find the second-to-last node
if (size <= 1) return removeFirst();
Node<E> prev = node(size - 2);
E val = tail.data;
prev.next = null;
tail = prev;
size--;
return val;
}
public E remove(int index) {
if (index == 0) return removeFirst();
Node<E> prev = node(index - 1);
Node<E> target = prev.next;
if (target == null) throw new IndexOutOfBoundsException("index=" + index);
prev.next = target.next;
if (target == tail) tail = prev;
size--;
return target.data;
}
public E get(int index) { return node(index).data; }
public E set(int index, E e) {
Node<E> n = node(index);
E old = n.data;
n.data = e;
return old;
}
public int indexOf(Object o) {
int i = 0;
for (Node<E> cur = head; cur != null; cur = cur.next, i++)
if (Objects.equals(o, cur.data)) return i;
return -1;
}
public int lastIndexOf(Object o) { // can't walk backwards: one pass, remember the last match
int i = 0, last = -1;
for (Node<E> cur = head; cur != null; cur = cur.next, i++)
if (Objects.equals(o, cur.data)) last = i;
return last;
}
public boolean contains(Object o) { return indexOf(o) >= 0; }
public void clear() {
head = tail = null; // nothing references the nodes now; the GC cleans up
size = 0;
}
public E getFirst() {
if (head == null) throw new NoSuchElementException();
return head.data;
}
public E getLast() {
if (tail == null) throw new NoSuchElementException();
return tail.data;
}
@Override
public String toString() { // O(n): follow next instead of calling get(i)
StringBuilder sb = new StringBuilder("[");
for (Node<E> cur = head; cur != null; cur = cur.next) {
sb.append(cur.data);
if (cur.next != null) sb.append(" -> ");
}
return sb.append("]").toString();
}
}
The task says clear() should “reset to the default size”, but a linked list has no capacity, so dropping the references is all it takes.
Remember
- Explain why
ArrayList.addis O(1) amortized even though some calls cost O(n), and why growing by+10each time turns into O(n²). - Know when
LinkedListreally beatsArrayList, and give the two reasons it usually loses (cache locality, ~24 bytes per node). - Give three reasons to drop
StackforArrayDeque, and say whyArrayDequerejectsnull. - Redraw the path
hashCode→ hash spreading →hash & (n - 1)→ bucket → list/tree, with the thresholds 8, 64 and 0.75. - Know why mutable keys break
HashMapand why production queues must be bounded.
Interview questions
Mid
How does ArrayList grow, and why is add O(1) amortized?
When full, it allocates an array ~1.5× bigger and copies over; because growth is geometric, the total copying across n adds is only O(n).
The default constructor starts with an empty array; the first add allocates 10 slots. Total copying is bounded by a constant times n, so each add averages O(1), even though a single add can be O(n).
When is LinkedList actually better than ArrayList?
Rarely: mainly when you insert or remove a lot in the middle through a ListIterator that’s already positioned there.
Or when you need cheap head operations and don’t want ArrayDeque. In most benchmarks ArrayList wins thanks to cache locality and fewer objects; LinkedList carries ~24 bytes of overhead per node and makes the GC work harder.
Why use ArrayDeque instead of Stack?
Stack extends Vector, so it locks for nothing and breaks LIFO; ArrayDeque is a circular array with O(1) amortized push/pop and no locking.
Every Stack method is synchronized, and it exposes index-based methods. ArrayDeque allocates no nodes. The Javadoc itself recommends Deque.
Senior
Walk me through how HashMap works in Java 8+.
A power-of-two array of buckets: the hash picks a bucket, collisions chain in a list, long lists become red-black trees, and past the load factor the table doubles.
16 buckets by default. The hash is spread with h ^ (h >>> 16) and the index is hash & (n-1). Once a bucket hits 8 nodes and the table has at least 64 slots it treeifies (O(log n) worst case), and it turns back into a list at 6. When size exceeds capacity * 0.75 the table doubles and entries are split. Not thread-safe; allows one null key.
What goes wrong if you use a mutable object as a HashMap key?
If a field that feeds hashCode changes after the put, get computes a different bucket, so the entry is never found again.
The entry stays in its old bucket as unreachable garbage that still takes memory, i.e. a leak. Use immutable keys (String, records, Long).
Which queue would you use for producer/consumer in production, and why bounded?
ArrayBlockingQueue or LinkedBlockingQueue with a capacity, because an unbounded queue hides slow consumers until the heap fills up.
An unbounded queue ends in OutOfMemoryError. A bounded queue creates backpressure: producers block or get false from offer, so you can reject requests, shed load or scale consumers. Note that Executors.newFixedThreadPool uses an unbounded LinkedBlockingQueue, which is a common trap.
How would you build an LRU cache with Java Collections?
Use new LinkedHashMap<>(capacity, 0.75f, true) and override removeEldestEntry to return size() > capacity; get and put are O(1).
Access order (true) makes every get move the entry to the end. From scratch, combine a HashMap (key → node) with a doubly linked list. For concurrent access you need locking, or a library like Caffeine.
Useful phrases for interviews
- “Appending is amortized constant time; the occasional resize is O(n), but it’s spread across all the cheap appends.”
- “Under the hood, HashMap hashes the key to a bucket and falls back to a tree when a bucket gets too crowded.”
- “I’d reach for ArrayDeque here, since Stack is a legacy, synchronized class.”
- “In production I’d make the queue bounded so we get backpressure instead of running out of memory.”
- “That approach breaks down when keys are mutable, because the hash changes after insertion.”
- “
new ArrayList<>()allocates lazily: the ten-slot array only appears on the first add.” - “Java 8 treeifies a bucket once it has eight entries and the table has at least 64 slots, so the worst case drops to O(log n).”
- “If I know the size up front, I presize the collection to avoid repeated resizing.”
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.