CODEWITHSUNDEEP
data-structureslinked-list
Lordoftherings
Lordoftherings

Reputation: 87

Why use linked lists, if at the end time complexity from arrays for deletion/insertion is equal?

I have following question. Why use Linked List, if time complexity for deletion of element for arrays is O(n) and for Linked List(with index given) is also O(n) since I also need to search through whole list?

Upvotes: 0

Views: 364

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126278

While the asymptotic complexity may be the same, the constant factor may be very different. In particular, you might have a collection of "large" things that are expensive to move or copy, but cheap to match. So with the linked list, you do a (fast) O(n) seach to find an element, then a O(1) to insert/remove there. With the array you need the same O(n) search and then a slow O(n) move of all the other elements in the array to make/remove space.

It is also possible you may have another connected data structure (such as a hash table) with fast lookup ability giving references into your collection. In such a case, you can find an element in the list in O(1) time, then remove it in O(1) time.

Another advantage is that lists are more amenable to atomic update -- a single-link list can be updated (insert or remove) with a single (atomic) pointer write.

Upvotes: 2

Related Questions