When inserting a node at a specific index in a singly linked list, what is the typical approach and its time complexity?

• A. Append to tail and shift pointers; O(1)
• B. Traverse to node at index-1, insert by adjusting next pointers; O(n)
• C. Create new node and insert after head; O(1)
• D. Rebuild the entire list with the new node; O(n^2)

Answer: (B)

Inserting at a specific position in a singly linked list relies on traversing from the head to reach the node just before where you want to insert. Since there’s no direct index access, you walk through the list until you reach the position index minus one, then you adjust pointers to weave the new node in: make the new node’s next point to the current node’s next, and update the current node’s next to the new node. If you’re inserting at the head (index 0), you simply update the head to the new node and point the new node’s next to the old head.

This approach is the standard because it uses the only efficient operation available on a singly linked list: pointer manipulation after locating the insertion point. The time is linear in the number of nodes you traverse, so the worst-case time complexity is O(n), since you may need to walk through most of the list. It correctly captures that insertion at an arbitrary index requires scanning to the prior node, followed by constant-time pointer updates.

Other options either imply unnecessary or unrealistic steps (like rebuilding the list) or only work for special cases (inserting after the head or at the tail with extra pointers), and don’t describe the general, scalable method for arbitrary indices.