Skip to main content
PreparationZone Logo
PrepZone

ArrayList and LinkedList

How each one stores elements, what that costs per operation, and which to default to.

Pass checkpoint below

Why this matters

  • The textbook answer — "LinkedList for insertions, ArrayList for reads" — is misleading, and knowing why marks the difference between memorised and understood.
  • ArrayList growth is the mechanism behind a surprising amount of garbage in list-heavy code, and one constructor argument removes it.
  • These two are the most frequently compared classes in Java interviews.

How each one stores elements

ArrayList — one array
[0] A
[1] B
[2] C

get(i) is instant. Inserting in the middle shifts everything after it.

LinkedList — linked nodes
Node Aprev · next →
Node Bprev · next →
Node Cprev · next → null

get(i) walks from an end. Insert is pointer surgery.

ArrayList stores elements next to each other, so index access is one calculation. LinkedList must walk node by node, but inserting in the middle only relinks two pointers.
  • ArrayList wraps an Object[]. Element i sits at offset i, so indexed access is a single calculation. Inserting in the middle shifts everything after it.
  • LinkedList is a doubly linked list of nodes. Each node holds the element plus a reference forward and backward. Reaching index i means walking i links.

Cost, honestly

AspectOperationArrayList vs LinkedList
get(i) / set(i)O(1)O(n) — must walk to the position
add at endAmortised O(1)O(1)
add or remove at index 0O(n) — shifts everythingO(1)
add or remove in the middleO(n) shiftO(n) to find, then O(1) to relink
contains / indexOfO(n)O(n)
Memory per elementOne slot, plus spare capacityA node object with two references
Cache behaviourExcellent — contiguousPoor — nodes scattered on the heap
  • get(i) / set(i)

    OperationO(1)
    ArrayList vs LinkedListO(n) — must walk to the position
  • add at end

    OperationAmortised O(1)
    ArrayList vs LinkedListO(1)
  • add or remove at index 0

    OperationO(n) — shifts everything
    ArrayList vs LinkedListO(1)
  • add or remove in the middle

    OperationO(n) shift
    ArrayList vs LinkedListO(n) to find, then O(1) to relink
  • contains / indexOf

    OperationO(n)
    ArrayList vs LinkedListO(n)
  • Memory per element

    OperationOne slot, plus spare capacity
    ArrayList vs LinkedListA node object with two references
  • Cache behaviour

    OperationExcellent — contiguous
    ArrayList vs LinkedListPoor — nodes scattered on the heap

LinkedList's middle insertion is only O(1) once you are already there, which an index-based call never is.

How ArrayList grows

The internal array has a capacity that is usually larger than the size. When it fills, a new larger array is allocated and the contents copied.

Java
Loading compiler…

Growth is roughly 1.5× the current capacity. That makes the amortised cost of add constant, because the occasional expensive copy is spread across many cheap appends. But each copy allocates a full array and leaves the old one for the garbage collector.

Practical consequences

  • Pre-size when you can. new ArrayList<>(expected) eliminates every intermediate array.
  • size() is not capacity. A list of 3 elements may hold an array of 10.
  • remove never shrinks the array. Call trimToSize() on the concrete ArrayList if a large list has shrunk permanently.
  • clear() nulls the slots but keeps the capacity, which is efficient for reuse.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 5 sections

  • Removing while iterating
  • remove has two overloads
  • CopyOnWriteArrayList
  • Other list operations worth knowing
  • Common misreadings

Test yourself

Answer these before moving on — recall is what makes it stick.