Java LinkedList Internals: Building a Doubly Linked List from Scratch

Collaborative text editors and streaming audio playback queues share a common algorithmic requirement: fast insertion and deletion at arbitrary positions without copying underlying memory.

Users constantly insert new text paragraphs or queue up songs at the top of the list.

If you store 100,000 document lines inside an ArrayList and insert a new line at position 0, ArrayList must shift all 100,000 existing array elements right by one slot in memory. Every single keystroke forces an $O(N)$ linear memory copy operation. Keystrokes feel sluggish.

This performance flaw is why linked data structures exist. A LinkedList stores elements in isolated node objects connected by memory pointers, enabling instantaneous head insertions without element shifting.

Why You Need This in Real Life

Choosing between ArrayList and LinkedList is one of the most common decision points in Java development.

Head/Tail Insertions: If your application frequently prepends items to the front of a sequence, LinkedList executes in exact $O(1)$ constant time.
Random Access Cost: If your application constantly reads elements by index (get(5000)), LinkedList requires stepping through node pointers one-by-one, running in $O(N)$ time.
Memory Pointer Overhead: Each LinkedList node allocates 24 bytes of object header and pointer fields per item, consuming significantly more heap space than a flat array.

A Hypothetical Production Misstep: The Index Lookup Loop Trap

Suppose a developer needs to process a list of 50,000 pending orders stored in a LinkedList:

// SLOW CODE TRAP: O(N^2) complexity!
for (int i = 0; i < orderList.size(); i++) {
    Order order = orderList.get(i); // get(i) traverses nodes from head every single iteration!
    processOrder(order);
}

Because orderList.get(i) starts at the head pointer and traverses node links i times, running this loop executes:

$1 + 2 + 3 + \dots + 50,000 = \frac{50,000 \times 50,001}{2} \approx 1,250,000,000 \text{ node pointer hops!}$

The batch job takes minutes instead of milliseconds. Using an Iterator or enhanced for loop fixes the issue by keeping a persistent pointer to the current node.

Node Structure and Memory Layout

A doubly linked list node holds three variables:

T item: The stored payload object reference.
Node<T> next: Reference pointer to the succeeding node.
Node<T> prev: Reference pointer to the preceding node.

       +-------------------------------------------------------+
       |                     Node Heap Layout                  |
       |  +----------------+---------------+----------------+  |
       |  |  Node<T> prev  |    T item     |  Node<T> next  |  |
       |  +----------------+---------------+----------------+  |
       +-------------------------------------------------------+

The list class maintains references to the first node (head) and the last node (tail).

head                                                            tail
  |                                                               |
  v                                                               v
+------+------+------+    +------+------+------+    +------+------+------+
| null | "A"  | next |--->| prev | "B"  | next |--->| prev | "C"  | null |
|      |      |      |<---|      |      |      |<---|      |      |      |
+------+------+------+    +------+------+------+    +------+------+------+

Prepending & Appending in Exact $O(1)$ Time

Inserting at the front or end of a doubly linked list requires zero array copies:

public void addLast(T element) {
    Node<T> oldTail = tail;
    Node<T> newNode = new Node<>(oldTail, element, null);
    tail = newNode;
    if (oldTail == null) {
        head = newNode;
    } else {
        oldTail.next = newNode;
    }
    size++;
}

Fast Index Traversal: The Half-Search Optimization

Linked lists cannot compute memory addresses directly by index. To fetch index 5, you must start at a boundary pointer and follow .next references step-by-step.

We optimize index lookup by checking whether the target index lies in the front half or back half of the list:

private Node<T> nodeAt(int index) {
    if (index < (size >> 1)) {
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    } else {
        Node<T> curr = tail;
        for (int i = size - 1; i > index; i--) {
            curr = curr.prev;
        }
        return curr;
    }
}

If size is 100 and you request index 90, the loop starts at tail and moves backward 10 steps instead of forward 90 steps from head.

Complete `MyLinkedList<T>` Code

public class MyLinkedList<T> {
    private static class Node<T> {
        T item;
        Node<T> next;
        Node<T> prev;

        Node(Node<T> prev, T element, Node<T> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size = 0;

    public void add(T element) {
        addLast(element);
    }

    public void addFirst(T element) {
        Node<T> oldHead = head;
        Node<T> newNode = new Node<>(null, element, oldHead);
        head = newNode;
        if (oldHead == null) {
            tail = newNode;
        } else {
            oldHead.prev = newNode;
        }
        size++;
    }

    public void addLast(T element) {
        Node<T> oldTail = tail;
        Node<T> newNode = new Node<>(oldTail, element, null);
        tail = newNode;
        if (oldTail == null) {
            head = newNode;
        } else {
            oldTail.next = newNode;
        }
        size++;
    }

    public T get(int index) {
        checkBounds(index);
        return nodeAt(index).item;
    }

    public T remove(int index) {
        checkBounds(index);
        return unlink(nodeAt(index));
    }

    public int size() {
        return size;
    }

    private T unlink(Node<T> target) {
        T element = target.item;
        Node<T> next = target.next;
        Node<T> prev = target.prev;

        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            target.prev = null;
        }

        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            target.next = null;
        }

        target.item = null; // Clear payload reference for GC
        size--;
        return element;
    }

    private Node<T> nodeAt(int index) {
        if (index < (size >> 1)) {
            Node<T> x = head;
            for (int i = 0; i < index; i++) x = x.next;
            return x;
        } else {
            Node<T> x = tail;
            for (int i = size - 1; i > index; i--) x = x.prev;
            return x;
        }
    }

    private void checkBounds(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
}

Architectural Trade-off: `ArrayList` vs `LinkedList`

Operation	`ArrayList`	`LinkedList`
Random Access (`get(i)`)	$O(1)$	$O(N)$
Append (`addLast`)	Amortized $O(1)$	Exact $O(1)$
Prepend (`addFirst`)	$O(N)$	Exact $O(1)$
Removal by Index	$O(N)$ (element copies)	$O(N)$ (index traversal)
Memory Per Element	4 bytes reference	24 bytes node overhead

Quick Summary

LinkedList connects elements via double pointers (prev and next).
Head and tail insertions take exact $O(1)$ time without array re-allocations.
Random index access takes $O(N)$ time because traversal must step through linked nodes.

References & Further Reading

OpenJDK Repository. OpenJDK 21 Source Code: java.util.LinkedList. GitHub.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Linked Lists). Addison-Wesley.
Oracle Corporation. Java SE 21 API Documentation: java.util.LinkedList. Oracle Docs.