Performance differences between ArrayList and LinkedList

Question

Yes  this is an old topic  but I still have some confusions   In Java  people say    ArrayList is faster than LinkedList if I randomly access its elements  I think random access means  give me the nth element   Why ArrayList is faster  LinkedList is faster than ArrayList for deletion  I understand this one  ArrayList s slower since the internal backing-up array needs to be reallocated  A code explanation   List lt String gt  list   new ArrayList lt String gt     list add  a    list add  b    list add  c    list remove  b    System out println list get 1      output  c   LinkedList is faster than ArrayList for insertion  What does insertion mean here  If it means to move some elements back and then put the element in the middle empty spot  ArrayList should be slower than LinkedList  If insertion only means an add Object  operation  how could this be slow

User · Answer

ArrayList   ArrayList is best choice if our frequent operation is retrieval operation  ArrayList is worst choice if our operation is insertion and deletion in the middle because internally several shift operations are performed  In ArrayList elements will be stored in consecutive memory locations hence retrieval operation will become easy    LinkedList -   LinkedList is best choice if our frequent operation is insertion and deletion in the middle  LinkedList is worst choice is our frequent operation is retrieval operation  In LinkedList the elements won t be stored in consecutive memory location and hence retrieval operation will be complex    Now coming to your questions -  1  ArrayList saves data according to indexes and it implements RandomAccess interface which is a marker interface that provides the capability of a Random retrieval to ArrayList but LinkedList doesn t implements RandomAccess Interface that s why ArrayList is faster than LinkedList   2  The underlying data structure for LinkedList is doubly linked list so insertion and deletion in the middle is very easy in LinkedList as it doesn t have to shift each and every element for each and every deletion and insertion operations just like ArrayList which is not recommended if our operation is insertion and deletion in the middle because internally several shift operations are performed   Source

User · Answer

Ignore this answer for now   The other answers  particularly that of aix  are mostly correct   Over the long term they re the way to bet   And if you have enough data  on one benchmark on one machine  it seemed to be about one million entries  ArrayList and LinkedList do currently work as advertized   However  there are some fine points that apply in the early 21st century   Modern computer technology seems  by my testing  to give an enormous edge to arrays   Elements of an array can be shifted and copied at insane speeds   As a result arrays and ArrayList will  in most practical situations  outperform LinkedList on inserts and deletes  often dramatically   In other words  ArrayList will beat LinkedList at its own game   The downside of ArrayList is it tends to hang onto memory space after deletions  where LinkedList gives up space as it gives up entries   The bigger downside of arrays and ArrayList is they fragment free memory and overwork the garbage collector   As an ArrayList expands  it creates new  bigger arrays  copies the old array to the new one  and frees the old one   Memory fills with big contiguous chunks of free memory that are not big enough for the next allocation   Eventually there s no suitable space for that allocation   Even though 90  of memory is free  no individual piece is big enough to do the job   The GC will work frantically to move things around  but if it takes too long to rearrange the space  it will throw an OutOfMemoryException   If it doesn t give up  it can still slow your program way down   The worst of it is this problem can be hard to predict   Your program will run fine one time   Then  with a bit less memory available  with no warning  it slows or stops   LinkedList uses small  dainty bits of memory and GC s love it   It still runs fine when you re using 99  of your available memory   So in general  use ArrayList for smaller sets of data that are not likely to have most of their contents deleted  or when you have tight control over creation and growth    For instance  creating one ArrayList that uses 90  of memory and using it without filling it for the duration of the program is fine   Continually creating and freeing ArrayList instances that use 10  of memory will kill you    Otherwise  go with LinkedList  or a Map of some sort if you need random access    If you have very large collections  say over 100 000 elements   no concerns about the GC  and plan lots of inserts and deletes and no random access  run a few benchmarks to see what s fastest

User · Answer

ArrayList is faster than LinkedList if I randomly access its elements  I think random access means  give me the nth element   Why ArrayList is faster    ArrayList has direct references to every element in the list  so it can get the n-th element in constant time  LinkedList has to traverse the list from the beginning to get to the n-th element      LinkedList is faster than ArrayList for deletion  I understand this one  ArrayList s slower since the internal backing-up array needs to be reallocated     ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free  If the deletion is done using the ListIterator remove   API  LinkedList just has to manipulate a couple of references  if the deletion is done by value or by index  LinkedList has to potentially scan the entire list first to find the element s  to be deleted      If it means move some elements back and then put the element in the middle empty spot  ArrayList should be slower    Yes  this is what it means  ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array  This involves moving some references around and in the worst case reallocating the entire array  LinkedList just has to manipulate some references

User · Answer

Even they seem to identical same implemented inteface List - non thread-safe  they give different results in terms of performance in add delete and searching time and consuming memory  LinkedList consumes more     LinkedLists can be used if you use highly insertion deletion with performance O 1    ArrayLists  can be used if you use direct access operations with performance O 1   This code may make clear of these comments and you can try to understand performance results    Sorry for boiler plate code    public class Test        private static Random rnd        static           rnd   new Random                static List lt String gt  testArrayList      static List lt String gt  testLinkedList      public static final int COUNT OBJ   2000000       public static void main String   args            testArrayList   new ArrayList lt  gt             testLinkedList   new LinkedList lt  gt              insertSomeDummyData testLinkedList           insertSomeDummyData testArrayList            checkInsertionPerformance testLinkedList      O 1          checkInsertionPerformance testArrayList       O 1  - gt  O n           checkPerformanceForFinding testArrayList       O 1          checkPerformanceForFinding testLinkedList      O n               public static void insertSomeDummyData List lt String gt  list            for  int i   COUNT OBJ  i--  gt  0                  list add new String      i                         public static void checkInsertionPerformance List lt String gt  list             long startTime  finishedTime          startTime   System currentTimeMillis            int rndIndex          for  int i   200  i--  gt  0                  rndIndex   rnd nextInt 100000               list add rndIndex   test                      finishedTime   System currentTimeMillis            System out println String format   s time passed at insertion  d   list getClass   getSimpleName     finishedTime - startTime                public static void checkPerformanceForFinding List lt String gt  list             long startTime  finishedTime          startTime   System currentTimeMillis            int rndIndex          for  int i   200  i--  gt  0                  rndIndex   rnd nextInt 100000               list get rndIndex                     finishedTime   System currentTimeMillis            System out println String format   s time passed at searching  d   list getClass   getSimpleName     finishedTime - startTime

User · Answer

Both remove   and insert   have a runtime efficiency of O n  for both ArrayLists and LinkedLists  However the reason behind the linear processing time comes from two very different reasons   In an ArrayList you get to the element in O 1   but actually removing or inserting something makes it O n  because all the following elements need to be changed   In a LinkedList it takes O n  to actually get to the desired element  because we have to start at the very beginning until we reach the desired index  Removing or inserting is constant once we get there  because we only have to change 1 reference for remove   and 2 references for insert     Which of the two is faster for inserting and removing depends on where it happens  If we are closer to the beginning the LinkedList will be faster  because we have to go through relatively few elements  If we are closer to the end an ArrayList will be faster  because we get there in constant time and only have to change the few remaining elements that follow it   Bonus  While there is no way of making these two methods O 1  for an ArrayList  there actually is a way to do this in LinkedLists  Lets say we want to go through the entire List removing and inserting elements on our way  Usually you would start from the very beginning for each elements using the LinkedList  we could also  save  the current element we re working on with an Iterator  With the help of the Iterator we get a O 1  efficiency for remove   and insert   when working in a LinkedList  Making it the only performance benefit I m aware of where a LinkedList is always better than an ArrayList

User · Answer

The ArrayList class is a wrapper class for an array  It contains an inner array   public ArrayList lt T gt        private Object   array      private int size      A LinkedList is a wrapper class for a linked list  with an inner node for managing the data   public LinkedList lt T gt        class Node lt T gt            T data          Node next          Node prev            private Node lt T gt  first      private Node lt T gt  last      private int size      Note  the present code is used to show how the class may be  not the actual implementation  Knowing how the implementation may be  we can do the further analysis      ArrayList is faster than LinkedList if I randomly access its elements  I think random access means  give me the nth element   Why ArrayList is faster    Access time for ArrayList  O 1   Access time for LinkedList  O n    In an array  you can access to any element by using array index   while in a linked list you must navigate through all the list starting from first until you get the element you need      LinkedList is faster than ArrayList for deletion  I understand this one  ArrayList s slower since the internal backing-up array needs to be reallocated    Deletion time for ArrayList  Access time   O n   Deletion time for LinkedList  Access time   O 1    The ArrayList must move all the elements from array index  to array index-1  starting by the item to delete index  The LinkedList should navigate until that item and then erase that node by decoupling it from the list      LinkedList is faster than ArrayList for deletion  I understand this one  ArrayList s slower since the internal backing-up array needs to be reallocated    Insertion time for ArrayList  O n   Insertion time for LinkedList  O 1    Why the ArrayList can take O n   Because when you insert a new element and the array is full  you need to create a new array with more size  you can calculate the new size with a formula like 2   size or 3   size   2   The LinkedList just add a new node next to the last   This analysis is not just in Java but in another programming languages like C  C   and C     More info here    http   en wikipedia org wiki Array data structure http   en wikipedia org wiki Linked list

User · Answer

In a LinkedList the elements have a reference to the element before and after it  In an ArrayList the data structure is just an array    A LinkedList needs to iterate over N elements to get the Nth element  An ArrayList only needs to return element N of the backing array  The backing array needs to either be reallocated for the new size and the array copied over or every element after the deleted element needs to be moved up to fill the empty space  A LinkedList just needs to set the previous reference on the element after the removed to the one before the removed and the next reference on the element before the removed element to the element after the removed element  Longer to explain  but faster to do  Same reason as deletion here

User · Answer

ArrayList  ArrayList has a structure like an array  it has a direct reference to every element  So rendom access is fast in ArrayList   LinkedList  In LinkedList for getting nth elemnt you have to traverse whole list  takes time as compared to ArrayList  Every element has a link to its previous  amp  nest element  so deletion is fast

User · Answer

ArrayList  The ArrayList class extends AbstractList and implements the List interface and RandomAccess  marker interface   ArrayList supports dynamic arrays that can grow as needed  It gives us first iteration over elements   LinkedList  A LinkedList is ordered by index position  like ArrayList  except that the elements are doubly-linked to one another  This linkage gives you new methods  beyond what you get from the List interface  for adding and removing from the beginning or end  which makes it an easy choice for implementing a stack or queue  Keep in mind that a LinkedList may iterate more slowly than an ArrayList  but it s a good choice when you need fast insertion and deletion  As of Java 5  the LinkedList class has been enhanced to implement the java util Queue interface  As such  it now supports the common queue methods  peek     poll     and offer

User · Answer

I want to add an additional piece of information her about the difference in performance    We already know that due to the fact that ArrayList implementation is backed by an Object   it s supports random access and dynamic resizing and LinkedList implementation uses references to head and tail to navigate it  It has no random access capabilities  but it supports dynamic resizing as well   The first thing is that with an ArrayList  you can immediately access the index  whereas with a LinkedList  you have iterate down the object chain   Secondly  inserting into ArrayList is generally slower because it has to grow once you hit its boundaries  It will have to create a new bigger array  and copy data from the original one   But the interesting thing is that when you create an ArrayList that is already huge enough to fit all your inserts it will obviously not involve any array copying operations  Adding to it will be even faster than with LinkedList because LinkedList will have to deal with its pointers  while huge ArrayList just sets value at given index     Check out for more ArrayList and LinkedList differences

User · Answer

Answer to 1  ArrayList uses an array under the hood   Accessing a member of an ArrayList object is as simple as accessing the array at the provided index  assuming the index is within the bounds of the backing array   A LinkedList has to iterate through its members to get to the nth element   That s O n  for a LinkedList  versus O 1  for ArrayList

[java] Performance differences between ArrayList and LinkedList

Examples related to java

Examples related to arraylist

Examples related to doubly-linked-list