Singly linked list

1
2
3
4
5
6
7
8
9
10
11

Head Reference
     |
     v
+----------+------+      +----------+------+      +----------+------+
| Data: 10 | next-+----> | Data: 20 | next-+----> | Data: 30 | null |
+----------+------+      +----------+------+      +----------+------+
  Addr: 0x1000             Addr: 0x4800             Addr: 0x9200
  (Heap Block A)           (Heap Block B)           (Heap Block C)

Notice: Nodes reside at arbitrary heap addresses!
To reach Data 30, the CPU must follow 2 pointer hops (0x1000 -> 0x4800 -> 0x9200).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// Canonical Singly Linked List Node Definition
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode() {}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Standard List (Deleting head requires special if-condition):
Head
 |
 v
[ 10 ] ----> [ 20 ] ----> [ 30 ] -> null

Sentinel Architecture (Every real node has a guaranteed predecessor!):
Dummy Head            Original Head
+-----------+       +-----------+       +-----------+
| Val:  -1  | ----> | Val:  10  | ----> | Val:  20  | ----> null
+-----------+       +-----------+       +-----------+
      ^
      |-- dummy.next always tracks the real head!
          Deleting node 10: dummy.next = dummy.next.next (Zero edge cases!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Eliminating head deletion edge cases using a Sentinel Node
public ListNode removeElements(ListNode head, int targetVal) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode curr = dummy;

    while (curr.next != null) {
        if (curr.next.val == targetVal) {
            // Unlink matching node: predecessor points around target
            curr.next = curr.next.next;
        } else {
            // Only advance curr when no deletion occurred
            curr = curr.next;
        }
    }

    return dummy.next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

--- INSERTION AFTER NODE 'PREV' ---
Initial State:
  [ Prev ] --------------------------> [ NextNode ]
              [ NewNode ]

Step 1: newNode.next = prev.next;
  [ Prev ] --------------------------> [ NextNode ]
              [ NewNode ] ------------->^

Step 2: prev.next = newNode;
  [ Prev ] ---------> [ NewNode ] ----> [ NextNode ]
  (Order matters! If step 2 runs first, NextNode is lost forever!)

--- DELETION AFTER NODE 'PREV' ---
Initial State:
  [ Prev ] ---------> [ Target ] -----> [ NextNode ]

Step 1: prev.next = prev.next.next;
  [ Prev ] ---------------------------> [ NextNode ]
                      [ Target ] (no references -> Garbage Collected!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public class MyLinkedList {
    private static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    private final Node dummy;
    private int size;

    public MyLinkedList() {
        dummy = new Node(-1);
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node curr = dummy.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node newNode = new Node(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = prev.next.next;
        size--;
    }

    public int size() {
        return size;
    }
}