Insertion

Insertion in Linked List

Linked list insertion can happen at three positions, each with different pointer logic:

1. Insert at Head — O(1)

The fastest case. No traversal needed. We simply point the new node's next to the current head, then update head to the new node.

Before: HEAD -> [10] -> [30] -> NULL
Insert 5 at head
After:  HEAD -> [5] -> [10] -> [30] -> NULL

2. Insert at Tail — O(N)

We must traverse the entire list to find the last node (where next == NULL), then attach the new node there.

Before: HEAD -> [10] -> [30] -> NULL
Insert 50 at tail
After:  HEAD -> [10] -> [30] -> [50] -> NULL

3. Insert at Position — O(N)

We traverse to the node just before the target position using a temp pointer, then splice in the new node by relinking the next pointers.

Before: HEAD -> [10] -> [30] -> NULL
Insert 20 at index 1
After:  HEAD -> [10] -> [20] -> [30] -> NULL

Key Insight: Always update newNode->next BEFORE updating temp->next. Reversing the order would lose the reference to the rest of the list.