In the ppt presentations on unordered linked lists when regarding complexity of insertion and deletion it is said:
• Insertion after a given item requires O(1) time, in contrast to O(n) for python lists.
• Deletion of a given item requires O(1) time, (assuming we have access to the previous item) in contrast to O(n) for
Python lists.
It is also said for both insertion and deletion:
• Time complexity: O(loc). In the worst case loc = n.
I thought the O(1) insertion to an unordered linked list was only because we would insert to the start of the list every time.
As for deletion of a given item would we not have to pass through the list until we get to the given item, worst case O(n)?
Have I misunderstood?
Thanks!