7

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.

Krishna Sai
  • 105
  • 2
  • 10
  • O(1) insert operation for linked list assumes that we stay at needed node. – MBo Jul 17 '18 at 17:28
  • But that is never the case in practical sense. We always have to traverse to the element which is essentially making it O(n) again. – Krishna Sai Jul 17 '18 at 17:39
  • 1
    Searching of needed place and insertion/deletion are different operations. Yes, they are used together frequently but some algorithms exploit single list traversal with multiple insertions etc. Note that practical usage of LL is rather rare because of your reasons. – MBo Jul 17 '18 at 17:50
  • According to Stroustrup vectors are faster than linkedlists since the time is dominated by the search instead of the shift: https://isocpp.org/blog/2014/06/stroustrup-lists – Mauricio Cele Lopez Belon Jul 17 '18 at 22:22
  • What data do you have to back up the assertion that linked list is preferred where insert/delete intensive operations are done? – Jim Mischel Jul 17 '18 at 22:52

3 Answers3

5

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).

OmG
  • 18,337
  • 10
  • 57
  • 90
  • *Finding an element in both cases is the same (`O(n)`).* Not necessarily true. You can find the *i*th element in an array in O(1). – Jim Mischel Jul 17 '18 at 22:51
5

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.

Chris Gong
  • 8,031
  • 4
  • 30
  • 51
2

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.

Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90