Linked List Insertion adds a new node at a desired position. Inserting at the head is O(1) — just update the head pointer. Inserting at the tail requires traversal to find the last node (O(n) without a tail pointer). Inserting at position k requires traversal to node k-1.
struct Node { int val; Node* next; Node(int v): val(v), next(nullptr){} };
Node* insertHead(Node* head, int val) {
Node* node = new Node(val);
node->next = head;
return node;
}
Node* insertAt(Node* head, int pos, int val) {
if (pos == 0) return insertHead(head, val);
Node* curr = head;
for (int i = 0; i < pos-1 && curr; i++) curr = curr->next;
if (!curr) return head;
Node* node = new Node(val);
node->next = curr->next;
curr->next = node;
return head;
}Create a new node, set its next to the current head, then update head to the new node. This is O(1) and the most common insertion for stack-like behavior.
Traverse to node at position k-1, then set new_node.next = curr.next and curr.next = new_node. The key is updating pointers in the right order to avoid losing the rest of the list.
Without a tail pointer, insertion at the end requires O(n) traversal. With a dedicated tail pointer, tail insertion is O(1) — a common optimization for queue implementations.
Quiz coming soon for this algorithm.