When to use LinkedList over ArrayList in Java?
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 = 0
orindex = list.size() - 1
(in this case, you can also usegetFirst()
andgetLast()
). One of the main benefits ofLinkedList<E>
add(int index, E element)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = 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 = 0
orindex = 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.
Why does ArrayList seriously outperform LinkedList?
From LinkedList source code:
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
From ArrayList source code:
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
So linked list has to create new node for each element added, while array list does not. ArrayList does not reallocate/resize for each new element, so most of time array list simply set object in array and increment size, while linked list does much more work.
You also commented:
When I wrote a linked list in college, I allocated blocks at a time and then farmed them out.
I do not think this would work in Java. You cannot do pointer tricks in Java, so you would have to allocate a lot of small arrays, or create empty nodes ahead. In both cases overhead would probably be a bit higher.
Performance differences between ArrayList and 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.
ArrayList vs LinkedList when inserting items at random indices?
Your expectations were incorrect. The ArrayList
Javadoc explicitly says (in part)1
The
add
operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for theLinkedList
implementation.
Because the constant factor is higher each add
operation on a LinkedList
is slightly slower than on ArrayList
, so you should have expected ArrayList
to be faster.
1 Added bold for emphasis.
ArrayList vs LinkedList from memory allocation perspective
LinkedList
might allocate fewer entries, but those entries are astronomically more expensive than they'd be for ArrayList
-- enough that even the worst-case ArrayList
is cheaper as far as memory is concerned.
(FYI, I think you've got it wrong; ArrayList
grows by 1.5x when it's full, not 2x.)
See e.g. https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList
consumes 24 bytes per element, while ArrayList
consumes in the best case 4 bytes per element, and in the worst case 6 bytes per element. (Results may vary depending on 32-bit versus 64-bit JVMs, and compressed object pointer options, but in those comparisons LinkedList
costs at least 36 bytes/element, and ArrayList
is at best 8 and at worst 12.)
UPDATE:
I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.
To be clear, even in the worst case, ArrayList
is 4x smaller than a LinkedList
with the same elements. The only possible way to make LinkedList
win is to deliberately fix the comparison by calling ensureCapacity
with a deliberately inflated value, or to remove lots of values from the ArrayList
after they've been added.
In short, it's basically impossible to make LinkedList
win the memory comparison, and if you care about space, then calling trimToSize()
on the ArrayList
will instantly make ArrayList
win again by a huge margin. Seriously. ArrayList
wins.
When to use ArrayList, LinkedList, and Stack in Java?
As ArrayList and LinkedList both implement List interface. They are very similar to use. Their main difference is their implementation which causes different performance for different operations. ArrayList is implemented as a resizable array. As more elements are added to ArrayList, its size is increased dynamically. It's elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array. LinkedList is implemented as a double linked list. Its performance on add and remove is better than ArrayList, but worse on get and set methods. So basically when you working with data that needs to be frequently added or removed from the list you would like to go for the LinkedList.
Difference between arraylist and linkedList
When should i use arrayList and when should I go for LinkedList?
Arraylist maintain indices like arrays. So if want more frequent get operations than put then arraylist is best to go.
LinkedList maintain pointers to elements. you can't to a specific index like in arraylist. But the advantage here in linkedlist is that they don't need to shift back and forth like in arraylist to maintain continues indices. So get operations in linkedlist are costly as you would have to go through pointers to reach your elements. But put operations are good as compared to arraylist. you just need to connect to pointers and that's it.
When should I use TreeSet, LinkedHashSet and HashSet?
the difference is only in ordering. treeset elements need to maintain a specific orders defined by your member objects.
ArrayList vs LinkedList Java
ArrayList
is a list implementation that's backed by an Object[]
. It supports random access and dynamic resizing.
LinkedList
is a list implementation that uses references to head and tail to navigate it. It has no random access capabilities, but it too supports dynamic resizing.
Bear in mind that both support the get(int index)
signature, but the difference between the two implementations is performance: with an ArrayList
, that's a matter of going to the index position, whereas with a LinkedList
, you have to walk down the object chain (either from the front or the rear, depending on what you've indexed into).
ArrayList Vs LinkedList
Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of add
is O(1) but is not fast:
public class MyList extends LinkedList {
public void add(Object o) {
Thread.sleep(10000);
super.add(o);
}
}
I suspect in your case ArrayList is performing well because it increases it's internal buffer size fairly aggressively so there will not be a large number of reallocations. When the buffer does not need to be resized ArrayList will have faster add
s.
You also need to be very careful when you do this kind of profiling. I'd suggest you change your profiling code to do a warm-up phase (so the JIT has the opportunity to do some optimization without affecting your results) and average the results over a number of runs.
private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;
public void perfTest() {
// Warmup
for (int i = 0; i < WARMUP; ++i) {
buildArrayList();
}
// Test
long sum = 0;
for (int i = 0; i < TEST; ++i) {
sum += buildArrayList();
}
System.out.println("Average time to build array list: " + (sum / TEST));
}
public long buildArrayList() {
long start = System.nanoTime();
ArrayList a = new ArrayList();
for (int i = 0; i < SIZE; ++i) {
a.add(i);
}
long end = System.nanoTime();
return end - start;
}
... same for buildLinkedList
(Note that sum
may overflow and you might be better to use System.currentTimeMillis()
).
It's also possible that the compiler is optimizing away your empty get
loops. Make sure the loop actually does something to ensure that the right code is getting called.
Is LinkedList really faster than ArrayList in the case of insertion in the middle of list?
BUSTED
Not really. Here
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(MAX_VAL/2, i);
}
you don't just insert the item; you pay the cost of iterating from the beginning to i
every time. Naturally, that's O(i)
.
On the other hand, the list must be quite large before you'll actually witness the performance benefit of mid-list insertion. System.arraycopy
is a blazing-fast operation and, on the other end, each insertion into a LinkedList
requires the allocation of a node instance.
In summary, ArrayList
is a better choice for 99% or more of real-world cases, and leveraging the narrow advantage of a LinkedList
requires great care.
General notes on microbenchmarking the JVM
I should also warn you that your benchmarking code is badly deficient. There is quite a sizable checklist of things to watch out for when microbencharking on the JVM, for example:
- always warm up the code to let the JIT compiler get to it;
- be very careful about interpreting
nanoTime
results due to accuracy/precision issues. Make the reading grow at least into milliseconds (millions of nanoseconds) to ensure reliability; - control the spurious side-effects of the Garbage Collector;
- etc.
Therefore the advice is to use a ready-made microbenchmarking framework such as OpenJDK's jmh.
Related Topics
How to Reference a Method in Javadoc
Cleanest Way to Toggle a Boolean Variable in Java
Why Have One Jvm Per Application
How to Configure Log4J to Log Different Log Levels to Different Files for the Same Logger
Generate JPA 2 Entities from Existing Database
Null-Safe Mapping Comparator Using Default Implementations
Does Stream.Foreach Respect the Encounter Order of Sequential Streams
How to Deserialize a Blank JSON String Value to Null for Java.Lang.String
Can a Class Have No Constructor
"No Match Found" When Using Matcher's Group Method
Write a Program That Will Surely Go into Deadlock
Htmlunit Doesn't Wait for JavaScript
How to Change the Default Application Icon in Java