Linked Lists

From contiguous to connected

In Arrays and Strings, you worked with data stored in a neat row: index 0, index 1, index 2, and so on.

A linked list changes the mental model. Instead of items living side-by-side in memory, each item points to the next item.

Why this matters for interviews:

• It tests whether you understand references/pointers, not just indexes.
• It forces careful thinking about edge cases like empty lists and single-node lists.
• It appears in classic MAANG-style questions: reverse a list, detect cycles, merge lists, remove nodes, and find the middle.

Today, we’ll focus on the core linked list model and the pointer moves you need before later topics like stacks, queues, trees, and graphs.

A linked list is a chain of nodes

A singly linked list node usually stores two things:

• value: the data
• next: a reference to the next node

head
 ↓
[10 | next] → [20 | next] → [30 | null]

The first node is called the head.

The last node points to null, which means: “the list ends here.”

Key contrast from arrays

In an array, you can jump directly to arr[5].

In a linked list, you must start at head and follow next references one by one until you arrive.

You have a singly linked list with 1,000 nodes and only a reference to head.

Which statement is most accurate?

Building nodes in Java

In Java, a linked list node is usually represented as a small class.

The important idea: next does not contain the next value directly. It stores a reference to another Node object.

This is the Java version of the arrow in the diagram.

```java
public class Main {
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);

        Node current = head;
        while (current != null) {
            System.out.print(current.value);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
    }
}
```

Pointer rewiring

Linked list operations are mostly about changing arrows.

Insert at front

newNode.next = head
head = newNode

Delete a node

To remove a node, you usually make the previous node skip it:

prev.next = current.next

The tricky part is not the assignment itself. The tricky part is handling cases like:

• deleting from an empty list
• deleting the head
• deleting a value that does not exist
• updating references in the correct order

```java
public class Main {
    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }

    static Node addFirst(Node head, int value) {
        Node newNode = new Node(value);
        newNode.next = head;
        return newNode;
    }

    static Node deleteFirst(Node head, int target) {
        if (head == null) return null;
        if (head.value == target) return head.next;

        Node current = head;
        while (current.next != null && current.next.value != target) {
            current = current.next;
        }

        if (current.next != null) {
            current.next = current.next.next;
        }
        return head;
    }

    static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.value);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = null;
        head = addFirst(head, 30);
        head = addFirst(head, 20);
        head = addFirst(head, 10);

        printList(head);
        head = deleteFirst(head, 20);
        printList(head);
    }
}
```

True or false:

If a singly linked list stores its size, then accessing the node at index k becomes O(1).

Interview thinking: move references, not indexes

With arrays, you often use indexes like left, right, or i.

With linked lists, you usually use node references:

• current to walk through the list
• previous to remember the node behind you
• next to avoid losing the rest of the list
• slow and fast for “runner” style problems

Example mental model for two references:

prev     current
 ↓         ↓
[10]  →  [20]  →  [30]  →  null

This is where beginners often level up: instead of asking “what index am I at?”, ask “which node reference do I need to keep safe?”

Classic linked list move: reversal

Reversing a singly linked list is a must-know pattern.

The goal:

Before: 1 → 2 → 3 → null
After:  3 → 2 → 1 → null

The danger: if you change current.next too early, you can lose access to the rest of the list.

So each loop does three careful steps:

1. Save next
2. Point current.next backward to prev
3. Move prev and current forward

```java
public class Main {
    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
    }

    static Node reverse(Node head) {
        Node prev = null;
        Node current = head;

        while (current != null) {
            Node next = current.next;  // save the rest
            current.next = prev;       // reverse the arrow
            prev = current;            // move prev forward
            current = next;            // move current forward
        }

        return prev;
    }

    static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.value);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        printList(head);
        head = reverse(head);
        printList(head);
    }
}
```

In iterative linked list reversal, before changing current.next, you should store the rest of the list in a variable commonly named _____.

What you should remember

Linked lists are not “better arrays.” They are a different trade-off.

Strengths

• Efficient insertion/deletion when you already have the relevant node reference
• Flexible size without needing contiguous memory
• Great for practicing reference manipulation

Costs

• No O(1) random access by index
• Extra memory for references
• More edge cases than arrays

Interview checklist

Before coding, ask:

• Can head be null?
• What happens with one node?
• Am I deleting or changing the head?
• Do I need prev, current, and next?
• Could I lose the rest of the list after rewiring?

Next, we’ll build on this “references over indexes” mindset when we study Stacks and Queues, two structures that often use linked-list-like thinking under the hood.