Detailed Analysis of LinkedList

LinkedList is also a very common List implementation in the Java Collections Framework, but its design is completely different from ArrayList. The core of ArrayList is a dynamic array, while the core of LinkedList is a linked list. If you think of ArrayList as a row of continuously indexed slots, LinkedList is more like a chain of nodes, where each node remembers its own value and also who comes before and after it.

Class Overview

From the source code perspective, LinkedList is roughly defined like this:

Java

        public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable

There are two important signals here:

It is not just a List
It also implements Deque, so it naturally supports double-ended queue operations.
It extends AbstractSequentialList
The name already tells the positioning: friendly for sequential access, not for random access.

This is very different from ArrayList. ArrayList is more random-access oriented, while LinkedList is more sequential-structure oriented.

Core Internal Fields

The most important fields in LinkedList are usually these:

Java

        transient int size = 0;
transient Node<E> first;
transient Node<E> last;

Their meanings are:

size
How many elements are currently in the list
first
Points to the head node
last
Points to the tail node

You can imagine a linked list as: null <- A <-> B <-> C -> null

Then:

first points to A
last points to C
size equals 3

These three fields almost define all behavior of LinkedList.

What Is Node

The real storage unit in LinkedList is not the element itself, but Node.

The source code idea looks like this:

Java

        private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

Each node stores three things:

item
The value of this node
next
Who the next node is
prev
Who the previous node is

That is the essence of a doubly linked list. For a middle node B in A <-> B <-> C, you have:

B.prev = A
B.item stores B's value
B.next = C

So LinkedList data is not stored contiguously; nodes are linked together by references.

Why It Is a Doubly Linked List

Because each node knows both its previous and next node.

This gives two direct advantages:

You can traverse forward from the head
You can also traverse backward from the tail

That is why when LinkedList searches an index in source code, it does not always start from the head. It chooses first or last depending on position.

What an Empty LinkedList Looks Like

When the list is empty:

size = 0
first = null
last = null

This is important because many insertion and deletion paths split into two cases:

The list was empty
The list was not empty

Many checks in the source revolve around this state.

Inserting at Head: linkFirst

Head insertion is one of the most typical LinkedList source code paths:

Java

        private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
                last = newNode;
        else
                f.prev = newNode;
        size++;
        modCount++;
}

Break it down:

Save old head f
Create new node newNode
New node's prev is null, because it becomes the new head
New node's next points to old head f
Move first to new node
If the list was empty
Old head f is null, so last must also point to this new node
If the list was not empty
Make old head's prev point to new node
Increment size
Increment modCount

The key point is: Head insertion does not move other elements. It only updates a few references.

Inserting at Tail: linkLast

Tail insertion is symmetric:

Java

        void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
                first = newNode;
        else
                l.next = newNode;
        size++;
        modCount++;
}

Logic:

Save old tail l
New node's prev points to old tail
New node's next is null, because it becomes tail
Update last
If list was empty, first also points to it
Otherwise old tail's next points to it
Update size and modCount

That is why LinkedList naturally handles tail insertion.

Inserting in Middle: linkBefore

If insertion is neither head nor tail, but before a given node, source logic is roughly:

Java

        void linkBefore(E e, Node<E> succ) {
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
                first = newNode;
        else
                pred.next = newNode;
        size++;
        modCount++;
}

The key is succ, the successor node, meaning "insert before whom".

Suppose current list is A <-> B <-> C and we insert X before B:

succ is B
pred is A
New X: prev = A
New X: next = B
Change A.next to X
Change B.prev to X

Result becomes A <-> X <-> B <-> C.

Only a few references are changed.

Removing a Node: unlink

Removal is another core linked-list operation. For removing a known node x, the idea is:

Java

        E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
                first = next;
        } else {
                prev.next = next;
                x.prev = null;
        }

        if (next == null) {
                last = prev;
        } else {
                next.prev = prev;
                x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
}

This method is very important.

Suppose removing middle node B from A <-> B <-> C. After removal it should be A <-> C.

In source terms:

Find B's prev, which is A
Find B's next, which is C
Set A.next = C
Set C.prev = A

Now B is detached from the chain.

Then source code also does these important steps:

x.prev = null
x.next = null
x.item = null

Main purpose: help GC reclaim faster and avoid meaningless retained references.

Why Removing a Known Node Is Fast

Because unlike ArrayList, no bulk shifting is needed.

Array deletion shifts all following elements left. Linked list deletion just reconnects neighbors.

So if you already have the target node, the unlink itself is O(1).

But there is a critical precondition: you must first get that node.

If you call remove(index), before unlinking you still need to locate the node at index, and that lookup is usually O(n).

So the precise source-level statement is:

Unlinking known node is O(1)
Locating node is usually O(n)
So remove by index is overall O(n)

Why Index Access Is Slow

Look at node(index), one of the key LinkedList methods:

Java

        Node<E> node(int index) {
        if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                        x = x.next;
                return x;
        } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                        x = x.prev;
                return x;
        }
}

Meaning:

If index is in first half
Traverse forward from head
If index is in second half
Traverse backward from tail

Example: If size = 100 and index = 80, source code does not walk 80 steps from first; it starts from last and walks backward about 19 steps.

This is an optimization, but the nature is unchanged: it is still linear lookup, not O(1) array addressing.

So get(index), set(index), add(index, e), and remove(index) all depend on node(index).

Essence of get, set, add, remove

You can compress these common methods into one pattern.

get(index)

Java

        public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

Check index, locate node via node(index), return item. The bottleneck is node(index).

set(index, element)

Java

        public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
}

Mutation itself is quick, but locating node is slow, so overall still O(n).

add(index, element)

Java

        public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
        linkLast(element);
        else
        linkBefore(element, node(index));
}

If append at end, call linkLast directly. Otherwise locate with node(index), then linkBefore.

remove(index)

Java

        public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

Locate first, then unlink.

You will notice almost all index-based bottlenecks are not in the mutation itself, but in locating the node.

Why LinkedList Is Not Good for Random Access

The source-level reason is straightforward:

It has no array-style direct index addressing. It can only move step by step along next or prev. Each get(index) may re-traverse from head or tail.

So if you write:

Java

        for (int i = 0; i < list.size(); i++) {
        list.get(i);
}

For ArrayList, that is usually fine. For LinkedList, performance may be very poor, because each get(i) walks the chain, and total cost can approach O(n^2).

So for LinkedList traversal, prefer:

for-each
Iterator
Sequential traversal from head to tail

Instead of repeatedly reading by index.

Why Deque Fits It Naturally

LinkedList implements Deque, which perfectly matches its structure.

Examples:

addFirst
Essentially calls linkFirst
addLast
Essentially calls linkLast
removeFirst
Essentially removes first
removeLast
Essentially removes last
peekFirst
Returns first.item
peekLast
Returns last.item

Because head and tail pointers are always maintained, LinkedList is naturally convenient as a double-ended queue.

That is one of its typical source-level design values: it is not only a List, but also very suitable as a Deque.

Why Iterator Traversal Is Sequential

Inside LinkedList there is an iterator implementation like ListItr. It usually maintains:

next
The next node to return
lastReturned
The node returned in previous step
nextIndex
Current iterator position
expectedModCount
Modification version captured when iterator is created

Its next() is basically:

Check for concurrent modification Return current node value Move pointer to next node

Since the list itself is sequentially linked, iterator just follows next.

modCount and Fail-Fast

This is another high-frequency source concept.

In LinkedList's inheritance chain there is modCount, representing structural modification count. It usually increases when operations like these happen:

add
remove
clear
Other structural changes

When an iterator is created, it records expectedModCount.

Then each iteration checks:

Current modCount Whether it equals expectedModCount

If not equal, it means the list was modified externally during iteration, and it throws ConcurrentModificationException.

That is the fail-fast mechanism.

Its purpose is not thread safety, but to expose misuse early.

For example, if you iterate with an iterator and also call list.remove() directly, this exception may occur.

A Minimal Source-Level Mental Model

Java

        class MyLinkedList<E> {
        Node<E> first;
        Node<E> last;
        int size;

        static class Node<E> {
                E item;
                Node<E> prev;
                Node<E> next;
        }
}

Use Cases

As a normal List:

add
get
set
remove
size

As a queue:

offer
poll
peek

As a deque:

offerFirst
offerLast
pollFirst
pollLast
peekFirst
peekLast

As a stack:

push
pop
peek

Everything it does is basically:

Head insertion: update first and old head's prev
Tail insertion: update last and old tail's next
Middle insertion: reconnect predecessor, new node, successor
Deletion: reconnect neighbors around target node
Index access: walk from head or tail to locate node
Iterator: visit one by one along next

Fonnpo

The Complete Spring Framework Guide

Detailed Analysis of HashMap

Detailed Analysis of ArrayList