Array & Data-Structure Operations
Singly Linked List Insertion
Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.
1Detailed explanation
A singly linked list stores values in nodes; each node points to the next one. Inserting does not move any existing data — it only changes pointers.
To insert at position p, walk p − 1 steps from the head to reach the node just before the insertion point. First point the new node at that node's successor, then point the predecessor at the new node. Doing it in the opposite order would lose the rest of the list.
Inserting at the head is O(1). Inserting at an arbitrary position is O(p) because of the walk.
2Pseudocode
procedure insertAt(head, value, position)
newNode ← Node(value)
if position = 0
newNode.next ← head
return newNode
current ← head
repeat position − 1 times while current ≠ null
current ← current.next
if current = null
return head // out of range
newNode.next ← current.next
current.next ← newNode
return head3Interactive visualization
Inserts a new node at a given position: walk to the node just before the position, point the new node at its successor, then re-link the predecessor to the new node.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
function insertAt(head, value, position) {
const newNode = new Node(value);
if (position === 0) {
newNode.next = head;
return newNode;
}
let current = head;
for (let i = 0; i < position - 1 && current !== null; i++) {
current = current.next;
}
if (current === null) {
return head;
}
newNode.next = current.next;
current.next = newNode;
return head;
}
function buildList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function printList(head) {
const parts = [];
for (let node = head; node !== null; node = node.next) parts.push(node.value);
parts.push("null");
console.log(parts.join(" -> "));
}
let head = buildList([10, 20, 30, 40]);
head = insertAt(head, 25, 2);
printList(head);
5Time and space complexity
Time: Inserting at the head needs no traversal → O(1). Inserting at position p walks p−1 links first, so the worst case (insert at the end without a tail pointer) is O(n). The re-linking itself is always O(1) — unlike arrays, no elements are shifted.
Space: Only the new node and the current pointer are created → O(1) auxiliary space.
6Common interview variations
- Insert into a sorted linked list.
- Delete the node at a position / with a value.
- Insert using a dummy (sentinel) head to remove the special case.
- Insert at the tail in O(1) by maintaining a tail pointer.
- Doubly linked list insertion (update prev pointers too).