Why does linked list delete and insert operation have complexity of O(1)?

Technology CommunityCategory: Linked ListsWhy does linked list delete and insert operation have complexity of O(1)?
VietMX Staff asked 3 years ago

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.