Understanding Java LinkedList: Definition, Implementation, and Core Operations

Introduction

The article introduces the Java LinkedList collection, a doubly‑linked list implementation that implements List, Deque, Cloneable, and Serializable. It highlights that, unlike ArrayList, LinkedList does not have a fixed size and grows by linking nodes.

Definition and Class Signature

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

Internal Fields

// Number of elements (nodes) in the list
transient int size = 0;
/** Pointer to the first node */
transient Node<E> first;
/** Pointer to the last node */
transient Node<E> last;

Node Inner Class

private static class Node<E> {
    E item;               // stored element
    Node<E> next;         // reference to next node
    Node<E> prev;         // reference to previous node
    // Constructor
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Constructors

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

The default constructor creates an empty list, while the second constructor populates the list with all elements from an existing collection.

Adding Elements

addFirst(E e) – inserts an 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) and add(E e) – append an element to the tail.

public void addLast(E e) { linkLast(e); }
public boolean add(E e) { linkLast(e); return true; }
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(int index, E element) – inserts an element at a specific 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++;
}

Removing Elements

Removal methods ( remove(), removeFirst(), removeLast(), remove(int index), remove(Object o)) adjust the predecessor and successor links similarly to the addition methods.

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

Searching Elements

Methods such as getFirst(), getLast(), get(int index), and indexOf(Object o) retrieve elements or their positions.

Traversing the List

For‑loop traversal using get(i) (inefficient for large lists because each call walks from the head or tail).

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " "); // A B C D
}

Iterator traversal – avoids repeated linear scans.

Iterator<String> it = list.listIterator();
while (it.hasNext()) {
    System.out.print(it.next() + " "); // A B C D
}
// Reverse iterator
Iterator<String> rev = list.descendingIterator();
while (rev.hasNext()) {
    System.out.print(rev.next() + " "); // D C B A
}

The internal ListItr class implements ListIterator and maintains next, prev, and index state, providing hasNext(), next(), hasPrevious(), previous(), and modification methods ( remove(), set(E), add(E)).

Concurrent Modification Check

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

All mutating operations increment modCount; iterators compare this value with expectedModCount to detect illegal concurrent modifications, throwing an exception if they differ.

References

The article cites several online resources and the book Effective Java for further reading.