0

Considering that for both linked list and array, inserting/deleting data from middle has O(n) complexity, why is linked list being preferred? Is array's O(n) (performing the operation) more costly than linked list's (indexing)?

Frenk Frenk
  • 113
  • 7
  • What is your source for saying that "linked list being preferred" and "insertion and deletion faster in linked list"? This depends on the actual programming language you use. Also, what do you mean with "(indexing)" in the context of a linked list? – trincot Dec 13 '20 at 12:56

1 Answers1

1

For an Array of size "M" : if i want to remove the element at Nth position then i can directly go to the Nth position using index in one go (i don't have to traverse till Nth index) and then i can remove the element, till this point the complexity is O(1) then i will have to shift the rest of the elements(M-N shifts) so my complexity will be linear i.e. O(M-N+1). and hence deletion or insertion at the last will give me the best performence( as N ~ M) and deletion or insertion at the start will be worst (as N ~ 1).

Now the LinkedList of size "M" : if you already have a reference to the node you want to insert after or delete after the time complexity is O(1) . If it isn't provided we can not directly reach the Nth element in the LinkedList, to access the Nth element we have to traverse N elements, so the search in the LinkedList is costlier then the ArrayList.

Milinda Reddy
  • 11
  • 1