Time complexity of deletion in a linked list

Question

I'm having a bit of trouble understanding why time complexity of link lists are O(1) according to this website. From what I understand if you want to delete an element surely you must traverse the list to find out where the element is located (if it even exists at all)? From what I understand shouldn't it be O(n) or am I missing something completely?

Answer 1

No, you are not missing something.

If you want to delete a specific element, the time complexity is O(n) (where n is the number of elements) because you have to find the element first.

If you want to delete an element at a specific index i, the time complexity is O(i) because you have to follow the links from the beginning.

The time complexity of insertion is only O(1) if you already have a reference to the node you want to insert after. The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before. All this is in contrast to an array-based list where insertions and removal are O(n) because you have to shift elements along.

The advantage of using a linked list rather than a list based on an array is that you can efficiently insert or remove elements while iterating over it. This means for example that filtering a linked list is more efficient than filtering a list based on an array.

Answer 2

Your are correct.

Deletion:

1.If pointer is given in this case Time Complexity is O(1).

2.You DON'T have pointer to the node to be deleted(Search and Delete). In this case Time Complexity is O(n).