Java LinkedList Internal Working

Every LinkedList operation — add(), get(), remove() — works by manipulating pointers on small Node objects scattered across the heap. There is no backing array. There is no pre-allocated block. Each element lives in its own Node object that holds the element reference and two pointers: one to the next node and one to the previous. Knowing this one structural fact explains every performance characteristic of LinkedList, why get(index) is O(n) when ArrayList.get() is O(1), and why adding at either end is O(1) when adding in the middle is O(n).

What Is Inside a LinkedList?

LinkedList<E> is backed by a doubly-linked chain of Node<E> objects. The class itself holds only three fields — and no array at all.

LINKEDLIST INTERNAL FIELDS (simplified from JDK source):

  transient int         size;    ← number of elements stored
  transient Node<E>     first;   ← pointer to the HEAD node (first element)
  transient Node<E>     last;    ← pointer to the TAIL node (last element)

  private static class Node<E> {
      E         item;   ← the actual element reference
      Node<E>   next;   ← pointer to the NEXT node (or null for tail)
      Node<E>   prev;   ← pointer to the PREVIOUS node (or null for head)
  }

EMPTY LINKEDLIST:
  size  = 0
  first = null
  last  = null

AFTER add("A"), add("B"), add("C"):

  LinkedList object:
    first ────────────────┐
    last ─────────────────────────────────────┐
    size = 3              │                   │
                          ▼                   ▼
         null ← [prev|"A"|next] ↔ [prev|"B"|next] ↔ [prev|"C"|next] → null

  Each Node object lives at its own heap address.
  first.next = B's node,  first.prev = null
  last.prev  = B's node,  last.next  = null
  B.prev     = A's node,  B.next     = C's node

  NAVIGATION:
    HEAD → TAIL: first.next.next... (forward traversal)
    TAIL → HEAD: last.prev.prev...  (backward traversal)
    Both directions are O(1) per step — two pointers per node.

Basic Overview — How Each Core Method Works

METHOD              WHAT HAPPENS INTERNALLY                        COMPLEXITY
─────────────────────────────────────────────────────────────────────────────
add(e)              linkLast(e): allocate new Node, wire to tail    O(1)
addFirst(e)         linkFirst(e): allocate new Node, wire to head   O(1)
add(index, e)       locate node at index via traversal, then link   O(n)
get(index)          traverse from head or tail to index             O(n)
set(index, e)       traverse to index, update node.item             O(n)
remove()            unlinkFirst(): rewire head pointer               O(1)
removeLast()        unlinkLast(): rewire tail pointer                O(1)
remove(index)       traverse to node, then unlink it                O(n)
remove(object)      linear scan for node, then unlink               O(n)
contains(object)    linear scan — indexOf(obj) >= 0                 O(n)
size()              return size field                                O(1)
isEmpty()           return size == 0                                 O(1)
peek()              first == null ? null : first.item                O(1)
peekLast()          last == null ? null : last.item                  O(1)
poll()              unlinkFirst() if not empty                       O(1)
pollLast()          unlinkLast() if not empty                        O(1)
push(e)             addFirst(e) — LIFO stack operation               O(1)
pop()               removeFirst()                                    O(1)
offer(e)            addLast(e) — FIFO queue operation                O(1)

KEY RULE: The only O(1) operations are at the two ENDS (head and tail).
          Everything requiring an index position in the MIDDLE is O(n).

When to Use LinkedList

USE LinkedList WHEN:
  1. Frequent O(1) insertions and removals at BOTH ends
     — FIFO queue: offer() at tail, poll() at head
     — LIFO stack: push() at head, pop() from head
     — Double-ended sliding window, work-stealing scheduler

  2. Both Deque AND List interfaces are needed on the same variable
     — addFirst(), addLast(), getFirst(), getLast()
     — AND get(index), subList(), listIterator()
     — Only LinkedList implements both simultaneously

  3. Frequent insertions/deletions in the MIDDLE of a large list
     IF you already hold a reference to the node via an iterator
     — iterator.remove() is O(1) after traversal — no shifting

USE ArrayList INSTEAD WHEN (which is most situations):
  - Random access by index is needed at all — get(i) is O(n) on LinkedList
  - Sequential iteration without removal is the primary operation
    (ArrayList's contiguous memory is CPU-cache-friendly; LinkedList nodes are scattered)
  - Memory efficiency matters — each LinkedList Node costs ~24 bytes extra
    (header + item + next + prev references) vs ArrayList's 4 bytes per reference

DO NOT USE LinkedList WHEN:
  - You think "it is better for insertions" without measuring
    For most real lists, ArrayList's amortised O(1) append and O(n) shift
    beats LinkedList's O(n) traversal + O(1) link for mid-list inserts
    because ArrayList's shift is a single System.arraycopy (native, SIMD-optimised)
    while LinkedList must traverse n/2 nodes before it can insert anything

How LinkedList Works Internally

Node Allocation and the Head/Tail Pointers

Every add() call allocates a new Node<E> object on the heap — no pre-allocation, no resizing. The first and last fields in the LinkedList object are the only two fixed pointers. Everything else is reached by traversing the chain.

STEP-BY-STEP: add("A"), add("B"), add("C")

AFTER add("A"):  [linkLast("A")]
  Node_A = new Node<>(prev=null, item="A", next=null)
  first  = Node_A
  last   = Node_A
  size   = 1

  Heap:  LinkedList{ first→Node_A, last→Node_A, size=1 }
         Node_A{ prev=null, "A", next=null }

AFTER add("B"):  [linkLast("B")]
  Node_B = new Node<>(prev=Node_A, item="B", next=null)
  Node_A.next = Node_B   ← wire the existing tail's next to new node
  last        = Node_B   ← move the tail pointer
  size        = 2

  Heap:  LinkedList{ first→Node_A, last→Node_B, size=2 }
         Node_A{ prev=null, "A", next→Node_B }
         Node_B{ prev→Node_A, "B", next=null }

AFTER add("C"):  [linkLast("C")]
  Node_C = new Node<>(prev=Node_B, item="C", next=null)
  Node_B.next = Node_C
  last        = Node_C
  size        = 3

  Heap:  LinkedList{ first→Node_A, last→Node_C, size=3 }
         Node_A{ prev=null,    "A", next→Node_B }
         Node_B{ prev→Node_A,  "B", next→Node_C }
         Node_C{ prev→Node_B,  "C", next=null   }

NO ARRAY. NO RESIZE. Each node is a separate heap object.
Adding 1,000 elements allocates exactly 1,000 Node objects.

get(index) — Bidirectional Traversal

LinkedList cannot jump to a position by index — there is no array to index into. Instead, it decides whether to start from first (head) or last (tail) based on whether the index is in the first or second half of the list.

get(index) IMPLEMENTATION:
  if (index < (size >> 1)) {
      Node<E> x = first;
      for (int i = 0; i < index; i++)
          x = x.next;            ← walk forward from head
      return x;
  } else {
      Node<E> x = last;
      for (int i = size - 1; i > index; i--)
          x = x.prev;            ← walk backward from tail
      return x;
  }

EXAMPLE: get(2) on list ["A","B","C","D","E"] (size=5):
  index=2, size/2=2.5 → index 2 is NOT < 2 (false)
  Walk backward from tail:
    x = Node_E (i=4)
    x = Node_D (i=3)
    x = Node_C (i=2)  ← stop
  return Node_C.item = "C"

EXAMPLE: get(1) on list ["A","B","C","D","E"] (size=5):
  index=1, 1 < 2.5 → true
  Walk forward from head:
    x = Node_A (start)
    x = Node_B (i=1)  ← stop
  return Node_B.item = "B"

WHY THIS MATTERS:
  Even with the bidirectional optimisation, get(size/2) is O(n/2) = O(n).
  Calling get(i) in a for loop is O(n²) — each call traverses half the list.
  ALWAYS use iterator or for-each when iterating — O(n) total instead of O(n²).

add(int index, E element) — Mid-List Insertion

add(2, "X") on list ["A","B","C","D"], size=4:

  Step 1: checkPositionIndex(2) — valid: 0 <= 2 <= 4
  Step 2: if index == size → linkLast; else:
          Node_at_2 = node(2) = Node_C (traverse from head: A → B → C)
  Step 3: linkBefore("X", Node_C):
          Node_X = new Node<>(prev=Node_B, item="X", next=Node_C)
          Node_B.next = Node_X   ← B now points to X
          Node_C.prev = Node_X   ← C now points back to X
          size++

  BEFORE: null ← A ↔ B ↔ C ↔ D → null
  AFTER:  null ← A ↔ B ↔ X ↔ C ↔ D → null

  POINTER SURGERY — only 4 pointer fields changed (Node_B.next, Node_X.next,
  Node_X.prev, Node_C.prev). No elements shifted. No array copied.
  But the O(n) traversal to FIND position 2 is unavoidable.

remove(int index) — Pointer Surgery

remove(1) on list ["A","B","C","D"], size=4:

  BEFORE: null ← A ↔ B ↔ C ↔ D → null

  Step 1: traverse to node at index 1 → Node_B
  Step 2: unlink(Node_B):
          Node_A.next = Node_C   ← B's predecessor now points to B's successor
          Node_C.prev = Node_A   ← B's successor now points back to B's predecessor
          Node_B.item = null     ← help GC — clear the element reference
          Node_B.next = null     ← detach Node_B from the chain
          Node_B.prev = null     ← detach Node_B from the chain
          size--

  AFTER: null ← A ↔ C ↔ D → null
         Node_B is now unreferenced → eligible for GC

  NULL-OUT AFTER REMOVAL:
    Setting Node_B.item, Node_B.next, Node_B.prev to null is critical.
    Without these assignments, Node_B holds strong references to Node_A
    and Node_C — preventing GC even after unlink.
    ArrayList does the same — elementData[--size] = null after remove.

Core Operations with Examples

Node-Level Visibility via Reflection

Output:
=== Observing node chain as elements are added ===
empty      size=0  nodes: HEAD →  → TAIL
add Alpha  size=1  nodes: HEAD → [Alpha] → TAIL
add Beta   size=2  nodes: HEAD → [Alpha] ↔ [Beta] → TAIL
add Gamma  size=3  nodes: HEAD → [Alpha] ↔ [Beta] ↔ [Gamma] → TAIL
addFirst Zeta size=4  nodes: HEAD → [Zeta] ↔ [Alpha] ↔ [Beta] ↔ [Gamma] → TAIL
addLast Omega size=5  nodes: HEAD → [Zeta] ↔ [Alpha] ↔ [Beta] ↔ [Gamma] ↔ [Omega] → TAIL

=== After remove operations ===
remove Beta  size=4  nodes: HEAD → [Zeta] ↔ [Alpha] ↔ [Gamma] ↔ [Omega] → TAIL
removeFirst  size=3  nodes: HEAD → [Alpha] ↔ [Gamma] ↔ [Omega] → TAIL
removeLast   size=2  nodes: HEAD → [Alpha] ↔ [Gamma] → TAIL

O(n) get vs O(1) Head/Tail Access

Output:
List: [10, 20, 30, 40, 50, 60, 70, 80]

=== O(1) head/tail operations ===
getFirst()  : 10
getLast()   : 80
peekFirst() : 10
peekLast()  : 80

=== O(n) indexed access ===
get(0)      : 10
get(3)      : 40
get(7)      : 80
get(4)      : 50

=== O(n²) trap: get(i) in a loop ===
WRONG way (O(n²)): 10 20 30 40 50 60 70 80 ← AVOID for large lists
CORRECT way (O(n)): 10 20 30 40 50 60 70 80 ← use for-each or iterator

=== FIFO queue using LinkedList ===
Queue: [first-in, second-in, third-in]
poll(): first-in
poll(): second-in
After polls: [third-in]

Iterator Correctness and Fail-Fast Behaviour

Output:
=== for-each with remove → CME ===
ConcurrentModificationException thrown

=== Iterator.remove() — safe O(1) node removal ===
After it.remove(): [validate, authenticate, process]

=== removeIf() — clean one-pass removal ===
After removeIf(starts with 'a'): [validate, process, notify]

=== ListIterator — forward + backward + add ===
Forward : 10 20 30 40 50
Backward: 50 40 30 20 10
After lit.add(25) at position 2: [10, 20, 25, 30, 40, 50]

Real-World Example — CRED Payment Processing Pipeline

CRED's payment processing service routes payments through sequential pipeline stages — KYC check, fraud detection, bank validation, and ledger entry. New stage handlers are registered at startup and payments flow through the chain in order. Handlers are rarely added or removed mid-pipeline, but when they are (A/B testing, regional compliance toggles), the linked structure allows O(1) handler insertion at any iterator position — no stage-shifting required.

Output:
Pipeline has 4 stages

[CRED-UPI] Processing txn=TXN-9921 amount=Rs.4999.00
    KYC check...
  Stage 1: PASSED
    Fraud detection...
  Stage 2: PASSED
    Bank validation...
  Stage 3: PASSED
    Ledger entry...
  Stage 4: PASSED
  All stages passed — txn approved

[CRED-UPI] Processing txn=TXN-9922 amount=Rs.250000.00
    KYC check...
  Stage 1: FAILED
  Pipeline halted at stage 1

[CRED-UPI] Processing txn=FLAGGED-TXN-001 amount=Rs.1500.00
    KYC check...
  Stage 1: PASSED
    Fraud detection...
  Stage 2: FAILED
  Pipeline halted at stage 2

Inserted compliance stage — now 5 stages

[CRED-UPI] Processing txn=TXN-9923 amount=Rs.8499.00
    KYC check...
  Stage 1: PASSED
    Compliance check...
  Stage 2: PASSED
    Fraud detection...
  Stage 3: PASSED
    Bank validation...
  Stage 4: PASSED
    Ledger entry...
  Stage 5: PASSED
  All stages passed — txn approved

Performance Considerations

Cache locality is the hidden cost. LinkedList nodes are allocated on the heap at different times and typically live at scattered memory addresses. Sequential iteration follows node.next pointers to arbitrary heap locations, causing CPU cache misses on each step. ArrayList's contiguous array allows hardware prefetching — the CPU loads the next few elements into cache automatically. Benchmarks consistently show ArrayList iteration outperforming LinkedList iteration even when both are O(n), simply because of cache behaviour.

Memory footprint per element. Each Node<E> object on a 64-bit JVM with compressed references costs approximately 28 bytes: 12 bytes for the object header, 4 bytes for item, 4 bytes for next, 4 bytes for prev, and 4 bytes padding. ArrayList stores 4 bytes per element (a reference into the elementData array). For one million strings, LinkedList uses ~28 MB for nodes alone; ArrayList uses ~4 MB.

Best Practices

Declare the variable as Deque<E> when using LinkedList as a double-ended queue. Deque<String> queue = new LinkedList<>() signals intent — the caller only gets queue operations (offer(), poll(), peek(), addFirst(), addLast()). Declaring LinkedList<String> exposes everything including get(index), which will be misused if visible. Consider ArrayDeque instead — it is faster than LinkedList for pure queue/stack use because of better cache behaviour and no per-element node allocation.

Never call get(index) inside a for loop on a LinkedList. for (int i = 0; i < list.size(); i++) { list.get(i); } is O(n²). Each get(i) traverses up to size/2 nodes. For a list of 10,000 elements this is 25 million node hops instead of 10,000. Use for-each or an explicit Iterator — both advance one node per step for O(n) total.

Use ListIterator for mid-list insertions. If the insertion point is found via an iterator, listIterator.add() is O(1) pointer surgery. If the insertion point must be found by index each time, that is O(n) traversal + O(1) link — equivalent to ArrayList's O(n) shift but with more heap allocation overhead. The cases where LinkedList genuinely beats ArrayList for mid-list operations are narrow: bulk insertions at the same position during a single iterator pass.

Clear the list by assigning a new instance when GC pressure matters. list.clear() iterates the chain setting each Node's fields to null — O(n). After clear(), the LinkedList holds no nodes. But if GC is not triggered, the cleared nodes may stay in memory briefly. list = new LinkedList<>() is equivalent and allows the old nodes to become unreachable in one step.

Common Mistakes

Mistake 1 — get(index) in a for Loop

Mistake 2 — Using LinkedList Where ArrayList Is Faster

Mistake 3 — Structural Modification During For-Each Iteration

Output:
[A, C, D]

Mistake 4 — Choosing LinkedList When ArrayDeque Is the Real Need

Interview Questions

Q1. What is the internal data structure of LinkedList in Java?

LinkedList<E> is backed by a doubly-linked chain of Node<E> objects. Each Node holds three fields: item (the element reference), next (pointer to the next node), and prev (pointer to the previous node). The LinkedList class itself holds only three fields: size, first (pointer to the head node), and last (pointer to the tail node). There is no backing array — elements are stored in individually allocated Node objects scattered across the heap. This means there is no resize operation: adding an element always allocates exactly one new Node.

Q2. Why is get(index) O(n) on LinkedList but O(1) on ArrayList?

ArrayList stores elements in a contiguous Object[] array and can access any position directly: elementData[index] is a single array dereference — O(1). LinkedList has no array; to reach position i, it must start at first or last and follow next or prev pointers one step at a time until the correct node is reached. Even with the bidirectional optimisation (start from the closer end), the worst case is O(n/2) = O(n). This is why calling get(i) inside a for loop on a LinkedList produces O(n²) behaviour.

Q3. Why does LinkedList use more memory than ArrayList per element?

Each LinkedList element is stored in a Node<E> object that carries three references: item, next, and prev. On a 64-bit JVM with compressed references, each Node costs approximately 28 bytes — 12 for the object header plus 4 bytes each for the three reference fields plus alignment padding. ArrayList stores a 4-byte reference per element in its contiguous Object[]. For one million elements, LinkedList uses roughly 28 MB just for nodes; ArrayList uses roughly 4 MB for the reference array. This 7:1 ratio compounds under GC pressure.

Q4. When does LinkedList's O(1) insertion actually beat ArrayList?

LinkedList's O(1) insertion advantage over ArrayList is real only in two specific cases. First, insertions at either end — addFirst() or addLast() — are O(1) on LinkedList versus O(n) for add(0, e) on ArrayList. Second, mid-list insertions via a ListIterator already positioned at the target node — the link operation is O(1) after the iterator walk. For typical mid-list inserts specified by index, LinkedList still traverses O(n) nodes to find the position, then does O(1) pointer surgery. ArrayList's O(n) System.arraycopy shift is a native SIMD-optimised bulk memory operation that is often faster in practice than the linked traversal at the same O(n) complexity.

Q5. What is the modCount mechanism and how does it cause ConcurrentModificationException?

modCount is an inherited int field from AbstractList that increments on every structural modification — add(), remove(), clear(), or any operation that changes the list's size. When iterator() is created, it captures modCount as expectedModCount. Every call to iterator.next() checks modCount == expectedModCount. If they differ, it means a structural change happened after the iterator was created, and ConcurrentModificationException is thrown. Iterator.remove() is the safe alternative — it performs the unlinking and then updates expectedModCount = modCount to keep them in sync.

Q6. How does removing a node from the middle of a LinkedList work internally?

remove(index) first traverses to the target node — O(n). Then unlink(node) executes four pointer updates: node.prev.next = node.next (the predecessor's forward pointer skips the target), node.next.prev = node.prev (the successor's backward pointer skips the target), then node.item = null, node.next = null, node.prev = null (all three fields on the removed node are nulled for GC). The null assignments are critical — without them, the unlinked Node object would still hold strong references to its neighbours, preventing garbage collection. This is the same reason ArrayList.remove() nulls the last element slot after shifting.

FAQs

What is the difference between LinkedList and ArrayList internally?

ArrayList uses a contiguous Object[] array with a logical size counter. Random access is O(1). Adding at the end is O(1) amortised. Inserting in the middle shifts elements via System.arraycopy. LinkedList uses a doubly-linked chain of Node objects. Random access requires traversal — O(n). Adding at either end is O(1) — just pointer surgery. Memory per element is ~28 bytes vs ~4 bytes for ArrayList.

Why is LinkedList iteration slower than ArrayList iteration despite both being O(n)?

Big-O notation ignores constant factors. ArrayList iteration reads from a contiguous array, allowing CPU hardware prefetching — the next several elements are loaded into L1/L2 cache automatically. LinkedList iteration follows node.next pointers to arbitrary heap addresses, causing cache misses on each step. Benchmarks consistently show ArrayList iteration outperforming LinkedList iteration by 2-5× for the same number of elements, even though both are O(n).

Does LinkedList support null elements?

Yes. LinkedList allows null elements — multiple nulls in the same list are permitted. list.contains(null) works correctly. ArrayDeque does not allow null; this is one specific case where LinkedList is the correct choice if null elements are required alongside queue or stack operations.

When should I use LinkedList over ArrayDeque for queue operations?

Use ArrayDeque for pure queue or stack operations in almost all cases — it is faster and more memory-efficient. Choose LinkedList over ArrayDeque only when you also need List interface methods on the same variable (get(index), set(index, e), subList()) or when null elements must be stored. ArrayDeque rejects null and does not implement List.

What does ListIterator give you that Iterator does not?

ListIterator<E> extends Iterator<E> with bidirectional traversal (hasPrevious(), previous()), positional information (nextIndex(), previousIndex()), forward insertion at the current cursor position (add(e) — O(1) pointer surgery on LinkedList), and in-place element replacement (set(e)). For LinkedList, ListIterator.add() is the only O(1) mid-list insertion — it inserts between the last returned element and the next, wiring the prev/next pointers without any traversal cost.

What happens when you call clear() on a LinkedList?

clear() iterates the entire chain setting each Node's item, next, and prev fields to null, then sets first = null, last = null, and size = 0. The null-out is essential — each Node holds strong references to its neighbours. Without clearing those references, detached nodes would keep each other alive in memory even after clear(). After clear(), the GC can reclaim the entire chain since no more strong references exist. The operation is O(n) — one pass through all nodes.

Summary

LinkedList<E> is a doubly-linked chain of Node objects — each holding the element, a forward pointer, and a backward pointer. The LinkedList class holds only size, first (head), and last (tail). There is no backing array, no resize, no pre-allocation. Every element lives at its own heap address.

The performance profile follows directly from this structure. Head and tail operations — addFirst(), addLast(), removeFirst(), removeLast(), peekFirst(), peekLast() — are all O(1). Everything involving a middle index requires traversal — O(n). The O(n²) get-in-loop mistake is the most common LinkedList performance bug in production code: for-each is the correct traversal pattern for any sequential processing.

For interviews: know that get(index) traverses from first or last depending on which half the index falls in, explain the Node null-out pattern after removal and why it prevents memory leaks, and name ArrayDeque as the preferred replacement for pure queue and stack use cases.

What to Read Next