What is the worst-case time complexity of insertion in a singly linked list?

A singly linked list node stores only its data and a pointer to the next node — there is no random-access index and no pointer back to the previous node. To insert a new node at any target position, you must therefore walk the list one hop at a time from the head until you reach the node just before that position; only once you are there does the actual relinking (creating the new node and updating two pointers) happen in constant time.

1. Take a concrete singly linked list of n = 4 nodes: A (index 0) → B (index 1) → C (index 2) → D (index 3), where "→" denotes each node's next pointer.

2. To insert a new node at index k, you must first reach the node currently at index k−1 (the predecessor) — because updating a node's next pointer requires already holding a reference to that node. Example: inserting a new node X at index 2 (so it lands between B and C) needs the predecessor at index 1, i.e. B, reached from the head A in k−1 = 1 hop (A → B).

3. Once the predecessor is reached, the relink is O(1): set X's next pointer to the predecessor's current next node (X's next = C), then update the predecessor's next pointer to X (B's next = X). The list becomes A → B → X → C → D.

4. This (k−1)-hop traversal is smallest when k = 0 (inserting at the very head needs no predecessor at all — the head reference is simply reassigned directly, 0 hops) and largest when k = n, i.e. appending after the current last node: for this same 4-node list, that predecessor is D at index 3, reached in n−1 = 3 hops (A → B → C → D).

5. Since the question does not restrict where the insertion happens, the worst case is this k = n scenario: n−1 traversal hops before the O(1) relink. This scales linearly with n, giving O(n) overall.

Cross-check: this matches the general rule for singly linked lists — cost is governed by how far the target position is from the head, since there is no way to jump directly to an interior or trailing node the way an array’s index allows. Inserting exactly at the head (k = 0) is the one position that needs no traversal and runs in O(1); that is a special/best-case scenario for a specific position, not the answer to "what is the worst case across insertion in general". Considered over all valid insertion positions, the worst case is O(n).

So the worst-case time complexity of insertion in a singly linked list is O(n).