When you are inserting a node in the middle of a linked list, the assumption taken is that you are already at the address where you have to insert the node. Indexing is considered as a separate operation. So insertion is itself O(1)
, but getting to that middle node is O(n)
. Thus adding to a linked list does not require a traversal, as long as you know a reference.