0

I was going through the differences between Array List and Linked List implementations of the List interface in Java. Almost all resources, I went through told that Array Lists provide better performanceO(1)for Index Based Operations(Searching etc.) and require shifting of elements (or copying in this case) for insertions and deletions.On the other hand, Linked lists are better for Insertions and deletions as it requires just the change of the references and instantiation of the Node object. Then I came across this one article which stated

In most cases, however, ArrayList outperforms LinkedList. Even elements shifting in ArrayList, while being an O(n) operation, is implemented as a very fast System.arraycopy() call. It can even appear faster than the LinkedList‘s O(1) insertion which requires instantiating a Node object and updating multiple references under the hood. LinkedList also can have a large memory overhead due to a creation of multiple small Node objects.

This made me think that if the copying of the elements for insertion/deletion(in ArrayList) can be faster than the instantiation of node and subsequent change of references(in LinkedList), then Array List should outperform Linked List for each use case. Now My question is that if this is true then what are the use cases for the Linked Lists? Please enlighten me if this premise is wrong

arjun gulyani
  • 669
  • 2
  • 8
  • 23
  • 1
    Consider a use case where you have a million values in the arraylist and you remove the first value. The entrire array list has to be reorganized while linkedlist will be just one swap away from perfection – utkarsh31 Nov 19 '17 at 08:15
  • @utkarsh31 so for smaller size arrays/linked lists, arrays will outperform the linked lists? and what could be the approximate size threshold when linked lists would be better? – arjun gulyani Nov 19 '17 at 08:17
  • with every new version of java there are new modifications and improvements happening within collections framework. I cannot be certain about a threshold when it will actually change because that would depend upon a lot of factors and some of them would be real time... – utkarsh31 Nov 19 '17 at 08:20
  • 1
    The proper way to make sure would be to write tests for your particular use-case and measure which one performs better. There is no "general rule" as many different factors can influence the actual results (and you should always make sure you can prove which one is better for your use-case) – UnholySheep Nov 19 '17 at 08:23
  • This link can probably help you. Please go through the link https://stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist – Ram Nov 19 '17 at 08:43
  • The link below would answer your question. >> [Refer this](https://docs.oracle.com/javase/tutorial/collections/implementations/list.html) – kemparaj565 Nov 19 '17 at 11:01

0 Answers0