Detailed Analysis of Java LinkedList Implementation (JDK 1.8)

LinkedList is an ordered sequence implemented as a doubly‑linked list. It allows efficient insertion and removal at any position, is not thread‑safe, and permits null elements.

Source Code Overview

1. Fields

/**
 * Number of elements in the list
 */
transient int size = 0;

/**
 * Pointer to first node
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

2. Constructors

/**
 * No‑arg constructor
 */
public LinkedList() {}

/**
 * Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

3. Node Class

private static class Node<E> {
    // element value
    E item;
    // next node
    Node<E> next;
    // previous node
    Node<E> prev;

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

Because each node holds both prev and next, the structure is a doubly‑linked list.

4. Adding Elements

addAll(Collection c)

Appends all elements of collection c to the end of the list. If addAll(int index, Collection<? extends E> c) is used, the elements are inserted after the specified index.

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) return false;
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked")
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

addFirst(E e)

Inserts the element at the head of the list.

public void addFirst(E e) {
    linkFirst(e);
}

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++;
}

addLast(E e)

Inserts the element at the tail of the list.

public void addLast(E e) {
    linkLast(e);
}

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++;
}

add(E e)

Appends the element to the end of the list.

public boolean add(E e) {
    linkLast(e);
    return true;
}

add(int index, E element)

Inserts element at the specified position.

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

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++;
}

5. Accessing Elements

get(int index)

Returns the element at the specified position.

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

private Node<E> node(int index) {
    // if index is in first half, start from first
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // start from last
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

getFirst() / getLast()

public E getFirst() {
    final Node<E> f = first;
    if (f == null) throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null) throw new NoSuchElementException();
    return l.item;
}

6. Removing Elements

remove(Object o)

Removes the first occurrence of the specified element.

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

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;
}

remove(int index)

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

removeFirst() / removeLast()

public E removeFirst() {
    final Node<E> f = first;
    if (f == null) throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null;
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

public E removeLast() {
    final Node<E> l = last;
    if (l == null) throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null;
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

7. Modifying Elements

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

8. Comparison with ArrayList

Advantages of LinkedList

No need for capacity expansion; space efficiency is high.

Insertion and removal operations are fast.

Disadvantages of LinkedList

Random access (get by index) is slower because it requires traversal.

Update and search operations are less efficient compared to ArrayList.

Overall, LinkedList is suitable when frequent insertions and deletions are required, while ArrayList excels at random access and iteration performance.