PK

PKBytes

Explore tracks
Chapter 11: Linked Lists
11.02Beginner / Intermediate8 topics20 min7 interactive animations

Singly linked operations

The core operations on a singly linked list: insert at the head, tail and an index, delete the head, tail or a value, search, traverse and reverse, with the pointer updates drawn step by step.

Learning goals

  • Insert and delete with the correct order of pointer updates
  • Know which operations are O(1) and which need a walk
  • Reverse a list in place

Prerequisites

Node fundamentals
11.02.1

Insert head

Inserting at the head creates a node, points it at the old head and makes it the new head: two assignments, O(1), independent of the list length. The order matters: set n.next = head before head = n, or the old list is lost.

Choose Insert at head in the animation.

Java
1static Node insertHead(Node head, int v) {
2    Node n = new Node(v);
3    n.next = head;          // first: point the new node at the old list
4    return n;               // second: the new node becomes the head
5}

Singly linked list: insert and delete

Interactive · edit the input

Your input

Try

linked list · 4 nodes

10
20
30
40
null
head
curr / prevNew nodeUnlinked node (garbage)Match
Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7
Java
1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

4

head

10

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1length=4 head=10Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2L11length=4 head=10 i=0Walk 1 step to reach the node before position 2.
3L11length=4 head=10 i=1prev = 20.
4L12length=5 head=10Create node 25; it is not linked yet.
5L12length=5 head=10n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6L12length=5 head=10prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7L12return=[10, 20, 25, 30, 40]Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).
11.02.2

Insert tail

Appending to a list without a tail pointer walks to the last node (O(n)) and links the new node after it. An empty list is a special case: the new node becomes the head. With a stored tail reference the same operation is O(1).

Run Insert at tail and count the walking steps.

Java
1static Node insertTail(Node head, int v) {
2    Node n = new Node(v);
3    if (head == null) return n;
4    Node cur = head;
5    while (cur.next != null) cur = cur.next;      // walk to the last node
6    cur.next = n;
7    return head;
8}

Singly linked list: insert and delete

Interactive · edit the input

Your input

Try

linked list · 4 nodes

10
20
30
40
null
head
curr / prevNew nodeUnlinked node (garbage)Match
Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7
Java
1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

4

head

10

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1length=4 head=10Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2L11length=4 head=10 i=0Walk 1 step to reach the node before position 2.
3L11length=4 head=10 i=1prev = 20.
4L12length=5 head=10Create node 25; it is not linked yet.
5L12length=5 head=10n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6L12length=5 head=10prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7L12return=[10, 20, 25, 30, 40]Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).
11.02.3

Insert at index

To insert at position i, stop at the node before the gap (position i - 1), point the new node at that node's successor, and then point the node before it at the new node. Reversing those two writes would orphan the rest of the list. Cost O(i) for the walk, O(1) for the splice; index 0 is the head case.

Insert at index 2 is the default preset.

Java
1static Node insertAt(Node head, int index, int v) {
2    if (index == 0) return insertHead(head, v);
3    Node prev = head;
4    for (int i = 0; i < index - 1; i++) prev = prev.next;   // node before the gap
5    Node n = new Node(v);
6    n.next = prev.next;                                     // 1) link the new node to the rest
7    prev.next = n;                                          // 2) splice it in
8    return head;
9}

Singly linked list: insert and delete

Interactive · edit the input

Your input

Try

linked list · 4 nodes

10
20
30
40
null
head
curr / prevNew nodeUnlinked node (garbage)Match
Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7
Java
1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

4

head

10

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1length=4 head=10Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2L11length=4 head=10 i=0Walk 1 step to reach the node before position 2.
3L11length=4 head=10 i=1prev = 20.
4L12length=5 head=10Create node 25; it is not linked yet.
5L12length=5 head=10n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6L12length=5 head=10prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7L12return=[10, 20, 25, 30, 40]Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).
11.02.4

Delete head/tail

Deleting the head is one assignment: head = head.next, O(1). Deleting the tail needs the second-to-last node (the one whose next.next is null) and sets its next to null: O(n), because a singly linked list cannot step backwards. A one-element list becomes empty.

Try Delete tail and compare it with Delete head.

Java
1static Node deleteHead(Node head) { return head == null ? null : head.next; }
2static Node deleteTail(Node head) {
3    if (head == null || head.next == null) return null;
4    Node cur = head;
5    while (cur.next.next != null) cur = cur.next;      // second-to-last node
6    cur.next = null;
7    return head;
8}

Singly linked list: insert and delete

Interactive · edit the input

Your input

Try

linked list · 4 nodes

10
20
30
40
null
head
curr / prevNew nodeUnlinked node (garbage)Match
Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7
Java
1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

4

head

10

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1length=4 head=10Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2L11length=4 head=10 i=0Walk 1 step to reach the node before position 2.
3L11length=4 head=10 i=1prev = 20.
4L12length=5 head=10Create node 25; it is not linked yet.
5L12length=5 head=10n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6L12length=5 head=10prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7L12return=[10, 20, 25, 30, 40]Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).
11.02.5

Delete by value

To delete the first node holding x, walk with a reference to the node before the candidate: when cur.next.val == x, set cur.next = cur.next.next to bypass it. The head needs a separate check, because nothing precedes it. A dummy node in front of the head removes that special case. O(n).

Try Delete first node with value and the not-found preset.

Java
1static Node deleteValue(Node head, int x) {
2    if (head == null) return null;
3    if (head.val == x) return head.next;
4    Node cur = head;
5    while (cur.next != null && cur.next.val != x) cur = cur.next;
6    if (cur.next != null) cur.next = cur.next.next;   // bypass the node: it becomes garbage
7    return head;
8}

Singly linked list: insert and delete

Interactive · edit the input

Your input

Try

linked list · 4 nodes

10
20
30
40
null
head
curr / prevNew nodeUnlinked node (garbage)Match
Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7
Java
1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

4

head

10

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L1length=4 head=10Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2L11length=4 head=10 i=0Walk 1 step to reach the node before position 2.
3L11length=4 head=10 i=1prev = 20.
4L12length=5 head=10Create node 25; it is not linked yet.
5L12length=5 head=10n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6L12length=5 head=10prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7L12return=[10, 20, 25, 30, 40]Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).
11.02.7

Traverse

Traversal visits every node from the head with a single cur reference: for (Node cur = head; cur != null; cur = cur.next). It is O(n) time and O(1) space. Do not modify head itself while traversing, or the list is lost; use a separate cursor. Recursion also works but uses O(n) stack.

The array animation shows the cost difference when reaching element k.

Java
1static void print(Node head) {
2    StringBuilder sb = new StringBuilder();
3    for (Node cur = head; cur != null; cur = cur.next) sb.append(cur.val).append(cur.next != null ? " -> " : "");
4    System.out.println(sb);
5}
6static void printRecursive(Node n) { if (n == null) return; System.out.print(n.val + " "); printRecursive(n.next); }

Reading element k: array vs linked list

Interactive · edit the input

Your input

Try

array memory (value, address)

12@1000
7@1004
31@1008
4@1012
19@1016
8@1020
25@1024
Setup

The 7 values sit in consecutive memory cells, 4 bytes apart, starting at address 1000.

Step 1 / 3
Java
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}

Live state

0 memory reads

k

5

base

1000

No condition evaluated on this step
Execution trace (dry run table)Show 3 steps
StepLineStateWhat happens
1L1k=5 base=1000The 7 values sit in consecutive memory cells, 4 bytes apart, starting at address 1000.
2L2k=5 address=1020Address = 1000 + 5 × 4 = 1020. One multiplication and one addition give the location, no matter how large k is.
3L2return=8return 8 with a single memory read: O(1) random access.
11.02.8

Reverse

Reversing flips every next pointer using three references: save next, point curr.next at prev, then advance both. The values never move. After the loop prev is the new head. O(n) time and O(1) space.

Step through the pointer flips; the arrows turn around one at a time.

Java
1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;      // save the rest
5        curr.next = prev;           // flip
6        prev = curr; curr = next;   // advance
7    }
8    return prev;
9}

Reversing a linked list by flipping pointers

Interactive · edit the input

Your input

Try

linked list · 5 nodes

1
2
3
4
5
null
head
Node being flippedAlready reversed
Setup

Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.

Step 1 / 17
Java
1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;          // save the rest of the list
5        curr.next = prev;               // flip the pointer
6        prev = curr; curr = next;       // step forward
7    }
8    return prev;                        // prev is the new head
9}
10static Node reverseBetween(Node head, int left, int right) {      // 1-based positions
11    Node dummy = new Node(0); dummy.next = head; Node pre = dummy;
12    for (int i = 1; i < left; i++) pre = pre.next;                // node before the segment
13    Node curr = pre.next;
14    for (int i = 0; i < right - left; i++) {
15        Node next = curr.next;
16        curr.next = next.next; next.next = pre.next; pre.next = next;   // move next to the front of the segment
17    }
18    return dummy.next;
19}
20static Node reverseKGroup(Node head, int k) {                     // groups shorter than k stay as they are
21    Node dummy = new Node(0); dummy.next = head; Node groupPrev = dummy;
22    while (true) {
23        Node kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next;
24        if (kth == null) break;                                   // fewer than k nodes left
25        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
26        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
27        groupPrev.next = kth; groupPrev = groupStart;
28    }
29    return dummy.next;
30}

Live state

head

1

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L2head=1Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.
2L4head=1Save next = 2 before changing curr.next, or the rest of the list would be lost.
3L5head=1curr.next = prev: node 1 now points to null (it becomes the tail).
4L6head=1Step both pointers forward.
5L4head=1Save next = 3 before changing curr.next, or the rest of the list would be lost.
6L5head=1curr.next = prev: node 2 now points back at 1.
7L6head=1Step both pointers forward.
8L4head=1Save next = 4 before changing curr.next, or the rest of the list would be lost.
9L5head=1curr.next = prev: node 3 now points back at 2.
10L6head=1Step both pointers forward.
11L4head=1Save next = 5 before changing curr.next, or the rest of the list would be lost.
12L5head=1curr.next = prev: node 4 now points back at 3.
13L6head=1Step both pointers forward.
14L4head=1Save next = null before changing curr.next, or the rest of the list would be lost.
15L5head=1curr.next = prev: node 5 now points back at 4.
16L6head=1Step both pointers forward.
17L8head=5 return=[5, 4, 3, 2, 1]Return prev as the new head: [5, 4, 3, 2, 1].

Practice ladder

Now try it yourself

Easy

  • Insert 5 at the head of 10 → 20
  • Delete the head of a one-node list

Medium

  • Delete the first node with value 30 from 10 → 20 → 30 → 40
  • Reverse 1 → 2 → 3 by hand writing prev, curr, next at each step

Advanced

  • Delete every node with a given value in one pass using a dummy node

Key takeaways

  • Link the new node to the rest first, then splice it in.
  • Head operations are O(1); anything that needs the previous node walks O(n).
  • Reverse with three pointers: save next, flip, advance.