I've always been one to simply use:
List<String> names = new ArrayList<>();
I use the interface as the type name for portability, so that when I ask questions such as this, I can rework my code.
When should LinkedList be used over ArrayList and vice-versa?
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) 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<E>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<E>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<E>Iterator.remove() is O(1). One of the main benefits of LinkedList<E>ListIterator.add(E element) is O(1). One of the main benefits of LinkedList<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 of ArrayList<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.
ArrayList is what you want. LinkedList is almost always a (performance) bug.
Why LinkedList sucks:
ArrayList was used.ArrayList, it is probably going to be significantly slower anyway.LinkedList in source because it is probably the wrong choice.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.
Update (Aug 27, 2021 -- 10 years later): This answer (my most historically upvoted answer on SO as well) is very likely wrong (for reasons outlined in the comments below). I'd like to add that ArrayList will optimize for sequential reading of memory and minimize cache-line and TLB misses, etc. The copying overhead when the array grows past the bounds is likely inconsequential by comparison (and can be done by efficient CPU operations). This answer is also probably getting worse over time given hardware trends. The only situations where a LinkedList might make sense would be something highly contrived where you had thousands of Lists any one of which might grow to be GB-sized, but where no good guess could be made at allocation-time of the List and setting them all to GB-sized would blow up the heap. And if you found some problem like that, then it really does call for reengineering whatever your solution is (and I don't like to lightly suggest reengineering old code because I myself maintain piles and piles of old code, but that'd be a very good case of where the original design has simply run out of runway and does need to be chucked). I'll still leave my decades-old poor opinion up there for you to read though. Simple, logical and pretty wrong.
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)
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.
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->Netherlands->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
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.
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.
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 |
|--------------------------------------|
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).
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.
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?
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.
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<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 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;
}
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.
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.