Unveiling Java’s LinkedList: Inside the Double‑Linked List Implementation

In the previous article we examined the source of ArrayList, which is backed by an array. This piece turns its focus to another frequently used class, LinkedList , with all analysis based on Java 8.

Class Overview

LinkedList implements the Deque and Serializable interfaces, meaning it can be used as a queue and can be serialized for transmission or storage.

Member Variables

The class maintains an int size field indicating the number of elements, a Node<E> first reference to the head node, and a Node<E> last reference to the tail node.

The internal static class Node<E> contains three fields: E item to store the element, Node<E> next pointing to the next node, and Node<E> prev pointing to the previous node.

LinkedList vs. ArrayList

Unlike ArrayList, which stores elements in a contiguous array and suffers from costly array resizing and element shifting, LinkedList links nodes together via next and prev pointers. Insertion or removal only rewires a few pointers, giving it high efficiency for frequent modifications, but it lacks O(1) random access because traversal from the head (or tail) is required.

Constructors

The no‑argument constructor creates an empty list; the constructor accepting a Collection delegates to addAll, which copies the collection’s elements into the list.

Core Methods

add() methods ultimately call linkLast to append at the tail or linkBefore to insert before a given node, updating surrounding pointers and size counters.

remove() methods locate the target node (by value or index) and invoke unlink, which detaches the node by reconnecting its predecessor and successor, clears its fields, and decrements the size.

clear() iterates from the head, nullifying each node’s item, then resets first, last, and size to zero.

get(int index) checks bounds, then uses node(int index) to retrieve the node, traversing from the nearer end (head or tail) for efficiency.

set(int index, E element) also validates the index, fetches the node via node, replaces its item, and returns the previous value.

Conclusion

LinkedList is implemented as a doubly‑linked list where each element resides in a node linked by forward and backward pointers. This structure provides fast insertion and deletion but requires linear traversal for element lookup, making it suitable for scenarios with heavy modifications and relatively modest lookup demands.