What is the time complexity of inserting a node at an arbitrary index in a singly linked list, and why?

• A. O(n) because you must traverse to the previous node before inserting
• B. O(1) because insertion is constant time
• C. O(n log n) due to pointer arithmetic
• D. O(1) expected due to tail pointer

Answer: (A)

Inserting at an arbitrary position in a singly linked list hinges on finding the node right before the insertion point. Since you can only move forward through next pointers, you must start at the head and walk along until you reach that predecessor. The number of steps you take scales with how far the insertion point is from the head, so in the worst case you traverse most or all of the list, giving linear time, O(n). Once the correct spot is found, the actual insertion is just a couple of constant-time pointer updates: the new node’s next points to the predecessor’s next, and the predecessor’s next points to the new node. So the overall operation is O(n) because the traversal dominates the cost, even though the insertion itself is O(1). If you’re inserting at the head, it can be done in O(1), and having a tail pointer helps only for end-insertion, not for arbitrary positions.