15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Deletion in linked list structures means making a node unreachable. Find the predecessor and set prev.next = target.next, which bypasses the target and keeps every later node. The head has no predecessor, so set head = head.next. Deletion is O(1) given the predecessor and O(n) by position.
| Delete a middle or last node | prev.next = target.next |
|---|---|
| Delete the head | head = head.next, O(1), no predecessor needed |
| Delete after a known predecessor | O(1): read, read, one write |
| Delete by position | O(n) worst case, to walk to the predecessor |
| Valid positions | 0 through n - 1 for a list of length n |
| Auxiliary space | O(1) |
A singly linked list node has:
valuenext, a reference to the next node or nullYou should already be able to:
next references from head,head is the only entry point to the list,Deletion changes reachability by changing references. A removed node's fields may still exist, but the node is no longer part of the reachable list.
If no node in the list points to a node, and head does not point to it, that node is no longer part of the reachable list.
A valid zero-based deletion position in a list of length n is from 0 through n - 1.
The operation in this lesson has this contract:
head, the first node or null; position, an integer.head, a removed value when deletion occurs, and a deletion status.next reference changes. On head deletion, the caller receives a new head. Invalid requests do not change the list.Reference scope:
Delete the node at position 1 from:
1head -> [4] -> [6] -> [7] -> [9] -> null
2 0 1 2 3Position 1 is not the head, so we need the node immediately before it.
1prev = [4]
2target = [6]Ask:
Which node currently points to
target, and where should that node point afterward?
Here, [4].next currently points to [6]. To remove [6] without losing [7], redirect [4].next to [7].
Keep the same list on the board:
1head -> [4] -> [6] -> [7] -> [9] -> nullDeleting position 1 from head, 4, 6, 7, 9: set prev.next = target.next so 4 points to 7, bypassing 6. 7 and 9 stay reachable. Return head 4 and removedValue 6.
Position 1 has:
1prev = [4]
2target = [6]The links are unchanged:
1[4].next = [6]
2[6].next = [7]If the operation must report what it removed, read the value before redirecting the link:
1removedValue = target.value = 6The list remains:
1head -> [4] -> [6] -> [7] -> [9] -> nullPerform one pointer update:
1prev.next = target.nextSubstitute the actual nodes:
1[4].next = [6].next
2[4].next = [7]The surviving links are now:
1[4].next = [7]
2[7].next = [9]headStart at head and follow next:
1head -> [4] -> [7] -> [9] -> nullThere is no longer a path from head to [6].
Node [6] was bypassed. Nodes [7] and [9] remain reachable because we used target.next, not null.
The operation returns:
1head = [4]
2removedValue = 6
3deleted = trueThe head reference did not change because position 1 was not the first position.
For position 0, there is no predecessor. Use a different update:
1head = head.nextBefore the bypass, prev must be immediately before target.
1prev -> target -> target.nextAfter this assignment:
1prev.next = target.nextevery node except target remains reachable in its original order.
For the board example:
1Before: [4] -> [6] -> [7] -> [9]
2After: [4] ------> [7] -> [9]The prefix before target stays in place. The suffix after target stays in place. Only the connection between them changes.
When deletion is by position, we must first find the predecessor. During that traversal, these conditions remain true:
prev is at position currentPosition - 1.prev is the predecessor needed if the requested position is currentPosition.For position 1, initialization places prev at position 0, immediately before the target.
There are three cases.
A negative position cannot name a node.
An empty list has no valid deletion position.
If traversal cannot establish both prev and prev.next, the requested non-head target does not exist. Return a no-deletion result and leave the list unchanged.
0The first node has no predecessor.
If head exists:
head.value.head.next.0We need the predecessor of the target.
prev = head, at position 0.currentPosition = 1.prev until it is immediately before the requested position.prev.next exists. That node is the target.target.value.prev.next = target.next.head and the saved value.The local deletion step needs no traversal once prev is known.
1DeletionResult:
2 head // resulting first node, or null
3 removedValue
4 deleted // true when exactly one node was removed1DELETE_AFTER(prev)
2Input:
3 prev, a non-null node whose prev.next is also non-null
4Returns:
5 the value stored in the removed node
6Mutates:
7 prev.next; no other reachable node link changes
8
91. target <- prev.next
102. removedValue <- target.value
113. prev.next <- target.next
124. return removedValueThe helper's caller must establish its preconditions: prev exists and prev.next exists.
1DELETE_AT(head, position)
2Input:
3 head, the first node of a singly linked list or null
4 position, an integer
5Returns:
6 DeletionResult containing the resulting head, a removed value when deleted,
7 and deleted = true or false
8Mutates:
9 On successful non-head deletion, changes one next reference.
10 On head deletion, does not change a node link; returns head.next as new head.
11 On invalid input or an invalid position, does not change the list.
12
131. if position < 0
142. return { head: head, removedValue: null, deleted: false }
15
163. if head = null
174. return { head: null, removedValue: null, deleted: false }
18
195. if position = 0
206. return { head: head.next, removedValue: head.value, deleted: true }
21
227. prev <- head
238. currentPosition <- 1
24
259. while currentPosition < position and prev.next != null
2610. prev <- prev.next
2711. currentPosition <- currentPosition + 1
28
2912. if currentPosition != position or prev.next = null
3013. return { head: head, removedValue: null, deleted: false }
31
3214. removedValue <- DELETE_AFTER(prev)
3315. return { head: head, removedValue: removedValue, deleted: true }Use the original input:
1head -> [4] -> [6] -> [7] -> [9] -> null
2position = 1| Pseudocode line | State |
|---|---|
| 1 | position < 0 is false because 1 < 0 is false. |
| 3 | head = null is false. head points to [4]. |
| 5 | position = 0 is false. This is not head deletion. |
| 7 | Set prev <- head. Now prev = [4]. |
| 8 | Set currentPosition <- 1. |
| 9 | Check currentPosition < position: 1 < 1 is false. Do not enter the loop. prev is already the predecessor of position 1. |
| 12 | currentPosition != position is false because both are 1. prev.next = null is false because [4].next is [6]. The target exists. |
| 14, helper line 1 | In DELETE_AFTER(prev), set target <- prev.next. So target = [6]. |
| 14, helper line 2 | Set removedValue <- target.value. So removedValue = 6. |
| 14, helper line 3 | Set prev.next <- target.next. This changes [4].next from [6] to [7]. |
| 14, helper line 4 | Return 6 from DELETE_AFTER. |
| 15 | Return { head: [4], removedValue: 6, deleted: true }. |
After line 14, follow links from head:
1head -> [4] -> [7] -> [9] -> nullNode [6] is no longer reachable from head.
We show that DELETE_AT returns the correct result for each possible input.
If position < 0, line 2 returns without changing a link. A negative position is invalid.
If head = null, line 4 returns without changing a link. An empty list has no node to remove.
For a nonzero position, the traversal stops either when it has reached the requested predecessor location or when no further next node exists. If line 12 finds that currentPosition is not the requested position, or that prev.next is null, the target does not exist. The algorithm returns no deletion and leaves the list unchanged.
When position = 0 and head is not null, line 6 returns head.next as the new head.
The old first node is no longer reachable from the returned head. Every former node after it remains connected in its original order. Exactly one node is removed.
Before the loop begins, prev = head, which is position 0, and currentPosition = 1. Therefore, prev is immediately before the node at currentPosition.
Each loop iteration advances both values once:
1prev <- prev.next
2currentPosition <- currentPosition + 1After the update, prev is again at position currentPosition - 1. No link changes during traversal, so the list remains unchanged while searching.
When the loop ends with a valid target, currentPosition = position and prev.next exists. Therefore, prev is immediately before the target node.
DELETE_AFTER(prev) sets:
1target <- prev.next
2prev.next <- target.nextBefore the assignment, prev points to target, and target points to its successor. After the assignment, prev points directly to that successor.
Thus:
target remain in their original order,target is no longer reachable from head,target remain reachable in their original order,The returned value is read from target before the bypass, so it is the value of the removed node.
For position 0, the algorithm:
head.next,head.value,The algorithm performs a constant number of operations.
1Time: O(1)DELETE_AFTER(prev):
prev.next,target.value,prev.next = target.next.The helper performs a constant number of operations.
1Time given prev: O(1)For a non-head position, the loop moves through nodes to locate the predecessor.
In the worst case, the requested valid position is near the end of a list of length n, or the request is beyond the end. The traversal visits O(n) nodes.
1Worst-case time: O(n)For the board example, position 1 requires no loop iterations because head is already its predecessor. That deletion performs constant work after the initial checks.
The algorithm stores:
prev,target inside the helper,currentPosition,removedValue.These are a constant number of references and scalar values, regardless of list length.
1Auxiliary space: O(1)target variableIncorrect idea:
1target <- target.nextExposing input:
1[4] -> [6] -> [7] -> null
2prev = [4]
3target = [6]Wrong state after the assignment:
1prev.next still points to [6]The local variable now refers to [7], but the list still contains [6]:
1head -> [4] -> [6] -> [7] -> nullCorrection:
1prev.next <- target.nextThe predecessor's link controls reachability from head.
prev.next for head deletionIncorrect assumption:
1prev.next <- target.nextfor every position, including position 0.
Exposing input:
1head -> [5] -> [7] -> null
2position = 0There is no predecessor of head. prev does not exist for this case.
Wrong outcome:
head.Correction:
1head <- head.nextHandle position 0 before trying to locate a predecessor.
Incorrect line:
1prev.next <- nullExposing input:
1head -> [4] -> [6] -> [7] -> [9] -> null
2delete [6], with prev = [4]Wrong resulting list:
1head -> [4] -> nullNodes [7] and [9] became unreachable too.
Correction:
1prev.next <- target.nextThe replacement link must point to the target's successor, not to null.
| Input | Position | Expected result |
|---|---|---|
null | 0 | No deletion; return null. |
[5] -> null | 0 | Return null; removed value is 5. |
[4] -> [7] -> null | 1 | Return [4] -> null; removed value is 7. |
[4] -> [7] -> null | 2 | Invalid position; list remains [4] -> [7] -> null. |
| Any list | -1 | Invalid position; list remains unchanged. |
Implement:
1deleteAt(head, position)It must return:
head,The executable tests verify:
1class Node:
2 def __init__(self, value, nxt=None):
3 self.value = value
4 self.next = nxt
5
6def delete_after(prev):
7 target = prev.next
8 removed = target.value # read the value before the bypass
9 prev.next = target.next # bypass target, keep the suffix
10 return removed
11
12def delete_at(head, position):
13 """Return (head, removed_value, deleted)."""
14 if position < 0 or head is None:
15 return head, None, False
16 if position == 0:
17 return head.next, head.value, True # no predecessor: move head
18 prev = head
19 current = 1
20 while current < position and prev.next is not None:
21 prev = prev.next
22 current += 1
23 if current != position or prev.next is None:
24 return head, None, False
25 return head, delete_after(prev), True
26
27def to_text(head):
28 parts = []
29 while head is not None:
30 parts.append(str(head.value))
31 head = head.next
32 return " -> ".join(parts + ["null"])
33
34head = Node(4, Node(6, Node(7, Node(9))))
35head, removed, ok = delete_at(head, 1)
36print(f"removed {removed}: {to_text(head)}")
37head, removed, ok = delete_at(head, 0)
38print(f"removed {removed}: {to_text(head)}")
39head, removed, ok = delete_at(head, 5)
40print(f"position 5: {'deleted' if ok else 'no deletion'}, {to_text(head)}")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 class Result {
13 Node head;
14 int removed;
15 boolean deleted;
16
17 Result(Node head, int removed, boolean deleted) {
18 this.head = head;
19 this.removed = removed;
20 this.deleted = deleted;
21 }
22 }
23
24 static int deleteAfter(Node prev) {
25 Node target = prev.next;
26 int removed = target.value; // read the value before the bypass
27 prev.next = target.next; // bypass target, keep the suffix
28 return removed;
29 }
30
31 static Result deleteAt(Node head, int position) {
32 if (position < 0 || head == null) return new Result(head, 0, false);
33 if (position == 0) return new Result(head.next, head.value, true); // no predecessor: move head
34 Node prev = head;
35 int current = 1;
36 while (current < position && prev.next != null) {
37 prev = prev.next;
38 current++;
39 }
40 if (current != position || prev.next == null) return new Result(head, 0, false);
41 return new Result(head, deleteAfter(prev), true);
42 }
43
44 static String toText(Node head) {
45 StringBuilder sb = new StringBuilder();
46 for (Node curr = head; curr != null; curr = curr.next) {
47 sb.append(curr.value).append(" -> ");
48 }
49 return sb.append("null").toString();
50 }
51
52 public static void main(String[] args) {
53 Node head = new Node(4, new Node(6, new Node(7, new Node(9, null))));
54 Result r = deleteAt(head, 1);
55 System.out.println("removed " + r.removed + ": " + toText(r.head));
56 r = deleteAt(r.head, 0);
57 System.out.println("removed " + r.removed + ": " + toText(r.head));
58 r = deleteAt(r.head, 5);
59 System.out.println("position 5: " + (r.deleted ? "deleted" : "no deletion") + ", " + toText(r.head));
60 }
61}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
11struct Result {
12 Node* head;
13 int removed;
14 bool deleted;
15};
16
17int deleteAfter(Node* prev) {
18 Node* target = prev->next;
19 int removed = target->value; // read the value before the bypass
20 prev->next = target->next; // bypass target, keep the suffix
21 return removed;
22}
23
24Result deleteAt(Node* head, int position) {
25 if (position < 0 || head == nullptr) return {head, 0, false};
26 if (position == 0) return {head->next, head->value, true}; // no predecessor: move head
27 Node* prev = head;
28 int current = 1;
29 while (current < position && prev->next != nullptr) {
30 prev = prev->next;
31 current++;
32 }
33 if (current != position || prev->next == nullptr) return {head, 0, false};
34 return {head, deleteAfter(prev), true};
35}
36
37string toText(Node* head) {
38 string s;
39 for (Node* curr = head; curr != nullptr; curr = curr->next) s += to_string(curr->value) + " -> ";
40 return s + "null";
41}
42
43int main() {
44 Node* head = new Node(4, new Node(6, new Node(7, new Node(9))));
45 Result r = deleteAt(head, 1);
46 cout << "removed " << r.removed << ": " << toText(r.head) << endl;
47 r = deleteAt(r.head, 0);
48 cout << "removed " << r.removed << ": " << toText(r.head) << endl;
49 r = deleteAt(r.head, 5);
50 cout << "position 5: " << (r.deleted ? "deleted" : "no deletion") << ", " << toText(r.head) << endl;
51}1class Node {
2 constructor(value, next = null) {
3 this.value = value;
4 this.next = next;
5 }
6}
7
8function deleteAfter(prev) {
9 const target = prev.next;
10 const removed = target.value; // read the value before the bypass
11 prev.next = target.next; // bypass target, keep the suffix
12 return removed;
13}
14
15function deleteAt(head, position) {
16 if (position < 0 || head === null) return { head, removed: null, deleted: false };
17 if (position === 0) return { head: head.next, removed: head.value, deleted: true }; // no predecessor: move head
18 let prev = head;
19 let current = 1;
20 while (current < position && prev.next !== null) {
21 prev = prev.next;
22 current++;
23 }
24 if (current !== position || prev.next === null) return { head, removed: null, deleted: false };
25 return { head, removed: deleteAfter(prev), deleted: true };
26}
27
28function toText(head) {
29 const parts = [];
30 for (let curr = head; curr !== null; curr = curr.next) parts.push(String(curr.value));
31 return [...parts, 'null'].join(' -> ');
32}
33
34let r = deleteAt(new Node(4, new Node(6, new Node(7, new Node(9)))), 1);
35console.log(`removed ${r.removed}: ${toText(r.head)}`);
36r = deleteAt(r.head, 0);
37console.log(`removed ${r.removed}: ${toText(r.head)}`);
38r = deleteAt(r.head, 5);
39console.log(`position 5: ${r.deleted ? 'deleted' : 'no deletion'}, ${toText(r.head)}`);Deletion removes an element so later operations no longer see it. In a linked list you do it by changing links: after prev.next = target.next, no path from head reaches the target, even though its fields still exist.
Return head.next as the new head. The first node has no predecessor, so there is no link to bypass. It takes O(1) time, and deleting the only node returns null, an empty list.
Find the node before it, call it prev, and set prev.next = prev.next.next. In 4 -> 6 -> 7 -> 9, deleting position 1 sets [4].next to [7], so the list becomes 4 -> 7 -> 9.
It is O(1) for the head and for any node whose predecessor you already hold. Deleting by position first walks to the predecessor, so the worst case is O(n).
You cut off the whole suffix, not one node. On 4 -> 6 -> 7 -> 9, setting [4].next to null leaves 4 -> null, and 7 and 9 become unreachable too.