15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The dummy node linked list technique adds one extra node before the real head, so the first real node has a predecessor. Deletion then uses the same prev.next = curr.next update for every node, with no head branch. You return dummy.next, never dummy. It costs O(1) extra space.
| What it is | A temporary helper node whose next is the real head |
|---|---|
| What it removes | The separate branch for changing the head |
| What you return | dummy.next, not dummy |
| Dummy vs sentinel | A dummy exists during one operation; a sentinel stays in the list representation |
| Time and space | O(n) time worst case, O(1) auxiliary space |
You should already be comfortable with these linked-list ideas:
next reference.head refers to the first real node, or is null for an empty list.next reference.The awkward case in deletion is the real head. A middle node has a predecessor that can bypass it:
1[7] -> [4] -> [9]
2 ^
3 predecessorTo remove 4, set the predecessor’s next to the target’s next.
The first real node has no real predecessor:
1head
2 |
3 v
4[4] -> [7] -> nullA dummy node provides a predecessor for the first real node. It is one extra helper node placed before the real head. Its value is not logical list data.
A temporary dummy head exists only while an operation runs. After the operation, return dummy.next, not dummy.
A sentinel node is related but different. It is a designated boundary node that remains part of a list representation after operations finish. This lesson uses a temporary dummy node.
Remove the first value 4 from this list:
1head
2 |
3 v
4[4] -> [7] -> [4] -> nullWithout a helper, the first [4] has no predecessor. Deleting it requires a separate head-deletion branch.
Create a dummy node whose next points to the original head:
1dummy
2 |
3 v
4[sentinel] -> [4] -> [7] -> [4] -> null
5 ^
6 real head = dummy.nextThe first real node now has a predecessor: dummy.
We will remove only the first 4.
Dummy head, step by step: prev starts on the dummy and curr on the first 4. One bypass, prev.next = curr.next, removes the first 4 with no special head case. Return dummy.next: 7, then 4, then null.
dummy.next is the original head.
Set:
1prev = dummy
2curr = dummy.nextSo the references are:
1prev
2 |
3 v
4[sentinel] -> [4] -> [7] -> [4] -> null
5 ^
6 currprev is immediately before curr.
curr.value is 4, which matches the target.
Do not move prev. It must remain the node immediately before curr.
Use one bypass update:
1prev.next = curr.nextHere, prev is dummy, and curr.next is the node containing 7.
Before the update:
1[sentinel] -> [4] -> [7] -> [4] -> nullAfter the update:
1[sentinel] -> [7] -> [4] -> nullThe original first [4] is no longer reachable from dummy.
The new real head is already stored in dummy.next, so no special assignment to head is needed.
Return:
1dummy.nextThe returned list is:
1[7] -> [4] -> nullDo not return dummy, because [sentinel] is helper data, not list data.
During the search, the relationship is:
1... -> prev -> curr -> ...At every search step:
prev is immediately before curr in the chain beginning at dummy.dummy.next identifies the current real head of the list.The loop invariant is that relationship.
Deletion needs the predecessor of the node being removed. When curr is the first real node, its predecessor remains available because prev is dummy.
If curr is not the target, advance both references together:
1prev = curr
2curr = curr.nextThe new prev remains immediately before the new curr.
If curr is the target, do not advance first. While prev still points directly to curr, bypass curr:
1prev.next = curr.nextMake head deletion use the same predecessor-bypass update as other deletions.
dummy and connect it to head.prev to dummy.curr to the first real node, dummy.next.curr exists:
curr.value equals target, set prev.next to curr.next and stop. This removes only the first match.dummy.next.The same steps handle an empty list. If head is null, then dummy.next is null, curr is null, the loop does not run, and the returned value is null.
1Node:
2 value
3 next
4
5function removeFirst(head, target) -> Node or null
6 Input:
7 head: first real node of a singly linked list, or null
8 target: value to remove
9
10 Returns:
11 The head of the real list after removing the first node
12 whose value equals target. Returns null if the result is empty.
13
14 Mutation behavior:
15 If a matching node exists, this function changes one next reference
16 in the existing list. It creates one temporary dummy node.
17 The dummy node is not part of the returned logical list.
18
19 1. dummy = new Node(sentinel, head)
20 // Helper contract: dummy.next is initially the original head.
21
22 2. prev = dummy
23 3. curr = dummy.next
24
25 4. while curr != null
26 5. if curr.value == target
27 6. prev.next = curr.next
28 // prev remains curr's predecessor during this update.
29 7. return dummy.next
30
31 8. prev = curr
32 9. curr = curr.next
33
34 10. return dummy.nextThe loop examines real nodes only. curr begins at dummy.next, not at dummy, so the dummy’s sentinel value is never compared with target.
Use the same input:
1head -> [4] -> [7] -> [4] -> null
2target = 4| Pseudocode line | State |
|---|---|
| 1 | Create dummy = [sentinel | next -> first 4]. |
| 2 | prev = dummy. |
| 3 | curr = dummy.next, so curr is the first [4]. |
| 4 | curr != null is true. Enter the loop. |
| 5 | curr.value == target is true because 4 == 4. |
| 6 | Set prev.next = curr.next. Since prev is dummy and curr.next is [7], dummy.next now points to [7]. |
| 7 | Return dummy.next, which is [7] -> [4] -> null. |
The loop does not advance to the second [4]. The function removes the first occurrence and returns immediately.
We show that removeFirst returns the real list with the first matching target removed, if one exists.
At line 1, dummy.next is set to the original head. The assignment is valid whether head is a real node or null.
At lines 2 and 3:
1prev = dummy
2curr = dummy.nextSo prev is immediately before curr in the chain beginning at dummy. Also, dummy.next identifies the real head. The invariant holds before the loop begins.
Assume the invariant holds at the start of an iteration.
If curr.value does not equal target, lines 8 and 9 move both references forward:
1prev = curr
2curr = curr.nextBefore moving, prev was immediately before curr. After moving, the old curr becomes the new prev, and the node after it becomes the new curr. Thus, prev remains immediately before curr. No link changes, so dummy.next still identifies the real head.
If curr.value equals target, line 6 performs:
1prev.next = curr.nextBecause prev is immediately before curr, this bypasses exactly curr. Nodes before curr remain connected, and nodes after curr remain reachable through prev. If curr was the original head, prev is dummy, so dummy.next becomes the next real node. The function then returns dummy.next, excluding the helper node.
There are two ways the function terminates.
curr becomes null, every real node was examined and none matched. No links were changed, so dummy.next is the unchanged real head. Returning it is correct.The algorithm removes the first occurrence of target when present, leaves the list unchanged when absent, and always returns the real head rather than the helper node.
Let n be the number of real nodes in the input list.
Creating and connecting the dummy node takes constant work:
1dummy = new Node(sentinel, head)That is O(1) time.
The loop advances curr at most once per real node. Therefore, it runs at most n iterations.
In each iteration, the algorithm performs:
If a match is found, it performs one bypass update and returns.
The total time is O(n) in the worst case. For the worked example, the target is at the head, so the loop performs one iteration. If the target is absent, the loop examines all n nodes.
The algorithm stores a fixed number of references:
1dummy, prev, currTherefore, auxiliary space is O(1). The list nodes themselves are input storage and are not counted as auxiliary space.
prev at headIncorrect assumption:
1prev = headSmallest exposing input:
1[4] -> [7] -> null
2target = 4The first node is the target, but there is no real predecessor before it. The implementation needs a separate head-deletion branch or fails to identify a node that can bypass [4].
Correction:
1dummy = new Node(sentinel, head)
2prev = dummy
3curr = dummy.nextNow dummy is the predecessor of the first real node.
dummyIncorrect return:
1return dummyExposing input:
1[4] -> [7] -> null
2target = 4After deletion, the links are:
1[sentinel] -> [7] -> nullReturning dummy exposes helper data as if it were a logical list value:
1[sentinel] -> [7] -> nullCorrection:
1return dummy.nextThe correct returned list is:
1[7] -> nullprev before bypassing currIncorrect order when curr matches:
1prev = curr
2prev.next = curr.nextExposing input:
1[4] -> [7] -> null
2target = 4Initially:
1prev = dummy
2curr = [4]After prev = curr, prev points to [4], not to the node before [4]. Then:
1prev.next = curr.nextonly changes [4].next to [7], which was already its next reference. The dummy still points to [4], so the target remains reachable.
Correction: bypass first while prev is still the predecessor.
1prev.next = curr.next| Input and target | Required result |
|---|---|
head = null, target 4 | null |
[4] -> null, target 4 | null |
[7] -> [4] -> null, target 4 | [7] -> null |
[4] -> [4] -> null, target 4 | [4] -> null |
[7] -> null, target 4 | [7] -> null |
Implement:
1removeFirst(head, target)Use a temporary dummy node. Return dummy.next.
Executable tests verify this contract:
1class Node:
2 def __init__(self, value, nxt=None):
3 self.value = value
4 self.next = nxt
5
6def remove_first(head, target):
7 dummy = Node(-1, head) # sentinel value is never compared
8 prev = dummy
9 curr = dummy.next
10 while curr is not None:
11 if curr.value == target:
12 prev.next = curr.next # bypass while prev is still the predecessor
13 return dummy.next
14 prev = curr
15 curr = curr.next
16 return dummy.next # return the real head, not dummy
17
18def to_text(head):
19 parts = []
20 while head is not None:
21 parts.append(str(head.value))
22 head = head.next
23 return " -> ".join(parts + ["null"])
24
25head = Node(4, Node(7, Node(4)))
26print(to_text(remove_first(head, 4)))
27print(to_text(remove_first(None, 4)))
28print(to_text(remove_first(Node(7), 4)))1public class Main {
2 static class Node {
3 int value;
4 Node next;
5
6 Node(int value, Node next) {
7 this.value = value;
8 this.next = next;
9 }
10 }
11
12 static Node removeFirst(Node head, int target) {
13 Node dummy = new Node(-1, head); // sentinel value is never compared
14 Node prev = dummy;
15 Node curr = dummy.next;
16 while (curr != null) {
17 if (curr.value == target) {
18 prev.next = curr.next; // bypass while prev is still the predecessor
19 return dummy.next;
20 }
21 prev = curr;
22 curr = curr.next;
23 }
24 return dummy.next; // return the real head, not dummy
25 }
26
27 static String toText(Node head) {
28 StringBuilder sb = new StringBuilder();
29 for (Node curr = head; curr != null; curr = curr.next) {
30 sb.append(curr.value).append(" -> ");
31 }
32 return sb.append("null").toString();
33 }
34
35 public static void main(String[] args) {
36 Node head = new Node(4, new Node(7, new Node(4, null)));
37 System.out.println(toText(removeFirst(head, 4)));
38 System.out.println(toText(removeFirst(null, 4)));
39 System.out.println(toText(removeFirst(new Node(7, null), 4)));
40 }
41}1#include <iostream>
2#include <string>
3using namespace std;
4
5struct Node {
6 int value;
7 Node* next;
8 Node(int v, Node* n = nullptr) : value(v), next(n) {}
9};
10
11Node* removeFirst(Node* head, int target) {
12 Node dummy(-1, head); // sentinel value is never compared
13 Node* prev = &dummy;
14 Node* curr = dummy.next;
15 while (curr != nullptr) {
16 if (curr->value == target) {
17 prev->next = curr->next; // bypass while prev is still the predecessor
18 return dummy.next;
19 }
20 prev = curr;
21 curr = curr->next;
22 }
23 return dummy.next; // return the real head, not dummy
24}
25
26string toText(Node* head) {
27 string s;
28 for (Node* curr = head; curr != nullptr; curr = curr->next) s += to_string(curr->value) + " -> ";
29 return s + "null";
30}
31
32int main() {
33 Node* head = new Node(4, new Node(7, new Node(4)));
34 cout << toText(removeFirst(head, 4)) << endl;
35 cout << toText(removeFirst(nullptr, 4)) << endl;
36 cout << toText(removeFirst(new Node(7), 4)) << endl;
37}1class Node {
2 constructor(value, next = null) {
3 this.value = value;
4 this.next = next;
5 }
6}
7
8function removeFirst(head, target) {
9 const dummy = new Node(-1, head); // sentinel value is never compared
10 let prev = dummy;
11 let curr = dummy.next;
12 while (curr !== null) {
13 if (curr.value === target) {
14 prev.next = curr.next; // bypass while prev is still the predecessor
15 return dummy.next;
16 }
17 prev = curr;
18 curr = curr.next;
19 }
20 return dummy.next; // return the real head, not dummy
21}
22
23function toText(head) {
24 const parts = [];
25 for (let curr = head; curr !== null; curr = curr.next) parts.push(String(curr.value));
26 return [...parts, 'null'].join(' -> ');
27}
28
29console.log(toText(removeFirst(new Node(4, new Node(7, new Node(4))), 4)));
30console.log(toText(removeFirst(null, 4)));
31console.log(toText(removeFirst(new Node(7), 4)));Both are helper nodes. A dummy node is temporary: it exists while one operation runs, and you return dummy.next afterward. A sentinel node is a boundary node that stays in the list representation after operations finish.
The first real node has no predecessor, so deleting it needs its own branch that moves head. With a dummy, prev starts at the dummy and one bypass update works for the head, the middle and the last node.
Return dummy.next. If the head was deleted, dummy.next is already the new head. Returning dummy exposes the helper value as if it were list data.
It costs one node, so O(1) auxiliary space regardless of list length. The dummy, prev and curr references are a fixed number of variables.
No. A middle node already has a predecessor, so prev.next = target.next works without help. The dummy only matters when the target can be the first real node.