Nodes and References

1.The node chain

Each ListNode holds a value and a reference next to the following node. The list is known only by its head; the last node's next is null. Nodes can sit anywhere in memory.

To reach position i you must follow i links: O(n) access. But once you hold a node, inserting or removing after it is O(1): change a couple of references.

2.Building and printing a list

A tiny helper to build a list from values and print it saves time in every lab.

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

public class Main {
    static ListNode build(int... values) {
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int v : values) { tail.next = new ListNode(v); tail = tail.next; }
        return dummy.next;
    }
    static String show(ListNode head) {
        StringBuilder sb = new StringBuilder();
        for (ListNode n = head; n != null; n = n.next) sb.append(n.val).append(" -> ");
        return sb.append("null").toString();
    }
    public static void main(String[] args) {
        ListNode head = build(4, 7, 1);
        System.out.println(show(head));
        head.next = head.next.next;          // remove 7 in O(1)
        System.out.println(show(head));
    }
}

4 -> 7 -> 1 -> null
4 -> 1 -> null

3.Array or linked list?

Arrays: O(1) index access, cache-friendly, but O(n) insert/delete in the middle. Linked lists: O(n) access, extra memory per node and poor cache use, but O(1) insert/delete once you're at the spot. In Java practice, ArrayList and ArrayDeque win most of the time; linked lists matter inside other structures, like the LRU cache (hash map + doubly linked list).