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 inserting 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<E>
get(int index)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also usegetFirst()andgetLast()).add(int index, E element)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also useaddFirst()andaddLast()/add()). One of the main benefits ofLinkedList<E>remove(int index)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also useremoveFirst()andremoveLast()). One of the main benefits ofLinkedList<E>Iterator.remove()is O(1). One of the main benefits ofLinkedList<E>ListIterator.add(E element)is O(1). One of the main benefits ofLinkedList<E>
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<E>
get(int index)is O(1). Main benefit ofArrayList<E>add(E element)is O(1) amortized, but O(n) worst-case since the array must be resized and copiedadd(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<E> 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 "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.
ArrayList<E>, 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 arises 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, and the ArrayList is already full to capacity, it creates another array with a size which is greater than previous size. 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.
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 inserting 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<E>
get(int index)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also usegetFirst()andgetLast()).add(int index, E element)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also useaddFirst()andaddLast()/add()). One of the main benefits ofLinkedList<E>remove(int index)is O(n) (with n/4 steps on average), but O(1) whenindex = 0orindex = list.size() - 1(in this case, you can also useremoveFirst()andremoveLast()). One of the main benefits ofLinkedList<E>Iterator.remove()is O(1). One of the main benefits ofLinkedList<E>ListIterator.add(E element)is O(1). One of the main benefits ofLinkedList<E>
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<E>
get(int index)is O(1). Main benefit ofArrayList<E>add(E element)is O(1) amortized, but O(n) worst-case since the array must be resized and copiedadd(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<E> 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 "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.
ArrayList<E>, 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 arises 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, and the ArrayList is already full to capacity, it creates another array with a size which is greater than previous size. 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.
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)
java - Performance differences between ArrayList and LinkedList - Stack Overflow
ArrayList has faster insert speed than LinkedList
Choosing between ArrayList and LinkedList - JEP Cafe #20
ArrayList vs LinkedList
My task needs to frequently insert element to a collection. LinkedList should be a good option, so I decided to test it against ArrayList, using the following snipper of code (it's Kotlin but it's still use java's ArrayList and LinkedList).
@Test
fun test1() {
val elementsCount = 9999999
val linkedListTime = measureNanoTime {
val list = LinkedList<Int>()
for (i in 0 until elementsCount) {
list.add(1)
}
}
val arrayListTime = measureNanoTime {
val list = ArrayList<Int>()
for (i in 0 until elementsCount) {
list.add(1)
}
}
println("Linked list time:")
println(linkedListTime)
println("Array list time:")
println(arrayListTime)
}The result is that ArrayList has much lower insert time compared to LinkedList
Linked list time: 683270459 Array list time: 223203092
From what I read from online explanation, LinkedList's slower speed has something to do with memory allocation for each element inserted.
ArrayList outperform LinkedList at insertion, which is the only thing that LinkedList is better at. What is LinkedList good for ? What is the use case of LinkedList?
ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?
ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.
LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.
ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.
If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.
Yes, this is what it means. ArrayList is indeed slower than LinkedList because it has to free up a slot in the middle of the array. This involves moving some references around and in the worst case reallocating the entire array. LinkedList just has to manipulate some references.
Ignore this answer for now. The other answers, particularly that of aix, are mostly correct. Over the long term they're the way to bet. And if you have enough data (on one benchmark on one machine, it seemed to be about one million entries) ArrayList and LinkedList do currently work as advertized. However, there are some fine points that apply in the early 21st century.
Modern computer technology seems, by my testing, to give an enormous edge to arrays. Elements of an array can be shifted and copied at insane speeds. As a result arrays and ArrayList will, in most practical situations, outperform LinkedList on inserts and deletes, often dramatically. In other words, ArrayList will beat LinkedList at its own game.
The downside of ArrayList is it tends to hang onto memory space after deletions, where LinkedList gives up space as it gives up entries.
The bigger downside of arrays and ArrayList is they fragment free memory and overwork the garbage collector. As an ArrayList expands, it creates new, bigger arrays, copies the old array to the new one, and frees the old one. Memory fills with big contiguous chunks of free memory that are not big enough for the next allocation. Eventually there's no suitable space for that allocation. Even though 90% of memory is free, no individual piece is big enough to do the job. The GC will work frantically to move things around, but if it takes too long to rearrange the space, it will throw an OutOfMemoryException. If it doesn't give up, it can still slow your program way down.
The worst of it is this problem can be hard to predict. Your program will run fine one time. Then, with a bit less memory available, with no warning, it slows or stops.
LinkedList uses small, dainty bits of memory and GC's love it. It still runs fine when you're using 99% of your available memory.
So in general, use ArrayList for smaller sets of data that are not likely to have most of their contents deleted, or when you have tight control over creation and growth. (For instance, creating one ArrayList that uses 90% of memory and using it without filling it for the duration of the program is fine. Continually creating and freeing ArrayList instances that use 10% of memory will kill you.) Otherwise, go with LinkedList (or a Map of some sort if you need random access). If you have very large collections (say over 100,000 elements), no concerns about the GC, and plan lots of inserts and deletes and no random access, run a few benchmarks to see what's fastest.
