15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Insertion in linked list nodes means rewiring at most two links. Find the predecessor, then set newNode.next = prev.next and prev.next = newNode, in that order. For the front, set newNode.next = head, then head = newNode. Insertion is O(1) given the predecessor and O(n) by position.
| Valid positions | 0 through n for a list of length n (n appends) |
|---|---|
| Insert at front | O(1): newNode.next = head, then head = newNode |
| Insert after a known node | O(1): two link assignments |
| Insert by position | O(n) worst case, to walk to the predecessor |
| Auxiliary space | O(1) beyond the one new node |
A singly linked list has nodes connected by next references.
1head -> [4] -> [7] -> [9] -> nullEach node stores:
null at the endAssume you can traverse from head by following next.
Insert one new node without losing any existing nodes.
Connect the new node to the old successor before redirecting the earlier node to the new node.
For a list of length n, valid zero-based insertion positions are:
10 through n inclusivePosition 0 means insert at the front. Position n means append.
References:
Insert value 6 at position 1:
1head -> [4] -> [7] -> [9] -> nullPositions are zero-based:
1position: 0 1 2
2node: [4] -> [7] -> [9] -> nullTo insert at position 1, find the node just before that position.
1prev = [4]The intended result is:
1head -> [4] -> [6] -> [7] -> [9] -> nullNode [4] is the predecessor. Node [7] is its old successor. The new node goes between them.
Position 1 is not front insertion. Its predecessor is at position 0.
Insert 6 at position 1: find prev = [4], create newNode = [6 | null], set newNode.next = prev.next, then prev.next = newNode. Order matters. The list ends as head -> [4] -> [6] -> [7] -> [9] -> null.
At this moment:
1prev.next -> [7]Create the node for value 6.
The existing list has not changed.
Make the new node point to the node that currently follows prev.
1newNode.next = prev.nextNow the references are:
1head -> [4] -> [7] -> [9] -> null
2 ^
3 prev
4
5newNode -> [6] -> [7] -> [9] -> nullThe original suffix beginning at [7] is still reachable through newNode.
Change prev.next.
1prev.next = newNodeThe list becomes:
1head -> [4] -> [6] -> [7] -> [9] -> nullThe links are now:
1[4].next -> [6]
2[6].next -> [7]
3[7].next -> [9]
4[9].next -> nullTraversing from head gives:
1[4, 6, 7, 9]The old suffix is still present:
1[7] -> [9] -> nullIt was not copied or rebuilt. It stayed connected because [6].next was set before [4].next changed.
The insertion protects these conditions.
prev still point where they pointed before.prev is not discarded.newNode.next receives the old successor, the entire old suffix can be reached through newNode.The invariant for insertion after prev is:
During a valid insertion after
prev, all nodes beforeprevremain linked as before, and after settingnewNode.nextto the old successor, the original suffix remains reachable throughnewNode.
For our example:
1Before redirection:
2[4] -> [7] -> [9]
3[6] -> [7] -> [9]Both [4] and [6] can reach [7] temporarily. Only after this connection exists do we redirect [4].next to [6].
The update order preserves the suffix.
There are two structural cases.
The new node becomes the head.
newNode.next.head with newNode.Insert at the front in two statements. First newNode.next = head links the new node 6 to the old first node 4. Then head = newNode moves head. Reverse the order and you lose [4] and [7].
To insert at position i, find the predecessor at position i - 1.
For position 1:
1predecessor position = 1 - 1 = 0Once prev is available:
newNode.newNode.next = prev.next.prev.next = newNode.A list with length n accepts insertion positions from 0 through n.
For example, a length-2 list is:
1[4] -> [7] -> nullValid insertion positions are:
10, 1, 2Position 2 appends:
1[4] -> [7] -> [6] -> nullPosition 3 is invalid because it is larger than the length.
For an empty list:
1head -> nullOnly position 0 is valid.
The procedure changes links in the existing list. It allocates exactly one node for a valid insertion.
Input
head: the first node of a singly linked list, or nullposition: requested zero-based insertion positionvalue: value for the new nodeReturn
head after a valid insertionINVALID_POSITION if position is below 0 or greater than the current list lengthMutation behavior
next reference for a non-front insertion, or replaces the external head reference for front insertion.Helper contract
Node(value) returns a newly allocated node with node.value = value and node.next = null.11 procedure insertAt(head, position, value):
22 if position < 0:
33 return INVALID_POSITION
44
55 if position = 0:
66 newNode = Node(value)
77 newNode.next = head
88 return newNode
99
1010 prev = head
1111 steps = 0
1212
1313 while prev is not null and steps < position - 1:
1414 prev = prev.next
1515 steps = steps + 1
1616
1717 if prev is null:
1818 return INVALID_POSITION
1919
2020 newNode = Node(value)
2121 newNode.next = prev.next
2222 prev.next = newNode
2323 return headFor a nonzero position, line 13 moves prev until it is at position position - 1.
If that predecessor does not exist, line 17 rejects the request before line 21 attempts to read prev.next.
Use the original input:
1head -> [4] -> [7] -> [9] -> null
2position = 1
3value = 6| Pseudocode line | State |
|---|---|
| 2 | position < 0 is false because 1 < 0 is false. |
| 5 | position = 0 is false because 1 ≠ 0. The insertion is not at the front. |
| 10 | Set prev = head. Now prev refers to [4]. |
| 11 | Set steps = 0. |
| 13 | Check prev is not null and steps < position - 1. prev is [4], but 0 < 1 - 1 becomes 0 < 0, which is false. The loop does not run. |
| 17 | prev is null is false. A predecessor exists: [4]. |
| 20 | Allocate `newNode = [6 |
| 21 | Set newNode.next = prev.next. Since prev is [4], prev.next is [7]. Now: newNode -> [6] -> [7] -> [9] -> null. |
| 22 | Set prev.next = newNode. Now [4].next refers to [6]. |
| 23 | Return head. |
Final structure:
1head -> [4] -> [6] -> [7] -> [9] -> nullA traversal reads:
1[4, 6, 7, 9]The old nodes remain in their original relative order:
1[4], [7], [9]Only [6] was inserted between [4] and [7].
We show that insertAt returns the correct new head for every valid position and rejects invalid positions.
If position < 0, line 2 detects it and line 3 returns INVALID_POSITION. No links have changed.
For a positive position that is too large, the traversal reaches null before locating the needed predecessor. Line 17 returns INVALID_POSITION before dereferencing prev.next. No links have changed.
Positions below 0 or above the current length are rejected.
Suppose position = 0.
newNode.next to the old head. Every old node remains reachable from newNode.newNode as the new head.The returned list has the new value first, followed by every old node in the same order.
Suppose position > 0 is valid.
prev at position 0, and steps = 0.prev forward by one link and increases steps by one. After steps iterations, prev refers to the node at position steps.steps = position - 1. Since the position is valid, that predecessor exists. So prev refers to the node immediately before the requested insertion position.Now consider the two pointer updates.
newNode.next to the old prev.next. The old suffix remains reachable through newNode.prev.next with newNode. Nodes before prev are unchanged, and the old suffix follows newNode.The returned list contains exactly one new node at the requested position. Every old node remains present and keeps its relative order.
If a direct reference to prev is already available, insertion uses these link assignments:
1newNode.next = prev.next
2prev.next = newNodeThat is a constant number of operations.
1Time: O(1)Front insertion performs:
1newNode.next = head
2head = newNodeThis is a constant number of operations.
1Time: O(1)For a nonzero position i, the procedure may follow i - 1 links to find the predecessor.
In the worst case, insertion is near the end of a list of length n. The traversal visits O(n) nodes before the two constant-time link updates.
1Worst-case time: O(n)Appending to a nonempty ordinary singly linked list also requires finding the last node when there is no tail reference, so it has the same traversal cost.
The procedure allocates one required new node. Apart from that node, it uses a fixed number of references and counters:
1prev
2steps
3newNodeThe auxiliary space beyond the required new node is:
1O(1)prev.next too earlyIncorrect order:
1prev.next = newNode
2newNode.next = prev.nextSmallest exposing input:
1[4] -> [7] -> [9] -> null
2insert 6 after [4]After the first incorrect line:
1[4] -> [6] -> nullThe original reference from [4] to [7] has been overwritten. The next incorrect line makes [6].next point to itself or otherwise fails to recover the old successor. Nodes [7] and [9] can become unreachable from head.
Correction:
1newNode.next = prev.next
2prev.next = newNodeSave the old successor through newNode before replacing the predecessor link.
head before connecting the new nodeIncorrect front insertion:
1head = newNodeSmallest exposing input:
1head -> [4] -> [7] -> null
2insert 2 at position 0Wrong result:
1head -> [2] -> nullThe old list beginning at [4] is no longer reachable from head.
Correction:
1newNode.next = head
2head = newNodeThe new node must retain the old head first.
Incorrect assumption:
1An empty list allows insertion at position 1.Exposing input:
1head -> null
2insert 6 at position 1There is no node at position 0, so there is no predecessor for position 1. Accessing prev.next fails, or an implementation inserts in the wrong place.
Correction:
1For an empty list, only position 0 is valid.| Input | Position | Correct result |
|---|---|---|
null | 0 | head -> [6] -> null |
[4] -> null | 0 | [6] -> [4] -> null |
[4] -> [7] -> null | 2 | [4] -> [7] -> [6] -> null |
[4] -> [7] -> null | 3 | reject as out of range |
| any list | -1 | reject as out of range |
Implement:
1insertAt(head, position, value)Contract:
head after inserting value at a valid zero-based position.position < 0 or position is greater than the current list length.Executable tests will verify:
1class Node:
2 def __init__(self, value, nxt=None):
3 self.value = value
4 self.next = nxt
5
6def insert_at(head, position, value):
7 """Return the new head, or None for an invalid position."""
8 if position < 0:
9 return None
10 if position == 0:
11 return Node(value, head) # new node keeps the old head first
12 prev = head
13 steps = 0
14 while prev is not None and steps < position - 1:
15 prev = prev.next
16 steps += 1
17 if prev is None:
18 return None # no predecessor, so reject
19 new_node = Node(value)
20 new_node.next = prev.next # 1. keep the old successor
21 prev.next = new_node # 2. then redirect the predecessor
22 return head
23
24def to_text(head):
25 parts = []
26 while head is not None:
27 parts.append(str(head.value))
28 head = head.next
29 return " -> ".join(parts + ["null"])
30
31head = Node(4, Node(7, Node(9)))
32head = insert_at(head, 1, 6)
33print(to_text(head))
34head = insert_at(head, 0, 2)
35print(to_text(head))
36head = insert_at(head, 5, 1) # position == length appends
37print(to_text(head))
38print("invalid position" if insert_at(head, 7, 3) is None else "inserted")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 // Returns the new head, or null for an invalid position.
13 static Node insertAt(Node head, int position, int value) {
14 if (position < 0) return null;
15 if (position == 0) return new Node(value, head); // new node keeps the old head first
16 Node prev = head;
17 int steps = 0;
18 while (prev != null && steps < position - 1) {
19 prev = prev.next;
20 steps++;
21 }
22 if (prev == null) return null; // no predecessor, so reject
23 Node newNode = new Node(value, null);
24 newNode.next = prev.next; // 1. keep the old successor
25 prev.next = newNode; // 2. then redirect the predecessor
26 return head;
27 }
28
29 static String toText(Node head) {
30 StringBuilder sb = new StringBuilder();
31 for (Node curr = head; curr != null; curr = curr.next) {
32 sb.append(curr.value).append(" -> ");
33 }
34 return sb.append("null").toString();
35 }
36
37 public static void main(String[] args) {
38 Node head = new Node(4, new Node(7, new Node(9, null)));
39 head = insertAt(head, 1, 6);
40 System.out.println(toText(head));
41 head = insertAt(head, 0, 2);
42 System.out.println(toText(head));
43 head = insertAt(head, 5, 1); // position == length appends
44 System.out.println(toText(head));
45 System.out.println(insertAt(head, 7, 3) == null ? "invalid position" : "inserted");
46 }
47}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
11// Returns the new head, or nullptr for an invalid position.
12Node* insertAt(Node* head, int position, int value) {
13 if (position < 0) return nullptr;
14 if (position == 0) return new Node(value, head); // new node keeps the old head first
15 Node* prev = head;
16 int steps = 0;
17 while (prev != nullptr && steps < position - 1) {
18 prev = prev->next;
19 steps++;
20 }
21 if (prev == nullptr) return nullptr; // no predecessor, so reject
22 Node* newNode = new Node(value);
23 newNode->next = prev->next; // 1. keep the old successor
24 prev->next = newNode; // 2. then redirect the predecessor
25 return head;
26}
27
28string toText(Node* head) {
29 string s;
30 for (Node* curr = head; curr != nullptr; curr = curr->next) s += to_string(curr->value) + " -> ";
31 return s + "null";
32}
33
34int main() {
35 Node* head = new Node(4, new Node(7, new Node(9)));
36 head = insertAt(head, 1, 6);
37 cout << toText(head) << endl;
38 head = insertAt(head, 0, 2);
39 cout << toText(head) << endl;
40 head = insertAt(head, 5, 1); // position == length appends
41 cout << toText(head) << endl;
42 cout << (insertAt(head, 7, 3) == nullptr ? "invalid position" : "inserted") << endl;
43}1class Node {
2 constructor(value, next = null) {
3 this.value = value;
4 this.next = next;
5 }
6}
7
8// Returns the new head, or null for an invalid position.
9function insertAt(head, position, value) {
10 if (position < 0) return null;
11 if (position === 0) return new Node(value, head); // new node keeps the old head first
12 let prev = head;
13 let steps = 0;
14 while (prev !== null && steps < position - 1) {
15 prev = prev.next;
16 steps++;
17 }
18 if (prev === null) return null; // no predecessor, so reject
19 const newNode = new Node(value);
20 newNode.next = prev.next; // 1. keep the old successor
21 prev.next = newNode; // 2. then redirect the predecessor
22 return head;
23}
24
25function toText(head) {
26 const parts = [];
27 for (let curr = head; curr !== null; curr = curr.next) parts.push(String(curr.value));
28 return [...parts, 'null'].join(' -> ');
29}
30
31let head = new Node(4, new Node(7, new Node(9)));
32head = insertAt(head, 1, 6);
33console.log(toText(head));
34head = insertAt(head, 0, 2);
35console.log(toText(head));
36head = insertAt(head, 5, 1); // position == length appends
37console.log(toText(head));
38console.log(insertAt(head, 7, 3) === null ? 'invalid position' : 'inserted');Walk prev to the node immediately before the target position. Then set newNode.next = prev.next and prev.next = newNode, in that order. To insert 6 at position 1 of 4 -> 7 -> 9, prev is node 4 and the result is 4 -> 6 -> 7 -> 9.
Only when you already hold the predecessor, or you insert at the front. Inserting by position first walks up to position - 1 links, so the worst case is O(n). Appending without a tail reference also needs that walk.
Set newNode.next = head, then head = newNode. Reversing the two lines makes head point at the new node first and loses the old list. Front insertion is O(1) and the caller must receive the new head.
You overwrite the only link to the old successor. On 4 -> 7 -> 9, redirecting [4].next to the new node first leaves nothing that points at 7, so 7 and 9 become unreachable from head.
For a list of length n, positions 0 through n. Position 0 is the front and position n appends. An empty list accepts only position 0, and a negative position or one above n is rejected without changing the list.