CODEWITHSUNDEEP
linked-listsingly-linked-list
wongx
wongx

Reputation: 11869

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.

enter image description here

Leetcode reference - adding: here
Leetcode reference - conclusion: chart

Upvotes: 1

Views: 2162

Answers (2)

trincot
trincot

Reputation: 350147

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.

Upvotes: 2

PMF
PMF

Reputation: 17185

No, you do not need to traverse the list to insert an element past an existing, given element. For this, you only need to update the next pointers of the element you already have and of the element you are inserting. It's not necessary to know the previous element.

Note that even insertion past the last element can be implemented in O(1) on a singly-linked list, if you keep a reference to the last element of the list.

Upvotes: 1

Related Questions