LinkedList

LinkedList is a doubly-linked list implementation of the List and Deque interfaces, providing sequential access with O(1) insertion/removal at both ends.

Source Code #

View Source on GitHub

Core Implementation #

LinkedList uses a doubly-linked list structure with header and size tracking:

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

Implementation Details #

Node Structure #

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

Construction #

public LinkedList() {
    // Empty constructor - first and last are null, size is 0
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Link Operations (Core Internal Methods) #

// Link as first element
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++;
}

// Link as last element
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++;
}

// Insert before non-null node
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++;
}

Unlink Operations #

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

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

// Unlink arbitrary node
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;
}

Add Operations #

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

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

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

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

Get Operations #

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

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

Node Access (Optimized for Proximity) #

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

Remove Operations #

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

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

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

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

Queue Operations (Deque Interface) #

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public boolean offer(E e) {
    return add(e);
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

Stack Operations #

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

public E pop() {
    return removeFirst();
}

Bulk Operations #

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

Clear Operation #

public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

Iteration Support #

public Iterator<E> iterator() {
    return new ListItr(0);
}

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;
    
    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    
    public boolean hasNext() {
        return nextIndex < size;
    }
    
    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
    
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
        
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }
    
    public int nextIndex() {
        return nextIndex;
    }
    
    public int previousIndex() {
        return nextIndex - 1;
    }
    
    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();
        
        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }
    
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }
    
    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Descending Iterator #

public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    
    public E next() {
        return itr.previous();
    }
    
    public void remove() {
        itr.remove();
    }
}

Serialization #

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    
    s.writeInt(size);
    
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    s.defaultReadObject();
    
    int size = s.readInt();
    
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

Performance Characteristics #

Time Complexity:
- get(int index): O(n) - must traverse from nearest end
- add(E e): O(1) - linking at end
- add(int index, E e): O(n) - must traverse to index
- remove(int index): O(n) - must traverse to index
- contains(Object o): O(n) - must traverse entire list
- addFirst()/addLast(): O(1)
- removeFirst()/removeLast(): O(1)
Space Complexity: O(n) where n is the number of elements
Memory Overhead: ~32 bytes per node (prev, next references, item, plus object header)

Best Practices #

Use for frequent insertions/removals: LinkedList excels when you need to frequently add/remove at both ends
Prefer ArrayList for random access: LinkedList has O(n) random access vs ArrayList’s O(1)
Use as Queue/Deque: LinkedList implements both Queue and Deque interfaces efficiently
Consider memory usage: LinkedList has higher per-element overhead than ArrayList
Leverage stack operations: Use push()/pop() for LIFO behavior

Common Pitfalls #

Performance issues with random access: get(int index) is O(n), not O(1)
Memory overhead: Each node has prev/next pointers (24 bytes overhead per element)
ConcurrentModificationException: Modifying list while iterating
Null elements: LinkedList allows null elements, which can cause NPE in some operations
Iterator invalidation: Removing elements outside iterator invalidates iterator state