Memory and implementation

In Java, a Node variable holds a reference to a heap object, never the object itself, and next is just another reference. That is why linked lists need no pointer arithmetic and cannot corrupt memory: a reference is either null or points at a live node. Passing a node to a method passes the reference by value, so the method can change the node's fields but cannot change which node the caller's variable points to.

This is also why methods that may change the head return the new head.

1static void setValue(Node n) { n.val = 99; }          // changes the caller's node
2static void replace(Node n) { n = new Node(1); }       // only rebinds the local copy of the reference
3static Node insertFront(Node head, int v) { Node n = new Node(v); n.next = head; return n; }   // return the new head

A dummy node is a temporary extra node placed before the real head. It gives every real node, including the first, a predecessor, so insertions and deletions at the head need no special case, and a builder can append to tail without checking for an empty result. Return dummy.next at the end. It costs one allocation and removes a whole class of null bugs.

The merge, partition and swap-pairs examples all use one.

1static Node removeAll(Node head, int x) {
2    Node dummy = new Node(0); dummy.next = head;
3    for (Node prev = dummy; prev.next != null; ) {
4        if (prev.next.val == x) prev.next = prev.next.next;   // works for the head too
5        else prev = prev.next;
6    }
7    return dummy.next;
8}

A sentinel is a permanent dummy node that stays in the list: head and tail sentinels in a doubly linked list, or a sentinel that terminates a search. A sentinel at the end of a list lets you write while (cur.val != x) cur = cur.next without a null check, by storing the search value in the sentinel first. The data structure then has no empty-list special cases.

The difference from a dummy: a sentinel is part of the structure, a dummy is local scaffolding.

1static boolean containsWithSentinel(Node head, Node sentinel, int x) {   // the list ends at the sentinel
2    sentinel.val = x;                          // guarantees the loop stops
3    Node cur = head;
4    while (cur.val != x) cur = cur.next;
5    return cur != sentinel;                    // found a real node, not the sentinel
6}

Java has no delete. When you unlink a node and nothing references it any more, it is unreachable and the garbage collector reclaims it, automatically and at an unspecified time. A node is still alive if anything still references it, including a stale next of the removed node itself pointing into the list. Clearing the removed node's next is not required for correctness (the collector handles chains), but it avoids keeping a long tail alive through a single stray reference.

A leak happens when you keep references you no longer need, for example in a cache.

1static Node removeFirst(Node head) {
2    if (head == null) return null;
3    Node next = head.next;
4    head.next = null;                // help the GC: the old head no longer pins the rest of the list
5    return next;
6}

Arrays win on indexed access, memory per element, cache behaviour and iteration speed. Linked lists win only when you already hold a node and need O(1) insertion or removal at that position (LRU caches, splicing, queues with O(1) ends), or when elements are huge and must not move. In practice ArrayList and ArrayDeque beat LinkedList for almost every workload, even with many insertions, because the cost of cache misses and allocation dominates.

Compare reading element k in both structures.

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}