Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsSenior20 min read

Inside Java Collections: ArrayList, LinkedList, ArrayDeque and HashMap

Review 14 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

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 first add creates 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×), then Arrays.copyOf moves 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 add that 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) or ensureCapacity(n) avoids repeated resizing.
  • ArrayList is not thread-safe. For concurrent use, consider Collections.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 exactly size to save memory.
  • remove(index) shifts the later elements left with System.arraycopy, then sets the last slot to null so the GC can reclaim the object. Forgetting that null is a textbook memory leak when you write your own data structure.
  • ArrayList keeps a modCount of structural changes. Its iterators check it to detect modification during iteration and throw ConcurrentModificationException. 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, an ArrayList<Integer> costs several times more than an int[] because of boxing (wrapping a primitive in an object; each Integer is ~16 bytes). Number-crunching code should use primitive arrays or IntStream.

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 List and Deque.
  • get(i) starts from whichever end is closer: from first if i < size/2, otherwise from last. Still O(n).
  • Every element is a Node object (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. ArrayList spends 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, ArrayDeque is 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 table of 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/put are O(1) on average, provided hashCode spreads well. A hashCode() that returns a constant piles every key into one bucket.
  • Not thread-safe: concurrent puts can lose data. Use ConcurrentHashMap.
  • Never use a mutable object as a key: change a field that feeds hashCode after the put and you’ll never get it back. Records and String make good keys because they’re immutable.
  • LinkedHashMap keeps insertion order; construct it with accessOrder = true and override removeEldestEntry and you have a simple LRU cache. TreeMap is a red-black tree with O(log n) operations plus floorKey, 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 null key (stored in bucket 0) and any number of null values.
  • Before Java 8, a concurrent resize could even create an infinite loop in a bucket.
  • HashSet is really a HashMap whose 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.arraycopy handles overlapping source and destination correctly, so use it to shift right (insert) and left (remove) instead of a hand-written for loop.
  • getFirst on an empty list throws NoSuchElementException, matching ArrayList.getFirst() in Java 21.
  • Objects.equals makes indexOf(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 []. Overriding toString beats a method that prints to System.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.add is O(1) amortized even though some calls cost O(n), and why growing by +10 each time turns into O(n²).
  • Know when LinkedList really beats ArrayList, and give the two reasons it usually loses (cache locality, ~24 bytes per node).
  • Give three reasons to drop Stack for ArrayDeque, and say why ArrayDeque rejects null.
  • 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 HashMap and 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.