CODEWITHSUNDEEP
arraysalgorithmdata-structureslinked-listbig-o
Krishna Sai
Krishna Sai

Reputation: 115

How is a linked list faster than an array for insert and delete operations although it takes O(n) for both data structures?

The worst case running time of Insert and delete operations in an array is O(n), because we might need to make n shifts.

Same is the case for linked list too, if we want to insert or delete ith element we might need to traverse the whole list to reach the position where insert/delete is expected to be done. So Linked list also takes O(n) time.

So why is linked list preferred where insert/delete intensive operations are done.

Upvotes: 8

Views: 4004

Answers (3)

Rafał Dowgird
Rafał Dowgird

Reputation: 45121

The benefit of the O(1) removal/insert from the linked list is realized when there's an additional data structure that points directly to the nodes. This lets avoid the O(n) cost of the list traversal.

A good example is a bounded size LRU cache where the key-value pairs are represented in a map which also keeps pointers to the linked list. The list represents the access order and here's where the LRU takes advantage of the fast linked list access. Taking an element from the middle and putting it in front is O(1).

Every key access (O(1)) unlinks the associated node from the middle of the list and moves it to the head of the list (in O(1) time). When the cache gets full, the tail node of the list gets removed (it represents the least recently used key/value), together with the key-value pair represented by it.

Upvotes: 2

OmG
OmG

Reputation: 18838

Searching an element in both cases is the same (O(n)). The difference is in inserting and deleting when you are at the specified position. In this case, inserting and deleting is O(1) in a linked list (as you should reset two pointers), but need O(n) in an array (as you need O(n) shifts).

Another difference is in traversing from a position to another position. In a list this traversing take O(n), but in an array it is O(1).

Upvotes: 5

Chris Gong
Chris Gong

Reputation: 8229

If you want to insert/delete the ith element in an array, searching only takes O(1) because of indexing. For example u can access the ith element of an array through array[i]. However, inserting/deleting that element, in the worst case, will take O(n) time. For example, if you inserted an element at position 0, you have to shift all the elements one spot to the right, which requires a traversal of the whole array.

If you want to insert/delete the ith element in an linked list, searching will take O(n) in the worst case because you have to keep a count and a pointer while traversing the list one element at a time. Once you arrive at the ith node, inserting/deleting only takes O(1) time since it's just a rearrangement of pointers, no shifting.

As to why linked lists are preferred when there are many inserts/deletions, I would say that one reason is that with linked lists you don't need to know how big it has to be ahead of time. Whereas with arrays, it may have to be resized often in anticipation of more/less elements.

Upvotes: 5

Related Questions