Linked Lists

The node: a value plus a pointer

A linked list is built from nodes. A node is a tiny object with two fields: the value it stores, and a reference to the next node in the chain. In Java, a reference is just a variable that points at another object, so the class is almost embarrassingly short.

The list itself is represented by a single reference to the first node, traditionally called the head. If the head is null, the list is empty. The last node's next field is null, which is how you know the chain has ended. There is no length field built in and no index; the structure is nothing but nodes pointing at nodes.

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

Traversal: the only way to get anywhere

With an array you can write arr[500] and land there instantly, because the elements sit side by side in memory and the position can be computed. A linked list offers no such shortcut. To reach the fifth node you must start at the head and follow next four times. This is called traversal, and it is the fundamental linked-list motion: a loop that advances a current pointer until it hits null.

Because of this, reading element i costs O(i) time (meaning the work grows in proportion to how far in you go) and searching the whole list is O(n), work proportional to the list's length. The classic traversal loop below appears, in some disguise, in nearly every linked-list problem you will ever solve. Notice that we move a separate variable, curr, rather than the head itself; if we advanced head we would lose our only handle on the list.

ListNode curr = head;
while (curr != null) {
    System.out.println(curr.val);
    curr = curr.next;
}

The dummy head trick

Insertions and deletions near the front of a list are annoying for one reason: the head is a special case. Deleting the third node means rewiring the second node's next pointer, but deleting the first node means changing the head variable itself. Two different kinds of code for one logical operation invites bugs.

The fix is a dummy head (also called a sentinel): a throwaway node placed before the real first node. Now every real node (including the first) has a node in front of it, so one uniform piece of code handles all positions. When you are done, the real list is dummy.next. This one-line trick removes an entire class of edge cases, and interviewers notice when you use it.

ListNode removeAll(ListNode head, int target) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == target) {
            prev.next = prev.next.next;
        } else {
            prev = prev.next;
        }
    }
    return dummy.next;
}

Arrays vs. linked lists: the honest trade-off

Here is the scorecard. Arrays win at random access: reading any index is O(1), constant time no matter how big the array. Linked lists lose there badly, at O(n). Linked lists win at insertion and deletion when you are already standing at the spot: rewiring pointers is O(1), while an array must shift every later element, which is O(n). Both need O(n) to find an arbitrary value.

In practice, arrays (and Java's ArrayList) win more often than beginners expect, because modern hardware reads consecutive memory much faster than memory scattered across the heap. Linked lists shine in specific roles: implementing queues and deques, splicing chains together without copying, and interview problems about reversing, cycles, and merging. Speaking of those roles. The next structures you will meet, stacks and queues, are exactly where these linear building blocks start doing real work.

Frequently asked