When to use LinkedList over ArrayList in Java

Question

I ve always been one to simply use   List lt String gt  names   new ArrayList lt  gt       I use the interface as the type name for portability  so that when I ask questions such as these I can rework my code     When should LinkedList be used over ArrayList and vice-versa

User · Answer

ArrayList is randomly accessible  while LinkedList is really cheap to expand and remove elements from  For most cases  ArrayList is fine   Unless you ve created large lists and measured a bottleneck  you ll probably never need to worry about the difference

User · Answer

In addition to the other good arguments above  you should notice ArrayList implements RandomAccess interface  while LinkedList implements Queue   So  somehow they address slightly different problems  with difference of efficiency and behavior  see their list of methods

User · Answer

Correct or Incorrect  Please execute test locally and decide for yourself   Edit Remove is faster in LinkedList than ArrayList   ArrayList  backed by Array  which needs to be double the size  is worse in large volume application   Below is the unit test result for each operation Timing is given in Nanoseconds     Operation                       ArrayList                      LinkedList    AddAll    Insert                101 16719                      2623 29291   Add       Insert-Sequentially   152 46840                      966 62216  Add       insert-randomly       36527                          29193  remove    Delete                20 56 9095                     20 45 4904  contains  Search                186 15 704                     189 64 981     Here s the code   import org junit Assert  import org junit Test   import java util     public class ArrayListVsLinkedList       private static final int MAX   500000      String   strings   maxArray                        ADD ALL                                               Test     public void arrayListAddAll             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            watch start            arrayList addAll stringList           watch totalTime  Array List addAll          101 16719 Nanoseconds             Test     public void linkedListAddAll   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings            watch start            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll stringList           watch totalTime  Linked List addAll            2623 29291 Nanoseconds              Note  ArrayList is 26 time faster here than LinkedList for addAll                          INSERT                                                    Test     public void arrayListAdd             Watch watch   new Watch            List lt String gt  arrayList   new ArrayList lt String gt  MAX            watch start            for  String string   strings              arrayList add string           watch totalTime  Array List add          152 46840 Nanoseconds             Test     public void linkedListAdd             Watch watch   new Watch             List lt String gt  linkedList   new LinkedList lt String gt             watch start            for  String string   strings              linkedList add string           watch totalTime  Linked List add            966 62216 Nanoseconds              Note  ArrayList is 9 times faster than LinkedList for add sequentially                          INSERT IN BETWEEN                                               Test     public void arrayListInsertOne             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX   MAX   10           arrayList addAll stringList            String insertString0   getString true  MAX   2   10           String insertString1   getString true  MAX   2   20           String insertString2   getString true  MAX   2   30           String insertString3   getString true  MAX   2   40            watch start             arrayList add insertString0           arrayList add insertString1           arrayList add insertString2           arrayList add insertString3            watch totalTime  Array List add          36527             Test     public void linkedListInsertOne             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll stringList            String insertString0   getString true  MAX   2   10           String insertString1   getString true  MAX   2   20           String insertString2   getString true  MAX   2   30           String insertString3   getString true  MAX   2   40            watch start             linkedList add insertString0           linkedList add insertString1           linkedList add insertString2           linkedList add insertString3            watch totalTime  Linked List add        29193               Note  LinkedList is 3000 nanosecond faster than ArrayList for insert randomly                          DELETE                                                             Test     public void arrayListRemove   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            arrayList addAll stringList           String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            arrayList remove searchString0           arrayList remove searchString1           watch totalTime  Array List remove          20 56 9095 Nanoseconds             Test     public void linkedListRemove   throws Exception           Watch watch   new Watch            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll Arrays asList strings             String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            linkedList remove searchString0           linkedList remove searchString1           watch totalTime  Linked List remove        20 45 4904 Nanoseconds              Note  LinkedList is 10 millisecond faster than ArrayList while removing item                             SEARCH                                                  Test     public void arrayListSearch   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            arrayList addAll stringList           String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            arrayList contains searchString0           arrayList contains searchString1           watch totalTime  Array List addAll   time        186 15 704             Test     public void linkedListSearch   throws Exception           Watch watch   new Watch            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll Arrays asList strings             String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            linkedList contains searchString0           linkedList contains searchString1           watch totalTime  Linked List addAll   time        189 64 981              Note  Linked List is 500 Milliseconds faster than ArrayList      class Watch           private long startTime          private long endTime           public void start                 startTime   System nanoTime                       private void stop                 endTime   System nanoTime                       public void totalTime String s                stop                System out println s    endTime - startTime                          private String   maxArray             String   strings   new String MAX           Boolean result   Boolean TRUE          for  int i   0  i  lt  MAX  i                  strings i    getString result  i               result    result                    return strings             private String getString Boolean result  int i            return String valueOf result    i   String valueOf  result

User · Answer

First of all use Vector instead ArrayList because you can overrite insureCapasity method   in ArrayList is private and add 1 5 size of current array https   docs oracle com javase 8 docs api java util Vector html ensureCapacity-int-  in many case it can be better that linkedList  the las has big advantage one you insert data with high freqency so size of you list changes very fast and you can t allocate size for number elements   In the theory you can get error like not  enough memory   but  in modern computers you have 16G and swaping disk  so if you list is billoins elements you can fail  comparing 15-20 years ago

User · Answer

Here is the Big-O notation in both ArrayList and LinkedList and also CopyOnWrite-ArrayList   ArrayList  get                 O 1  add                 O 1  contains            O n  next                O 1  remove              O n  iterator remove     O n    LinkedList  get                 O n  add                 O 1  contains            O n  next                O 1  remove              O 1  iterator remove     O 1    CopyOnWrite-ArrayList  get                 O 1  add                 O n  contains            O n  next                O 1  remove              O n  iterator remove     O n    Based on these you have to decide what to choose

User · Answer

I know this is an old post  but I honestly can t believe nobody mentioned that LinkedList implements Deque   Just look at the methods in Deque  and Queue   if you want a fair comparison  try running LinkedList against ArrayDeque and do a feature-for-feature comparison

User · Answer

My rule of thumb is if I need a Collection  i e  doesn t need to be a List  then use ArrayList if you know the size in advance  or can know the size confidently  or know that it won t vary much  If you need random access  i e  you use get index   then avoid LinkedList  Basically  use LinkedList only if you don t need index access and don t know the  approximate  size of the collection you re allocating  Also if you re going to be making lots of additions and removals  again through the Collection interface  then LinkedList may be preferable

User · Answer

It depends upon what operations you will be doing more on the List   ArrayList is faster to access an indexed value  It is much worse when inserting or deleting objects   To find out more  read any article that talks about the difference between arrays and linked lists

User · Answer

In addition to the other good arguments above  you should notice ArrayList implements RandomAccess interface  while LinkedList implements Queue   So  somehow they address slightly different problems  with difference of efficiency and behavior  see their list of methods

User · Answer

ArrayList is what you want  LinkedList is almost always a  performance  bug  Why LinkedList sucks   It uses lots of small memory objects  and therefore impacts performance across the process  Lots of small objects are bad for cache-locality  Any indexed operation requires a traversal  i e  has O n  performance  This is not obvious in the source code  leading to algorithms O n  slower than if ArrayList was used  Getting good performance is tricky  Even when big-O performance is the same as ArrayList  it is probably going to be significantly slower anyway  It s jarring to see LinkedList in source because it is probably the wrong choice

User · Answer

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList  If you re not sure      just start with ArrayList   TLDR  in ArrayList accessing an element takes constant time  O 1   and adding an element takes O n  time  worst case   In LinkedList adding an element takes O n  time and accessing also takes O n  time but LinkedList uses more memory than ArrayList  LinkedList and ArrayList are two different implementations of the List interface  LinkedList implements it with a doubly-linked list  ArrayList implements it with a dynamically re-sizing array  As with standard linked list and array operations  the various methods will have different algorithmic runtimes  For LinkedList lt E gt   get int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use getFirst   and getLast     One of the main benefits of LinkedList lt E gt  add int index  E element  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use addFirst   and addLast   add     One of the main benefits of LinkedList lt E gt  remove int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use removeFirst   and removeLast     One of the main benefits of LinkedList lt E gt  Iterator remove   is O 1   One of the main benefits of LinkedList lt E gt  ListIterator add E element  is O 1   One of the main benefits of LinkedList lt E gt   Note  Many of the operations need n 4 steps on average  constant number of steps in the best case  e g  index   0   and n 2 steps in worst case  middle of list  For ArrayList lt E gt   get int index  is O 1   Main benefit of ArrayList lt E gt  add E element  is O 1  amortized  but O n  worst-case since the array must be resized and copied add int index  E element  is O n   with n 2 steps on average  remove int index  is O n   with n 2 steps on average  Iterator remove   is O n   with n 2 steps on average  ListIterator add E element  is O n   with n 2 steps on average   Note  Many of the operations need n 2 steps on average  constant number of steps in the best case  end of list   n steps in the worst case  start of list  LinkedList lt E gt  allows for constant-time insertions or removals using iterators  but only sequential access of elements  In other words  you can walk the list forwards or backwards  but finding a position in the list takes time proportional to the size of the list  Javadoc says  quot operations that index into the list will traverse the list from the beginning or the end  whichever is closer quot   so those methods are O n   n 4 steps  on average  though O 1  for index   0  ArrayList lt E gt   on the other hand  allow fast random read access  so you can grab any element in constant time  But adding or removing from anywhere but the end requires shifting all the latter elements over  either to make an opening or fill the gap  Also  if you add more elements than the capacity of the underlying array  a new array  1 5 times the size  is allocated  and the old array is copied to the new one  so adding to an ArrayList is O n  in the worst case but constant on average  So depending on the operations you intend to do  you should choose the implementations accordingly  Iterating over either kind of List is practically equally cheap   Iterating over an ArrayList is technically faster  but unless you re doing something really performance-sensitive  you shouldn t worry about this -- they re both constants   The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements  These operations can then be done in O 1  by changing the list locally only  In an array list  the remainder of the array needs to be moved  i e  copied   On the other side  seeking in a LinkedList means following the links in O n   n 2 steps  for worst case  whereas in an ArrayList the desired position can be computed mathematically and accessed in O 1   Another benefit of using a LinkedList arise when you add or remove from the head of the list  since those operations are O 1   while they are O n  for ArrayList  Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head  but it is not a List  Also  if you have large lists  keep in mind that memory usage is also different  Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored  ArrayLists don t have this overhead  However  ArrayLists take up as much memory as is allocated for the capacity  regardless of whether elements have actually been added  The default initial capacity of an ArrayList is pretty small  10 from Java 1 4 - 1 8   But since the underlying implementation is an array  the array must be resized if you add a lot of elements  To avoid the high cost of resizing when you know you re going to add a lot of elements  construct the ArrayList with a higher initial capacity  If the data structures perspective is used to understand the two structures  a LinkedList is basically a sequential data structure which contains a head Node  The Node is a wrapper for two components   a value of type T  accepted through generics  and another reference to the Node linked to it  So  we can assert it is a recursive data structure  a Node contains another Node which has another Node and so on      Addition of elements takes linear time in LinkedList as stated above  An ArrayList  is a growable array  It is just like a regular array  Under the hood  when an element is added at index i  it creates another array with a size which is 1 greater than previous size  So in general  when n elements are to be added to an ArrayList  a new array of size previous size plus n is created   The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices

User · Answer

Correct or Incorrect  Please execute test locally and decide for yourself   Edit Remove is faster in LinkedList than ArrayList   ArrayList  backed by Array  which needs to be double the size  is worse in large volume application   Below is the unit test result for each operation Timing is given in Nanoseconds     Operation                       ArrayList                      LinkedList    AddAll    Insert                101 16719                      2623 29291   Add       Insert-Sequentially   152 46840                      966 62216  Add       insert-randomly       36527                          29193  remove    Delete                20 56 9095                     20 45 4904  contains  Search                186 15 704                     189 64 981     Here s the code   import org junit Assert  import org junit Test   import java util     public class ArrayListVsLinkedList       private static final int MAX   500000      String   strings   maxArray                        ADD ALL                                               Test     public void arrayListAddAll             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            watch start            arrayList addAll stringList           watch totalTime  Array List addAll          101 16719 Nanoseconds             Test     public void linkedListAddAll   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings            watch start            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll stringList           watch totalTime  Linked List addAll            2623 29291 Nanoseconds              Note  ArrayList is 26 time faster here than LinkedList for addAll                          INSERT                                                    Test     public void arrayListAdd             Watch watch   new Watch            List lt String gt  arrayList   new ArrayList lt String gt  MAX            watch start            for  String string   strings              arrayList add string           watch totalTime  Array List add          152 46840 Nanoseconds             Test     public void linkedListAdd             Watch watch   new Watch             List lt String gt  linkedList   new LinkedList lt String gt             watch start            for  String string   strings              linkedList add string           watch totalTime  Linked List add            966 62216 Nanoseconds              Note  ArrayList is 9 times faster than LinkedList for add sequentially                          INSERT IN BETWEEN                                               Test     public void arrayListInsertOne             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX   MAX   10           arrayList addAll stringList            String insertString0   getString true  MAX   2   10           String insertString1   getString true  MAX   2   20           String insertString2   getString true  MAX   2   30           String insertString3   getString true  MAX   2   40            watch start             arrayList add insertString0           arrayList add insertString1           arrayList add insertString2           arrayList add insertString3            watch totalTime  Array List add          36527             Test     public void linkedListInsertOne             Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll stringList            String insertString0   getString true  MAX   2   10           String insertString1   getString true  MAX   2   20           String insertString2   getString true  MAX   2   30           String insertString3   getString true  MAX   2   40            watch start             linkedList add insertString0           linkedList add insertString1           linkedList add insertString2           linkedList add insertString3            watch totalTime  Linked List add        29193               Note  LinkedList is 3000 nanosecond faster than ArrayList for insert randomly                          DELETE                                                             Test     public void arrayListRemove   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            arrayList addAll stringList           String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            arrayList remove searchString0           arrayList remove searchString1           watch totalTime  Array List remove          20 56 9095 Nanoseconds             Test     public void linkedListRemove   throws Exception           Watch watch   new Watch            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll Arrays asList strings             String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            linkedList remove searchString0           linkedList remove searchString1           watch totalTime  Linked List remove        20 45 4904 Nanoseconds              Note  LinkedList is 10 millisecond faster than ArrayList while removing item                             SEARCH                                                  Test     public void arrayListSearch   throws Exception           Watch watch   new Watch            List lt String gt  stringList   Arrays asList strings           List lt String gt  arrayList   new ArrayList lt String gt  MAX            arrayList addAll stringList           String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            arrayList contains searchString0           arrayList contains searchString1           watch totalTime  Array List addAll   time        186 15 704             Test     public void linkedListSearch   throws Exception           Watch watch   new Watch            List lt String gt  linkedList   new LinkedList lt String gt             linkedList addAll Arrays asList strings             String searchString0   getString true  MAX   2   10           String searchString1   getString true  MAX   2   20            watch start            linkedList contains searchString0           linkedList contains searchString1           watch totalTime  Linked List addAll   time        189 64 981              Note  Linked List is 500 Milliseconds faster than ArrayList      class Watch           private long startTime          private long endTime           public void start                 startTime   System nanoTime                       private void stop                 endTime   System nanoTime                       public void totalTime String s                stop                System out println s    endTime - startTime                          private String   maxArray             String   strings   new String MAX           Boolean result   Boolean TRUE          for  int i   0  i  lt  MAX  i                  strings i    getString result  i               result    result                    return strings             private String getString Boolean result  int i            return String valueOf result    i   String valueOf  result

User · Answer

It s an efficiency question  LinkedList is fast for adding and deleting elements  but slow to access a specific element  ArrayList is fast for accessing a specific element but can be slow to add to either end  and especially slow to delete in the middle   Array vs ArrayList vs LinkedList vs Vector goes more in depth  as does  Linked List

User · Answer

Here is the Big-O notation in both ArrayList and LinkedList and also CopyOnWrite-ArrayList   ArrayList  get                 O 1  add                 O 1  contains            O n  next                O 1  remove              O n  iterator remove     O n    LinkedList  get                 O n  add                 O 1  contains            O n  next                O 1  remove              O 1  iterator remove     O 1    CopyOnWrite-ArrayList  get                 O 1  add                 O n  contains            O n  next                O 1  remove              O n  iterator remove     O n    Based on these you have to decide what to choose

User · Answer

In addition to the other good arguments above  you should notice ArrayList implements RandomAccess interface  while LinkedList implements Queue   So  somehow they address slightly different problems  with difference of efficiency and behavior  see their list of methods

User · Answer

ArrayList is what you want  LinkedList is almost always a  performance  bug  Why LinkedList sucks   It uses lots of small memory objects  and therefore impacts performance across the process  Lots of small objects are bad for cache-locality  Any indexed operation requires a traversal  i e  has O n  performance  This is not obvious in the source code  leading to algorithms O n  slower than if ArrayList was used  Getting good performance is tricky  Even when big-O performance is the same as ArrayList  it is probably going to be significantly slower anyway  It s jarring to see LinkedList in source because it is probably the wrong choice

User · Answer

Yeah  I know  this is an ancient question  but I ll throw in my two cents   LinkedList is almost always the wrong choice  performance-wise   There are some very specific algorithms where a LinkedList is called for  but those are very  very rare and the algorithm will usually specifically depend on LinkedList s ability to insert and delete elements in the middle of the list relatively quickly  once you ve navigated there with a ListIterator   There is one common use case in which LinkedList outperforms ArrayList  that of a queue   However  if your goal is performance  instead of LinkedList you should also consider using an ArrayBlockingQueue  if you can determine an upper bound on your queue size ahead of time  and can afford to allocate all the memory up front   or this CircularArrayList implementation    Yes  it s from 2001  so you ll need to generify it  but I got comparable performance ratios to what s quoted in the article just now in a recent JVM

User · Answer

See the Java Tutorials - List Implementations

User · Answer

ArrayList extends AbstractList and implements the List Interface  ArrayList is dynamic array It can be said that it was basically created to overcome the drawbacks of arrays The LinkedList class extends AbstractSequentialList and implements List Deque  and Queue interface  Performance arraylist get   is  O 1  whereas linkedlist get   is O n   arraylist add   is  O 1  and linkedlist add   is 0 1  arraylist contains   is O n  andlinkedlist contains   is O n   arraylist next   is O 1  and linkedlist next   is O 1  arraylist remove   is O n  whereas linkedlist remove   is O 1  In arraylistiterator remove   is O n  whereas In linkedlist iterator remove  is O 1

User · Answer

Yeah  I know  this is an ancient question  but I ll throw in my two cents   LinkedList is almost always the wrong choice  performance-wise   There are some very specific algorithms where a LinkedList is called for  but those are very  very rare and the algorithm will usually specifically depend on LinkedList s ability to insert and delete elements in the middle of the list relatively quickly  once you ve navigated there with a ListIterator   There is one common use case in which LinkedList outperforms ArrayList  that of a queue   However  if your goal is performance  instead of LinkedList you should also consider using an ArrayBlockingQueue  if you can determine an upper bound on your queue size ahead of time  and can afford to allocate all the memory up front   or this CircularArrayList implementation    Yes  it s from 2001  so you ll need to generify it  but I got comparable performance ratios to what s quoted in the article just now in a recent JVM

User · Answer

Algorithm           ArrayList   LinkedList seek front            O 1          O 1  seek back             O 1          O 1  seek to index         O 1          O N  insert at front       O N          O 1  insert at back        O 1          O 1  insert after an item  O N          O 1   Algorithms  Big-Oh Notation  archived  ArrayLists are good for write-once-read-many or appenders  but bad at add remove from the front or middle

User · Answer

Operation get i  in ArrayList is faster than LinkedList  because  ArrayList  Resizable-array implementation of the List interface LinkedList  Doubly-linked list implementation of the List and Deque interfaces  Operations that index into the list will traverse the list from the beginning or the end  whichever is closer to the specified index

User · Answer

An array list is essentially an array with methods to add items etc   and you should use a generic list instead   It is a collection of items which can be accessed through an indexer   for example  0    It implies a progression from one item to the next   A linked list specifies a progression from one item to the next  Item a -  item b    You can get the same effect with an array list  but a linked list absolutely says what item is supposed to follow the previous one

User · Answer

See the Java Tutorials - List Implementations

User · Answer

In addition to the other good arguments above  you should notice ArrayList implements RandomAccess interface  while LinkedList implements Queue   So  somehow they address slightly different problems  with difference of efficiency and behavior  see their list of methods

User · Answer

One of the tests I saw on here only conducts the test once   But what I have noticed is that you need to run these tests many times and eventually their times will converge   Basically the JVM needs to warm up   For my particular use case I needed to add remove items to a list that grows to about 500 items   In my tests LinkedList came out faster  with LinkedList coming in around 50 000 NS and ArrayList coming in at around 90 000 NS    give or take   See the code below   public static void main String   args        List lt Long gt  times   new ArrayList lt  gt         for  int i   0  i  lt  100  i              times add doIt               System out println  avg        times stream   mapToLong x - gt  x  average         static long doIt         long start   System nanoTime        List lt Object gt  list   new LinkedList lt  gt           uncomment line below to test with ArrayList       list   new ArrayList lt  gt         for  int i   0  i  lt  500  i              list add i              Iterator it   list iterator        while  it hasNext              it next            it remove              long end   System nanoTime        long diff   end - start        uncomment to see the JVM warmup and get faster for the first few iterations       System out println diff      return diff

User · Answer

ArrayList and LinkedList have their own pros and cons   ArrayList uses contiguous memory address compared to LinkedList which uses pointers toward the next node  So when you want to look up an element in an ArrayList is faster than doing n iterations with LinkedList   On the other hand  insertion and deletion in a LinkedList are much easier because you just have to change the pointers whereas an ArrayList implies the use of shift operation for any insertion or deletion   If you have frequent retrieval operations in your app use an ArrayList  If you have frequent insertion and deletion use a LinkedList

User · Answer

1  Underlying Data Structure The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList  This will lead to further differences in performance  2  LinkedList implements Deque Another difference between ArrayList and LinkedList is that apart from the List interface  LinkedList also implements Deque interface  which provides first in first out operations for add   and poll   and several other Deque functions  3  Adding elements in ArrayList Adding element in ArrayList is O 1  operation if it doesn t trigger re-size of Array  in which case it becomes O log n    On the other hand  appending an element in LinkedList is O 1  operation  as it doesn t require any navigation  4  Removing an element from a position In order to remove an element from a particular index e g  by calling remove index   ArrayList performs a copy operation which makes it close to O n  while LinkedList needs to traverse to that point which also makes it O n 2   as it can traverse from either direction based upon proximity  5  Iterating over ArrayList or LinkedList Iteration is the O n  operation for both LinkedList and ArrayList where n is a number of an element  6  Retrieving element from a position The get index  operation is O 1  in ArrayList while its O n 2  in LinkedList  as it needs to traverse till that entry  Though  in Big O notation O n 2  is just O n  because we ignore constants there  7  Memory LinkedList uses a wrapper object  Entry  which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array  So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another  If Array is large enough it may take a lot of memory at that point and trigger Garbage collection  which can slow response time  From all the above differences between ArrayList vs LinkedList  It looks ArrayList is the better choice than LinkedList in almost all cases  except when you do a frequent add   operation than remove    or get    It s easier to modify a linked list than ArrayList  especially if you are adding or removing elements from start or end because linked list internally keeps references of those positions and they are accessible in O 1  time  In other words  you don t need to traverse through the linked list to reach the position where you want to add elements  in that case  addition becomes O n  operation  For example  inserting or deleting an element in the middle of a linked list  In my opinion  use ArrayList over LinkedList for most of the practical purpose in Java

User · Answer

TL DR due to modern computer architecture  ArrayList will be significantly more efficient for nearly any possible use-case - and therefore LinkedList should be avoided except some very unique and extreme cases     In theory  LinkedList has an O 1  for the add E element   Also adding an element in the mid of a list should be very efficient   Practice is very different  as LinkedList is a Cache Hostile Data structure  From performance POV - there are very little cases where LinkedList could be better performing than the Cache-friendly ArrayList   Here are results of a benchmark testing inserting elements in random locations  As you can see - the array list if much more efficient  although in theory each insert in the middle of the list will require  move  the n later elements of the array  lower values are better      Working on a later generation hardware  bigger  more efficient caches  - the results are even more conclusive     LinkedList takes much more time to accomplish the same job  source Source Code  There are two main reasons for this    Mainly - that the nodes of the LinkedList are scattered randomly across the memory  RAM   Random Access Memory   isn t really random and blocks of memory need to be fetched to cache  This operation takes time  and when such fetches happen frequently - the memory pages in the cache need to be replaced all the time -  Cache misses -  Cache is not efficient  ArrayList elements are stored on continuous memory - which is exactly what the modern CPU architecture is optimizing for  Secondary LinkedList required to hold back forward pointers  which means 3 times the memory consumption per value stored compared to ArrayList    DynamicIntArray  btw  is a custom ArrayList implementation holding Int  primitive type  and not Objects - hence all data is really stored adjacently - hence even more efficient   A key elements to remember is that the cost of fetching memory block  is more significant than the cost accessing a single memory cell  That s why reader 1MB of sequential memory is up to x400 times faster than reading this amount of data from different blocks of memory   Latency Comparison Numbers   2012  ---------------------------------- L1 cache reference                           0 5 ns Branch mispredict                            5   ns L2 cache reference                           7   ns                      14x L1 cache Mutex lock unlock                           25   ns Main memory reference                      100   ns                      20x L2 cache  200x L1 cache Compress 1K bytes with Zippy             3 000   ns        3 us Send 1K bytes over 1 Gbps network       10 000   ns       10 us Read 4K randomly from SSD              150 000   ns      150 us           1GB sec SSD Read 1 MB sequentially from memory     250 000   ns      250 us Round trip within same datacenter      500 000   ns      500 us Read 1 MB sequentially from SSD      1 000 000   ns    1 000 us    1 ms   1GB sec SSD  4X memory Disk seek                           10 000 000   ns   10 000 us   10 ms  20x datacenter roundtrip Read 1 MB sequentially from disk    20 000 000   ns   20 000 us   20 ms  80x memory  20X SSD Send packet CA- gt Netherlands- gt CA    150 000 000   ns  150 000 us  150 ms   Source  Latency Numbers Every Programmer Should Know  Just to make the point even clearer  please check the benchmark of adding elements to the beginning of the list  This is a use-case where  in-theory  the LinkedList should really shine  and ArrayList should present poor or even worse-case results     Note  this is a benchmark of the C   Std lib  but my previous experience shown the C   and Java results are very similar  Source Code  Copying a sequential bulk of memory is an operation optimized by the modern CPUs - changing theory and actually making  again  ArrayList Vector much more efficient    Credits  All benchmarks posted here are created by Kjell Hedstr  m  Even more data can be found on his blog

User · Answer

Algorithm           ArrayList   LinkedList seek front            O 1          O 1  seek back             O 1          O 1  seek to index         O 1          O N  insert at front       O N          O 1  insert at back        O 1          O 1  insert after an item  O N          O 1   Algorithms  Big-Oh Notation  archived  ArrayLists are good for write-once-read-many or appenders  but bad at add remove from the front or middle

User · Answer

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList  If you re not sure      just start with ArrayList   TLDR  in ArrayList accessing an element takes constant time  O 1   and adding an element takes O n  time  worst case   In LinkedList adding an element takes O n  time and accessing also takes O n  time but LinkedList uses more memory than ArrayList  LinkedList and ArrayList are two different implementations of the List interface  LinkedList implements it with a doubly-linked list  ArrayList implements it with a dynamically re-sizing array  As with standard linked list and array operations  the various methods will have different algorithmic runtimes  For LinkedList lt E gt   get int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use getFirst   and getLast     One of the main benefits of LinkedList lt E gt  add int index  E element  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use addFirst   and addLast   add     One of the main benefits of LinkedList lt E gt  remove int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use removeFirst   and removeLast     One of the main benefits of LinkedList lt E gt  Iterator remove   is O 1   One of the main benefits of LinkedList lt E gt  ListIterator add E element  is O 1   One of the main benefits of LinkedList lt E gt   Note  Many of the operations need n 4 steps on average  constant number of steps in the best case  e g  index   0   and n 2 steps in worst case  middle of list  For ArrayList lt E gt   get int index  is O 1   Main benefit of ArrayList lt E gt  add E element  is O 1  amortized  but O n  worst-case since the array must be resized and copied add int index  E element  is O n   with n 2 steps on average  remove int index  is O n   with n 2 steps on average  Iterator remove   is O n   with n 2 steps on average  ListIterator add E element  is O n   with n 2 steps on average   Note  Many of the operations need n 2 steps on average  constant number of steps in the best case  end of list   n steps in the worst case  start of list  LinkedList lt E gt  allows for constant-time insertions or removals using iterators  but only sequential access of elements  In other words  you can walk the list forwards or backwards  but finding a position in the list takes time proportional to the size of the list  Javadoc says  quot operations that index into the list will traverse the list from the beginning or the end  whichever is closer quot   so those methods are O n   n 4 steps  on average  though O 1  for index   0  ArrayList lt E gt   on the other hand  allow fast random read access  so you can grab any element in constant time  But adding or removing from anywhere but the end requires shifting all the latter elements over  either to make an opening or fill the gap  Also  if you add more elements than the capacity of the underlying array  a new array  1 5 times the size  is allocated  and the old array is copied to the new one  so adding to an ArrayList is O n  in the worst case but constant on average  So depending on the operations you intend to do  you should choose the implementations accordingly  Iterating over either kind of List is practically equally cheap   Iterating over an ArrayList is technically faster  but unless you re doing something really performance-sensitive  you shouldn t worry about this -- they re both constants   The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements  These operations can then be done in O 1  by changing the list locally only  In an array list  the remainder of the array needs to be moved  i e  copied   On the other side  seeking in a LinkedList means following the links in O n   n 2 steps  for worst case  whereas in an ArrayList the desired position can be computed mathematically and accessed in O 1   Another benefit of using a LinkedList arise when you add or remove from the head of the list  since those operations are O 1   while they are O n  for ArrayList  Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head  but it is not a List  Also  if you have large lists  keep in mind that memory usage is also different  Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored  ArrayLists don t have this overhead  However  ArrayLists take up as much memory as is allocated for the capacity  regardless of whether elements have actually been added  The default initial capacity of an ArrayList is pretty small  10 from Java 1 4 - 1 8   But since the underlying implementation is an array  the array must be resized if you add a lot of elements  To avoid the high cost of resizing when you know you re going to add a lot of elements  construct the ArrayList with a higher initial capacity  If the data structures perspective is used to understand the two structures  a LinkedList is basically a sequential data structure which contains a head Node  The Node is a wrapper for two components   a value of type T  accepted through generics  and another reference to the Node linked to it  So  we can assert it is a recursive data structure  a Node contains another Node which has another Node and so on      Addition of elements takes linear time in LinkedList as stated above  An ArrayList  is a growable array  It is just like a regular array  Under the hood  when an element is added at index i  it creates another array with a size which is 1 greater than previous size  So in general  when n elements are to be added to an ArrayList  a new array of size previous size plus n is created   The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices

User · Answer

An array list is essentially an array with methods to add items etc   and you should use a generic list instead   It is a collection of items which can be accessed through an indexer   for example  0    It implies a progression from one item to the next   A linked list specifies a progression from one item to the next  Item a -  item b    You can get the same effect with an array list  but a linked list absolutely says what item is supposed to follow the previous one

User · Answer

It depends upon what operations you will be doing more on the List   ArrayList is faster to access an indexed value  It is much worse when inserting or deleting objects   To find out more  read any article that talks about the difference between arrays and linked lists

User · Answer

ArrayList and LinkedList both implements List interface  and their methods and results are almost identical  However there are few differences between them which make one better over another depending on the requirement   ArrayList Vs LinkedList  1  Search  ArrayList search operation is pretty fast compared to the LinkedList search operation  get int index  in ArrayList gives the performance of O 1  while LinkedList performance is O n    Reason  ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list  On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element   2  Deletion  LinkedList remove operation gives O 1  performance while ArrayList gives variable performance  O n  in worst case  while removing first element  and O 1  in best case  While removing last element       Conclusion  LinkedList element deletion is faster compared to   ArrayList    Reason  LinkedList   s each element maintains two pointers  addresses  which points to the both neighbor elements in the list  Hence removal only requires change in the pointer location in the two neighbor nodes  elements  of the node which is going to be removed  While In ArrayList all the elements need to be shifted to fill out the space created by removed element   3  Inserts Performance  LinkedList add method gives O 1  performance while ArrayList gives O n  in worst case  Reason is same as explained for remove   4  Memory Overhead  ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes      hence the memory consumption is high in LinkedList comparatively    There are few similarities between these classes which are as follows    Both ArrayList and LinkedList are implementation of List interface  They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List  Both these classes are non-synchronized and can be made synchronized explicitly by using Collections synchronizedList method  The iterator and listIterator returned by these classes are fail-fast  if list is structurally modified at any time after the iterator is created  in any way except through the iterator   s own remove or add methods  the iterator will throw a ConcurrentModificationException     When to use LinkedList and when to use ArrayList    As explained above the insert and remove operations give good performance  O 1   in LinkedList compared to ArrayList O n        Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice   Search  get method  operations are fast in Arraylist  O 1   but not in LinkedList  O n        so If there are less add and remove operations and more search operations requirement  ArrayList would be your best bet

User · Answer

Thus far  nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList is  lots more  than an ArrayList so I did some number crunching to demonstrate exactly how much both lists take up for N null references   Since references are either 32 or 64 bits  even when null  on their relative systems  I have included 4 sets of data for 32 and 64 bit LinkedLists and ArrayLists   Note  The sizes shown for the ArrayList lines are for trimmed lists - In practice  the capacity of the backing array in an ArrayList is generally larger than its current element count   Note 2   thanks BeeOnRope  As CompressedOops is default now from mid JDK6 and up  the values below for 64-bit machines will basically match their 32-bit counterparts  unless of course you specifically turn it off         The result clearly shows that LinkedList is a whole lot more than ArrayList  especially with a very high element count  If memory is a factor  steer clear of LinkedLists   The formulas I used follow  let me know if I have done anything wrong and I will fix it up   b  is either 4 or 8 for 32 or 64 bit systems  and  n  is the number of elements  Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not   ArrayList   ArrayList object header   size integer   modCount integer   array reference    array oject header   b   n    MOD array oject  8    MOD ArrayList object  8     8   4   4   b    12   b   n    MOD 12   b   n  8    MOD 8   4   4   b    12   b   n    MOD 12   b   n  8   8   LinkedList   LinkedList object header   size integer   modCount integer   reference to header   reference to footer    node object overhead   reference to previous element   reference to next element   reference to element    n    MOD node object  8    n   MOD LinkedList object  8     8   4   4   2   b    8   3   b    n   MOD 8   3   b  8    n   MOD 8   4   4   2   b    8   3   b    n   MOD 8   3   b  8    n  8

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  Actually removing or inserting is constant  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  When done precisely in the middle the LinkedList will be faster because going through n elements is quicker than moving n values  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  Let s 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 element using the LinkedList  we could also  quot save quot  the current element we re working on with an Iterator  With the help of the Iterator  we get an 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

As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade  I would prefer the behavior of LinkedList over ArrayList   While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware -- the behavior of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage  while under pressure  which is catastrophic behavior   Similarly  you can get better throughput in an app from the default throughput tenured garbage collector  but once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows your SLAs if it occurs too often   Even though the CMS collector takes more resources and does not achieve the same raw throughput  it is a much better choice because it has more predictable and smaller latency   ArrayList is only a better choice for performance if all you mean by performance is throughput and you can ignore latency   In my experience at my job I cannot ignore worst-case latency

User · Answer

If your code has add 0  and remove 0   use a LinkedList and it s prettier addFirst   and removeFirst   methods  Otherwise  use ArrayList   And of course  Guava s ImmutableList is your best friend

User · Answer

It s an efficiency question  LinkedList is fast for adding and deleting elements  but slow to access a specific element  ArrayList is fast for accessing a specific element but can be slow to add to either end  and especially slow to delete in the middle   Array vs ArrayList vs LinkedList vs Vector goes more in depth  as does  Linked List

User · Answer

It depends upon what operations you will be doing more on the List   ArrayList is faster to access an indexed value  It is much worse when inserting or deleting objects   To find out more  read any article that talks about the difference between arrays and linked lists

User · Answer

I have read the responses  but there is one scenario where I always use a LinkedList over an ArrayList that I want to share to hear opinions   Every time I had a method that returns a list of data obtained from a DB I always use a LinkedList   My rationale was that because it is impossible to know exactly how many results am I getting  there will be not memory wasted  as in ArrayList with the difference between the capacity and actual number of elements   and there would be no time wasted trying to duplicate the capacity   As far a ArrayList  I agree that at least you should always use the constructor with the initial capacity  to minimize the duplication of the arrays as much as possible

User · Answer

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList  If you re not sure      just start with ArrayList   TLDR  in ArrayList accessing an element takes constant time  O 1   and adding an element takes O n  time  worst case   In LinkedList adding an element takes O n  time and accessing also takes O n  time but LinkedList uses more memory than ArrayList  LinkedList and ArrayList are two different implementations of the List interface  LinkedList implements it with a doubly-linked list  ArrayList implements it with a dynamically re-sizing array  As with standard linked list and array operations  the various methods will have different algorithmic runtimes  For LinkedList lt E gt   get int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use getFirst   and getLast     One of the main benefits of LinkedList lt E gt  add int index  E element  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use addFirst   and addLast   add     One of the main benefits of LinkedList lt E gt  remove int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use removeFirst   and removeLast     One of the main benefits of LinkedList lt E gt  Iterator remove   is O 1   One of the main benefits of LinkedList lt E gt  ListIterator add E element  is O 1   One of the main benefits of LinkedList lt E gt   Note  Many of the operations need n 4 steps on average  constant number of steps in the best case  e g  index   0   and n 2 steps in worst case  middle of list  For ArrayList lt E gt   get int index  is O 1   Main benefit of ArrayList lt E gt  add E element  is O 1  amortized  but O n  worst-case since the array must be resized and copied add int index  E element  is O n   with n 2 steps on average  remove int index  is O n   with n 2 steps on average  Iterator remove   is O n   with n 2 steps on average  ListIterator add E element  is O n   with n 2 steps on average   Note  Many of the operations need n 2 steps on average  constant number of steps in the best case  end of list   n steps in the worst case  start of list  LinkedList lt E gt  allows for constant-time insertions or removals using iterators  but only sequential access of elements  In other words  you can walk the list forwards or backwards  but finding a position in the list takes time proportional to the size of the list  Javadoc says  quot operations that index into the list will traverse the list from the beginning or the end  whichever is closer quot   so those methods are O n   n 4 steps  on average  though O 1  for index   0  ArrayList lt E gt   on the other hand  allow fast random read access  so you can grab any element in constant time  But adding or removing from anywhere but the end requires shifting all the latter elements over  either to make an opening or fill the gap  Also  if you add more elements than the capacity of the underlying array  a new array  1 5 times the size  is allocated  and the old array is copied to the new one  so adding to an ArrayList is O n  in the worst case but constant on average  So depending on the operations you intend to do  you should choose the implementations accordingly  Iterating over either kind of List is practically equally cheap   Iterating over an ArrayList is technically faster  but unless you re doing something really performance-sensitive  you shouldn t worry about this -- they re both constants   The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements  These operations can then be done in O 1  by changing the list locally only  In an array list  the remainder of the array needs to be moved  i e  copied   On the other side  seeking in a LinkedList means following the links in O n   n 2 steps  for worst case  whereas in an ArrayList the desired position can be computed mathematically and accessed in O 1   Another benefit of using a LinkedList arise when you add or remove from the head of the list  since those operations are O 1   while they are O n  for ArrayList  Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head  but it is not a List  Also  if you have large lists  keep in mind that memory usage is also different  Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored  ArrayLists don t have this overhead  However  ArrayLists take up as much memory as is allocated for the capacity  regardless of whether elements have actually been added  The default initial capacity of an ArrayList is pretty small  10 from Java 1 4 - 1 8   But since the underlying implementation is an array  the array must be resized if you add a lot of elements  To avoid the high cost of resizing when you know you re going to add a lot of elements  construct the ArrayList with a higher initial capacity  If the data structures perspective is used to understand the two structures  a LinkedList is basically a sequential data structure which contains a head Node  The Node is a wrapper for two components   a value of type T  accepted through generics  and another reference to the Node linked to it  So  we can assert it is a recursive data structure  a Node contains another Node which has another Node and so on      Addition of elements takes linear time in LinkedList as stated above  An ArrayList  is a growable array  It is just like a regular array  Under the hood  when an element is added at index i  it creates another array with a size which is 1 greater than previous size  So in general  when n elements are to be added to an ArrayList  a new array of size previous size plus n is created   The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices

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  Actually removing or inserting is constant  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  When done precisely in the middle the LinkedList will be faster because going through n elements is quicker than moving n values  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  Let s 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 element using the LinkedList  we could also  quot save quot  the current element we re working on with an Iterator  With the help of the Iterator  we get an 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

ArrayList extends AbstractList and implements the List Interface  ArrayList is dynamic array It can be said that it was basically created to overcome the drawbacks of arrays The LinkedList class extends AbstractSequentialList and implements List Deque  and Queue interface  Performance arraylist get   is  O 1  whereas linkedlist get   is O n   arraylist add   is  O 1  and linkedlist add   is 0 1  arraylist contains   is O n  andlinkedlist contains   is O n   arraylist next   is O 1  and linkedlist next   is O 1  arraylist remove   is O n  whereas linkedlist remove   is O 1  In arraylistiterator remove   is O n  whereas In linkedlist iterator remove  is O 1

User · Answer

It depends upon what operations you will be doing more on the List   ArrayList is faster to access an indexed value  It is much worse when inserting or deleting objects   To find out more  read any article that talks about the difference between arrays and linked lists

User · Answer

ArrayList is randomly accessible  while LinkedList is really cheap to expand and remove elements from  For most cases  ArrayList is fine   Unless you ve created large lists and measured a bottleneck  you ll probably never need to worry about the difference

User · Answer

As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade  I would prefer the behavior of LinkedList over ArrayList   While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware -- the behavior of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage  while under pressure  which is catastrophic behavior   Similarly  you can get better throughput in an app from the default throughput tenured garbage collector  but once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows your SLAs if it occurs too often   Even though the CMS collector takes more resources and does not achieve the same raw throughput  it is a much better choice because it has more predictable and smaller latency   ArrayList is only a better choice for performance if all you mean by performance is throughput and you can ignore latency   In my experience at my job I cannot ignore worst-case latency

User · Answer

If your code has add 0  and remove 0   use a LinkedList and it s prettier addFirst   and removeFirst   methods  Otherwise  use ArrayList   And of course  Guava s ImmutableList is your best friend

User · Answer

1  Underlying Data Structure The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList  This will lead to further differences in performance  2  LinkedList implements Deque Another difference between ArrayList and LinkedList is that apart from the List interface  LinkedList also implements Deque interface  which provides first in first out operations for add   and poll   and several other Deque functions  3  Adding elements in ArrayList Adding element in ArrayList is O 1  operation if it doesn t trigger re-size of Array  in which case it becomes O log n    On the other hand  appending an element in LinkedList is O 1  operation  as it doesn t require any navigation  4  Removing an element from a position In order to remove an element from a particular index e g  by calling remove index   ArrayList performs a copy operation which makes it close to O n  while LinkedList needs to traverse to that point which also makes it O n 2   as it can traverse from either direction based upon proximity  5  Iterating over ArrayList or LinkedList Iteration is the O n  operation for both LinkedList and ArrayList where n is a number of an element  6  Retrieving element from a position The get index  operation is O 1  in ArrayList while its O n 2  in LinkedList  as it needs to traverse till that entry  Though  in Big O notation O n 2  is just O n  because we ignore constants there  7  Memory LinkedList uses a wrapper object  Entry  which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array  So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another  If Array is large enough it may take a lot of memory at that point and trigger Garbage collection  which can slow response time  From all the above differences between ArrayList vs LinkedList  It looks ArrayList is the better choice than LinkedList in almost all cases  except when you do a frequent add   operation than remove    or get    It s easier to modify a linked list than ArrayList  especially if you are adding or removing elements from start or end because linked list internally keeps references of those positions and they are accessible in O 1  time  In other words  you don t need to traverse through the linked list to reach the position where you want to add elements  in that case  addition becomes O n  operation  For example  inserting or deleting an element in the middle of a linked list  In my opinion  use ArrayList over LinkedList for most of the practical purpose in Java

User · Answer

Operation get i  in ArrayList is faster than LinkedList  because  ArrayList  Resizable-array implementation of the List interface LinkedList  Doubly-linked list implementation of the List and Deque interfaces  Operations that index into the list will traverse the list from the beginning or the end  whichever is closer to the specified index

User · Answer

Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList  If you re not sure      just start with ArrayList   TLDR  in ArrayList accessing an element takes constant time  O 1   and adding an element takes O n  time  worst case   In LinkedList adding an element takes O n  time and accessing also takes O n  time but LinkedList uses more memory than ArrayList  LinkedList and ArrayList are two different implementations of the List interface  LinkedList implements it with a doubly-linked list  ArrayList implements it with a dynamically re-sizing array  As with standard linked list and array operations  the various methods will have different algorithmic runtimes  For LinkedList lt E gt   get int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use getFirst   and getLast     One of the main benefits of LinkedList lt E gt  add int index  E element  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use addFirst   and addLast   add     One of the main benefits of LinkedList lt E gt  remove int index  is O n   with n 4 steps on average   but O 1  when index   0 or index   list size   - 1  in this case  you can also use removeFirst   and removeLast     One of the main benefits of LinkedList lt E gt  Iterator remove   is O 1   One of the main benefits of LinkedList lt E gt  ListIterator add E element  is O 1   One of the main benefits of LinkedList lt E gt   Note  Many of the operations need n 4 steps on average  constant number of steps in the best case  e g  index   0   and n 2 steps in worst case  middle of list  For ArrayList lt E gt   get int index  is O 1   Main benefit of ArrayList lt E gt  add E element  is O 1  amortized  but O n  worst-case since the array must be resized and copied add int index  E element  is O n   with n 2 steps on average  remove int index  is O n   with n 2 steps on average  Iterator remove   is O n   with n 2 steps on average  ListIterator add E element  is O n   with n 2 steps on average   Note  Many of the operations need n 2 steps on average  constant number of steps in the best case  end of list   n steps in the worst case  start of list  LinkedList lt E gt  allows for constant-time insertions or removals using iterators  but only sequential access of elements  In other words  you can walk the list forwards or backwards  but finding a position in the list takes time proportional to the size of the list  Javadoc says  quot operations that index into the list will traverse the list from the beginning or the end  whichever is closer quot   so those methods are O n   n 4 steps  on average  though O 1  for index   0  ArrayList lt E gt   on the other hand  allow fast random read access  so you can grab any element in constant time  But adding or removing from anywhere but the end requires shifting all the latter elements over  either to make an opening or fill the gap  Also  if you add more elements than the capacity of the underlying array  a new array  1 5 times the size  is allocated  and the old array is copied to the new one  so adding to an ArrayList is O n  in the worst case but constant on average  So depending on the operations you intend to do  you should choose the implementations accordingly  Iterating over either kind of List is practically equally cheap   Iterating over an ArrayList is technically faster  but unless you re doing something really performance-sensitive  you shouldn t worry about this -- they re both constants   The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements  These operations can then be done in O 1  by changing the list locally only  In an array list  the remainder of the array needs to be moved  i e  copied   On the other side  seeking in a LinkedList means following the links in O n   n 2 steps  for worst case  whereas in an ArrayList the desired position can be computed mathematically and accessed in O 1   Another benefit of using a LinkedList arise when you add or remove from the head of the list  since those operations are O 1   while they are O n  for ArrayList  Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head  but it is not a List  Also  if you have large lists  keep in mind that memory usage is also different  Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored  ArrayLists don t have this overhead  However  ArrayLists take up as much memory as is allocated for the capacity  regardless of whether elements have actually been added  The default initial capacity of an ArrayList is pretty small  10 from Java 1 4 - 1 8   But since the underlying implementation is an array  the array must be resized if you add a lot of elements  To avoid the high cost of resizing when you know you re going to add a lot of elements  construct the ArrayList with a higher initial capacity  If the data structures perspective is used to understand the two structures  a LinkedList is basically a sequential data structure which contains a head Node  The Node is a wrapper for two components   a value of type T  accepted through generics  and another reference to the Node linked to it  So  we can assert it is a recursive data structure  a Node contains another Node which has another Node and so on      Addition of elements takes linear time in LinkedList as stated above  An ArrayList  is a growable array  It is just like a regular array  Under the hood  when an element is added at index i  it creates another array with a size which is 1 greater than previous size  So in general  when n elements are to be added to an ArrayList  a new array of size previous size plus n is created   The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices

User · Answer

It s an efficiency question  LinkedList is fast for adding and deleting elements  but slow to access a specific element  ArrayList is fast for accessing a specific element but can be slow to add to either end  and especially slow to delete in the middle   Array vs ArrayList vs LinkedList vs Vector goes more in depth  as does  Linked List

User · Answer

ArrayList is randomly accessible  while LinkedList is really cheap to expand and remove elements from  For most cases  ArrayList is fine   Unless you ve created large lists and measured a bottleneck  you ll probably never need to worry about the difference

User · Answer

When should I use LinkedList  When working with stacks mostly  or when working with buffers  When should I use ArrayList  Only when working with indexes   otherwise you can use HashTable with linked list  then you get   Hash table   linked list   Access by key O 1   Insert by key O 1   Remove by key O 1  and there is a trick to implement RemoveAll   SetAll with O 1  when using versioning   It seems like a good solution  and in most of the cases it is  how ever you should know  HashTable takes a lot of disc space  so when you need to manage 1 000 000 elements list it can become a thing that matters  This can happen in server implementations  in clients it is rarely the case   Also take a look at Red-Black-Tree   Random access Log n   Insert Log n   Remove Log n

User · Answer

Let s compare LinkedList and ArrayList w r t  below parameters   1  Implementation     ArrayList is the resizable array implementation of list interface   while       LinkedList is the Doubly-linked list implementation of the list interface      2  Performance   get int index  or search operation     ArrayList get int index  operation runs in constant time i e O 1   while       LinkedList get int index  operation run time is O n      The reason behind ArrayList being faster than LinkedList is that ArrayList uses an index based system for its elements as it internally uses an array data structure  on the other hand   LinkedList does not provide index-based access for its elements as it iterates either from the beginning or end  whichever is closer  to retrieve the node at the specified element index  insert   or add Object  operation     Insertions in LinkedList are generally fast as compare to ArrayList  In LinkedList adding or insertion is O 1  operation         While in ArrayList  if the array is the full i e worst case   there is an extra cost of resizing array and copying elements to the new array  which makes runtime of add operation in ArrayList O n   otherwise it is O 1    remove int  operation  Remove operation in LinkedList is generally the same as ArrayList i e  O n       In LinkedList  there are two overloaded remove methods  one is remove   without any parameter which removes the head of the list and runs in constant time O 1   The other overloaded remove method in LinkedList is remove int  or remove Object  which removes the Object or int passed as a parameter  This method traverses the LinkedList until it found the Object and unlink it from the original list  Hence this method runtime is O n         While in ArrayList remove int  method involves copying elements from the old array to new updated array  hence its runtime is O n        3  Reverse  Iterator     LinkedList can be iterated in reverse direction using descendingIterator   while       there is no descendingIterator   in ArrayList   so we need to write our own code to iterate over the ArrayList in reverse direction      4  Initial Capacity     If the constructor  is not overloaded  then ArrayList creates an empty list of initial capacity 10  while       LinkedList  only constructs the empty list without any initial capacity      5  Memory Overhead     Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node  While       In ArrayList  each index only holds the actual object data       Source

User · Answer

First of all use Vector instead ArrayList because you can overrite insureCapasity method   in ArrayList is private and add 1 5 size of current array https   docs oracle com javase 8 docs api java util Vector html ensureCapacity-int-  in many case it can be better that linkedList  the las has big advantage one you insert data with high freqency so size of you list changes very fast and you can t allocate size for number elements   In the theory you can get error like not  enough memory   but  in modern computers you have 16G and swaping disk  so if you list is billoins elements you can fail  comparing 15-20 years ago

User · Answer

An important feature of a linked list  which I didn t read in another answer  is the concatenation of two lists  With an array this is O n     overhead of some reallocations  with a linked list this is only O 1  or O 2   -   Important  For Java its LinkedList this is not true  See Is there a fast concat method for linked list in Java

User · Answer

An important feature of a linked list  which I didn t read in another answer  is the concatenation of two lists  With an array this is O n     overhead of some reallocations  with a linked list this is only O 1  or O 2   -   Important  For Java its LinkedList this is not true  See Is there a fast concat method for linked list in Java

User · Answer

My rule of thumb is if I need a Collection  i e  doesn t need to be a List  then use ArrayList if you know the size in advance  or can know the size confidently  or know that it won t vary much  If you need random access  i e  you use get index   then avoid LinkedList  Basically  use LinkedList only if you don t need index access and don t know the  approximate  size of the collection you re allocating  Also if you re going to be making lots of additions and removals  again through the Collection interface  then LinkedList may be preferable

User · Answer

One of the tests I saw on here only conducts the test once   But what I have noticed is that you need to run these tests many times and eventually their times will converge   Basically the JVM needs to warm up   For my particular use case I needed to add remove items to a list that grows to about 500 items   In my tests LinkedList came out faster  with LinkedList coming in around 50 000 NS and ArrayList coming in at around 90 000 NS    give or take   See the code below   public static void main String   args        List lt Long gt  times   new ArrayList lt  gt         for  int i   0  i  lt  100  i              times add doIt               System out println  avg        times stream   mapToLong x - gt  x  average         static long doIt         long start   System nanoTime        List lt Object gt  list   new LinkedList lt  gt           uncomment line below to test with ArrayList       list   new ArrayList lt  gt         for  int i   0  i  lt  500  i              list add i              Iterator it   list iterator        while  it hasNext              it next            it remove              long end   System nanoTime        long diff   end - start        uncomment to see the JVM warmup and get faster for the first few iterations       System out println diff      return diff

User · Answer

Joshua Bloch  the author of LinkedList      Does anyone actually use LinkedList   I wrote it  and I never use it    Link  https   twitter com joshbloch status 583813919019573248  I m sorry for the answer for being not that informative as the other answers  but I thought it would be the most interesting and self-explanatory

User · Answer

TL DR due to modern computer architecture  ArrayList will be significantly more efficient for nearly any possible use-case - and therefore LinkedList should be avoided except some very unique and extreme cases     In theory  LinkedList has an O 1  for the add E element   Also adding an element in the mid of a list should be very efficient   Practice is very different  as LinkedList is a Cache Hostile Data structure  From performance POV - there are very little cases where LinkedList could be better performing than the Cache-friendly ArrayList   Here are results of a benchmark testing inserting elements in random locations  As you can see - the array list if much more efficient  although in theory each insert in the middle of the list will require  move  the n later elements of the array  lower values are better      Working on a later generation hardware  bigger  more efficient caches  - the results are even more conclusive     LinkedList takes much more time to accomplish the same job  source Source Code  There are two main reasons for this    Mainly - that the nodes of the LinkedList are scattered randomly across the memory  RAM   Random Access Memory   isn t really random and blocks of memory need to be fetched to cache  This operation takes time  and when such fetches happen frequently - the memory pages in the cache need to be replaced all the time -  Cache misses -  Cache is not efficient  ArrayList elements are stored on continuous memory - which is exactly what the modern CPU architecture is optimizing for  Secondary LinkedList required to hold back forward pointers  which means 3 times the memory consumption per value stored compared to ArrayList    DynamicIntArray  btw  is a custom ArrayList implementation holding Int  primitive type  and not Objects - hence all data is really stored adjacently - hence even more efficient   A key elements to remember is that the cost of fetching memory block  is more significant than the cost accessing a single memory cell  That s why reader 1MB of sequential memory is up to x400 times faster than reading this amount of data from different blocks of memory   Latency Comparison Numbers   2012  ---------------------------------- L1 cache reference                           0 5 ns Branch mispredict                            5   ns L2 cache reference                           7   ns                      14x L1 cache Mutex lock unlock                           25   ns Main memory reference                      100   ns                      20x L2 cache  200x L1 cache Compress 1K bytes with Zippy             3 000   ns        3 us Send 1K bytes over 1 Gbps network       10 000   ns       10 us Read 4K randomly from SSD              150 000   ns      150 us           1GB sec SSD Read 1 MB sequentially from memory     250 000   ns      250 us Round trip within same datacenter      500 000   ns      500 us Read 1 MB sequentially from SSD      1 000 000   ns    1 000 us    1 ms   1GB sec SSD  4X memory Disk seek                           10 000 000   ns   10 000 us   10 ms  20x datacenter roundtrip Read 1 MB sequentially from disk    20 000 000   ns   20 000 us   20 ms  80x memory  20X SSD Send packet CA- gt Netherlands- gt CA    150 000 000   ns  150 000 us  150 ms   Source  Latency Numbers Every Programmer Should Know  Just to make the point even clearer  please check the benchmark of adding elements to the beginning of the list  This is a use-case where  in-theory  the LinkedList should really shine  and ArrayList should present poor or even worse-case results     Note  this is a benchmark of the C   Std lib  but my previous experience shown the C   and Java results are very similar  Source Code  Copying a sequential bulk of memory is an operation optimized by the modern CPUs - changing theory and actually making  again  ArrayList Vector much more efficient    Credits  All benchmarks posted here are created by Kjell Hedstr  m  Even more data can be found on his blog

User · Answer

I usually use one over the other based on the time complexities of the operations that I d perform on that particular List                                                                      --------------------- --------------------- -------------------- ------------         Operation            ArrayList             LinkedList         Winner      --------------------- --------------------- -------------------- ------------        get index               O 1                     O n          ArrayList                                                   n 4 steps in avg                  --------------------- --------------------- -------------------- ------------         add E                  O 1                     O 1          LinkedList                          --------------------- --------------------                                       O n  in worst case                                       --------------------- --------------------- -------------------- ------------       add index  E             O n                     O n          LinkedList                               n 2 steps              n 4 steps                                           --------------------- --------------------                                                              O 1  if index   0                 --------------------- --------------------- -------------------- ------------     remove index  E            O n                     O n          LinkedList                          --------------------- --------------------                                           n 2 steps              n 4 steps                     --------------------- --------------------- -------------------- ------------     Iterator remove            O n                     O 1          LinkedList      ListIterator add                                                              --------------------- --------------------- -------------------- ------------     -------------------------------------- -----------------------------------                 ArrayList                            LinkedList                -------------------------------------- -----------------------------------        Allows fast read access              Retrieving element takes O n       -------------------------------------- -----------------------------------      Adding an element require shifting   o 1   but traversing takes time             all the later elements                                                -------------------------------------- -----------------------------------      To add more elements than capacity        new array need to be allocated       --------------------------------------

User · Answer

When should I use LinkedList  When working with stacks mostly  or when working with buffers  When should I use ArrayList  Only when working with indexes   otherwise you can use HashTable with linked list  then you get   Hash table   linked list   Access by key O 1   Insert by key O 1   Remove by key O 1  and there is a trick to implement RemoveAll   SetAll with O 1  when using versioning   It seems like a good solution  and in most of the cases it is  how ever you should know  HashTable takes a lot of disc space  so when you need to manage 1 000 000 elements list it can become a thing that matters  This can happen in server implementations  in clients it is rarely the case   Also take a look at Red-Black-Tree   Random access Log n   Insert Log n   Remove Log n

User · Answer

Thus far  nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList is  lots more  than an ArrayList so I did some number crunching to demonstrate exactly how much both lists take up for N null references   Since references are either 32 or 64 bits  even when null  on their relative systems  I have included 4 sets of data for 32 and 64 bit LinkedLists and ArrayLists   Note  The sizes shown for the ArrayList lines are for trimmed lists - In practice  the capacity of the backing array in an ArrayList is generally larger than its current element count   Note 2   thanks BeeOnRope  As CompressedOops is default now from mid JDK6 and up  the values below for 64-bit machines will basically match their 32-bit counterparts  unless of course you specifically turn it off         The result clearly shows that LinkedList is a whole lot more than ArrayList  especially with a very high element count  If memory is a factor  steer clear of LinkedLists   The formulas I used follow  let me know if I have done anything wrong and I will fix it up   b  is either 4 or 8 for 32 or 64 bit systems  and  n  is the number of elements  Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not   ArrayList   ArrayList object header   size integer   modCount integer   array reference    array oject header   b   n    MOD array oject  8    MOD ArrayList object  8     8   4   4   b    12   b   n    MOD 12   b   n  8    MOD 8   4   4   b    12   b   n    MOD 12   b   n  8   8   LinkedList   LinkedList object header   size integer   modCount integer   reference to header   reference to footer    node object overhead   reference to previous element   reference to next element   reference to element    n    MOD node object  8    n   MOD LinkedList object  8     8   4   4   2   b    8   3   b    n   MOD 8   3   b  8    n   MOD 8   4   4   2   b    8   3   b    n   MOD 8   3   b  8    n  8

User · Answer

I usually use one over the other based on the time complexities of the operations that I d perform on that particular List                                                                      --------------------- --------------------- -------------------- ------------         Operation            ArrayList             LinkedList         Winner      --------------------- --------------------- -------------------- ------------        get index               O 1                     O n          ArrayList                                                   n 4 steps in avg                  --------------------- --------------------- -------------------- ------------         add E                  O 1                     O 1          LinkedList                          --------------------- --------------------                                       O n  in worst case                                       --------------------- --------------------- -------------------- ------------       add index  E             O n                     O n          LinkedList                               n 2 steps              n 4 steps                                           --------------------- --------------------                                                              O 1  if index   0                 --------------------- --------------------- -------------------- ------------     remove index  E            O n                     O n          LinkedList                          --------------------- --------------------                                           n 2 steps              n 4 steps                     --------------------- --------------------- -------------------- ------------     Iterator remove            O n                     O 1          LinkedList      ListIterator add                                                              --------------------- --------------------- -------------------- ------------     -------------------------------------- -----------------------------------                 ArrayList                            LinkedList                -------------------------------------- -----------------------------------        Allows fast read access              Retrieving element takes O n       -------------------------------------- -----------------------------------      Adding an element require shifting   o 1   but traversing takes time             all the later elements                                                -------------------------------------- -----------------------------------      To add more elements than capacity        new array need to be allocated       --------------------------------------

User · Answer

I know this is an old post  but I honestly can t believe nobody mentioned that LinkedList implements Deque   Just look at the methods in Deque  and Queue   if you want a fair comparison  try running LinkedList against ArrayDeque and do a feature-for-feature comparison

User · Answer

ArrayList is what you want  LinkedList is almost always a  performance  bug  Why LinkedList sucks   It uses lots of small memory objects  and therefore impacts performance across the process  Lots of small objects are bad for cache-locality  Any indexed operation requires a traversal  i e  has O n  performance  This is not obvious in the source code  leading to algorithms O n  slower than if ArrayList was used  Getting good performance is tricky  Even when big-O performance is the same as ArrayList  it is probably going to be significantly slower anyway  It s jarring to see LinkedList in source because it is probably the wrong choice

User · Answer

ArrayList is essentially an array  LinkedList is implemented as a double linked list    The get is pretty clear  O 1  for ArrayList  because ArrayList allow random access by using index  O n  for LinkedList  because it needs to find the index first  Note  there are different versions of add and remove    LinkedList is faster in add and remove  but slower in get  In brief  LinkedList should be preferred if     there are no large number of random access of element  there are a large number of add remove operations       ArrayList       add E e          add at the end of ArrayList require memory resizing cost    O n  worst  O 1  amortized  add int index  E element     add to a specific index position require shifting  amp  possible memory resizing cost O n   remove int index    remove a specified element require shifting  amp  possible memory resizing cost O n   remove Object o     remove the first occurrence of the specified element from this list need to search the element first  and then shifting  amp  possible memory resizing cost O n         LinkedList       add E e    add to the end of the list O 1   add int index  E element    insert at specified position need to find the position first O n   remove     remove first element of the list O 1   remove int index    remove element with specified index need to find the element first O n   remove Object o    remove the first occurrence of the specified element need to find the element first O n     Here is a figure from programcreek com  add and remove are the first type  i e   add an element at the end of the list and remove the element at the specified position in the list

User · Answer

ArrayList is randomly accessible  while LinkedList is really cheap to expand and remove elements from  For most cases  ArrayList is fine   Unless you ve created large lists and measured a bottleneck  you ll probably never need to worry about the difference

User · Answer

It s an efficiency question  LinkedList is fast for adding and deleting elements  but slow to access a specific element  ArrayList is fast for accessing a specific element but can be slow to add to either end  and especially slow to delete in the middle   Array vs ArrayList vs LinkedList vs Vector goes more in depth  as does  Linked List

User · Answer

If your code has add 0  and remove 0   use a LinkedList and it s prettier addFirst   and removeFirst   methods  Otherwise  use ArrayList   And of course  Guava s ImmutableList is your best friend

User · Answer

Let s compare LinkedList and ArrayList w r t  below parameters   1  Implementation     ArrayList is the resizable array implementation of list interface   while       LinkedList is the Doubly-linked list implementation of the list interface      2  Performance   get int index  or search operation     ArrayList get int index  operation runs in constant time i e O 1   while       LinkedList get int index  operation run time is O n      The reason behind ArrayList being faster than LinkedList is that ArrayList uses an index based system for its elements as it internally uses an array data structure  on the other hand   LinkedList does not provide index-based access for its elements as it iterates either from the beginning or end  whichever is closer  to retrieve the node at the specified element index  insert   or add Object  operation     Insertions in LinkedList are generally fast as compare to ArrayList  In LinkedList adding or insertion is O 1  operation         While in ArrayList  if the array is the full i e worst case   there is an extra cost of resizing array and copying elements to the new array  which makes runtime of add operation in ArrayList O n   otherwise it is O 1    remove int  operation  Remove operation in LinkedList is generally the same as ArrayList i e  O n       In LinkedList  there are two overloaded remove methods  one is remove   without any parameter which removes the head of the list and runs in constant time O 1   The other overloaded remove method in LinkedList is remove int  or remove Object  which removes the Object or int passed as a parameter  This method traverses the LinkedList until it found the Object and unlink it from the original list  Hence this method runtime is O n         While in ArrayList remove int  method involves copying elements from the old array to new updated array  hence its runtime is O n        3  Reverse  Iterator     LinkedList can be iterated in reverse direction using descendingIterator   while       there is no descendingIterator   in ArrayList   so we need to write our own code to iterate over the ArrayList in reverse direction      4  Initial Capacity     If the constructor  is not overloaded  then ArrayList creates an empty list of initial capacity 10  while       LinkedList  only constructs the empty list without any initial capacity      5  Memory Overhead     Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node  While       In ArrayList  each index only holds the actual object data       Source

User · Answer

ArrayList and LinkedList have their own pros and cons   ArrayList uses contiguous memory address compared to LinkedList which uses pointers toward the next node  So when you want to look up an element in an ArrayList is faster than doing n iterations with LinkedList   On the other hand  insertion and deletion in a LinkedList are much easier because you just have to change the pointers whereas an ArrayList implies the use of shift operation for any insertion or deletion   If you have frequent retrieval operations in your app use an ArrayList  If you have frequent insertion and deletion use a LinkedList

User · Answer

Joshua Bloch  the author of LinkedList      Does anyone actually use LinkedList   I wrote it  and I never use it    Link  https   twitter com joshbloch status 583813919019573248  I m sorry for the answer for being not that informative as the other answers  but I thought it would be the most interesting and self-explanatory

User · Answer

ArrayList and LinkedList both implements List interface  and their methods and results are almost identical  However there are few differences between them which make one better over another depending on the requirement   ArrayList Vs LinkedList  1  Search  ArrayList search operation is pretty fast compared to the LinkedList search operation  get int index  in ArrayList gives the performance of O 1  while LinkedList performance is O n    Reason  ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list  On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element   2  Deletion  LinkedList remove operation gives O 1  performance while ArrayList gives variable performance  O n  in worst case  while removing first element  and O 1  in best case  While removing last element       Conclusion  LinkedList element deletion is faster compared to   ArrayList    Reason  LinkedList   s each element maintains two pointers  addresses  which points to the both neighbor elements in the list  Hence removal only requires change in the pointer location in the two neighbor nodes  elements  of the node which is going to be removed  While In ArrayList all the elements need to be shifted to fill out the space created by removed element   3  Inserts Performance  LinkedList add method gives O 1  performance while ArrayList gives O n  in worst case  Reason is same as explained for remove   4  Memory Overhead  ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes      hence the memory consumption is high in LinkedList comparatively    There are few similarities between these classes which are as follows    Both ArrayList and LinkedList are implementation of List interface  They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List  Both these classes are non-synchronized and can be made synchronized explicitly by using Collections synchronizedList method  The iterator and listIterator returned by these classes are fail-fast  if list is structurally modified at any time after the iterator is created  in any way except through the iterator   s own remove or add methods  the iterator will throw a ConcurrentModificationException     When to use LinkedList and when to use ArrayList    As explained above the insert and remove operations give good performance  O 1   in LinkedList compared to ArrayList O n        Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice   Search  get method  operations are fast in Arraylist  O 1   but not in LinkedList  O n        so If there are less add and remove operations and more search operations requirement  ArrayList would be your best bet

User · Answer

ArrayList is what you want  LinkedList is almost always a  performance  bug  Why LinkedList sucks   It uses lots of small memory objects  and therefore impacts performance across the process  Lots of small objects are bad for cache-locality  Any indexed operation requires a traversal  i e  has O n  performance  This is not obvious in the source code  leading to algorithms O n  slower than if ArrayList was used  Getting good performance is tricky  Even when big-O performance is the same as ArrayList  it is probably going to be significantly slower anyway  It s jarring to see LinkedList in source because it is probably the wrong choice

User · Answer

If your code has add 0  and remove 0   use a LinkedList and it s prettier addFirst   and removeFirst   methods  Otherwise  use ArrayList   And of course  Guava s ImmutableList is your best friend

User · Answer

I have read the responses  but there is one scenario where I always use a LinkedList over an ArrayList that I want to share to hear opinions   Every time I had a method that returns a list of data obtained from a DB I always use a LinkedList   My rationale was that because it is impossible to know exactly how many results am I getting  there will be not memory wasted  as in ArrayList with the difference between the capacity and actual number of elements   and there would be no time wasted trying to duplicate the capacity   As far a ArrayList  I agree that at least you should always use the constructor with the initial capacity  to minimize the duplication of the arrays as much as possible

User · Answer

ArrayList is essentially an array  LinkedList is implemented as a double linked list    The get is pretty clear  O 1  for ArrayList  because ArrayList allow random access by using index  O n  for LinkedList  because it needs to find the index first  Note  there are different versions of add and remove    LinkedList is faster in add and remove  but slower in get  In brief  LinkedList should be preferred if     there are no large number of random access of element  there are a large number of add remove operations       ArrayList       add E e          add at the end of ArrayList require memory resizing cost    O n  worst  O 1  amortized  add int index  E element     add to a specific index position require shifting  amp  possible memory resizing cost O n   remove int index    remove a specified element require shifting  amp  possible memory resizing cost O n   remove Object o     remove the first occurrence of the specified element from this list need to search the element first  and then shifting  amp  possible memory resizing cost O n         LinkedList       add E e    add to the end of the list O 1   add int index  E element    insert at specified position need to find the position first O n   remove     remove first element of the list O 1   remove int index    remove element with specified index need to find the element first O n   remove Object o    remove the first occurrence of the specified element need to find the element first O n     Here is a figure from programcreek com  add and remove are the first type  i e   add an element at the end of the list and remove the element at the specified position in the list

[java] When to use LinkedList over ArrayList in Java?

Examples related to java

Examples related to arraylist

Examples related to collections

Examples related to linked-list