Why does adding to a singly linked list require O(1) constant time?
While doing leetcode, it says adding to a specific node in a singly linked list requires O(1) time complexity:
Unlike an array, we don’t need to move all elements past the inserted element. Therefore, you can insert a new node into a linked list in O(1) time complexity, which is very efficient.
When deleting it's O(n) time which makes sense because you need to traverse to the node-1 and change the pointers. Isn't it the same when adding, which means it should also be O(n) time complexity?
Specifically, when adding, you still need to traverse to the index-1 you want to add at and change that node's .next to the new node.
Leetcode reference - adding: here
Leetcode reference - conclusion: chart
It is important to know what the given input is. For instance, for the insert operation on a singly linked list you have highlighted the case where the node is given after which a new node should be inserted. This is indeed a O(1) operation. This is so because all the nodes that precede the given node are not affected by this operation.
This is different in this case: if for the delete operation the node is given that must be deleted, it cannot be done in O(1) in a singly linked list, because the node that precedes it must be updated. So now that preceding node must be retrieved by iterating from the start of the list.
We can "turn the tables":
What would be the time complexity if we were given a node and need to insert a new node before it? Then it will not be O(1), but O(n), for the simple reason that a change must be made to the node that precedes the given node.
What would be the time complexity if for a delete action we were given the node that precedes it? Then it can be done in O(1).
Still, if the input for either an insert or delete action is not a node reference, but an index, or a node's value, then both have a time complexity of O(n): the list must be traversed to find the given index or the given value.
So the time complexity for an action on a singly linked list depends very much on what the input is.