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 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<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.
I see the question as being the opposite-
When should you use an Array over a List?
Only you have a specific reason to do so (e.g.: Project Constraints, Memory Concerns (not really a good reason), etc.)
Lists are much easier to use (imo) and have much more functionality.
Note: You should also consider whether or not something like a Set, or another data structure is a better fit than a List for what you are trying to do.
Each data structure, and implementation, has different pros/cons. Pick the ones that excel at the things that you need to do.
If you need get() to be O(1) for any item? Likely use an ArrayList, Need O(1) insert()? Possibly a Linked List. Need O(1) contains()? Possibly a Hashset.
TLDR: Each data structure is good at some things, and bad at others. Look at your objectives and choose the data structure that best fits the given problem.
Edit:
One thing not noted is that you're better off declaring the variable
as its interface (i.e. List or Queue) rather than its implementing
class. This way, you can change the implementation at some later date
without changing anything else in the code.
As an example:
List<String> myList = new ArrayList<String>();
vs
List<String> myList = new LinkedList<String>();
Note that myList is a List in both examples.
--R. Bemrose
Best Answer
I like to think of it as a data-structure that lets you enjoy both worlds, the quick-access to an index like with an array and the infinite growth of a list. Of course, there are always trade-offs.
ArrayList
is actually a wrapper to an array. Every time the size of the array ends, a new array, twice the size, is created and all the data from the original array is copied to the new one.From the java doc:
This allows O(1) access for most of the operations like it would take with an array. Once in a while you need to pay for this performance with an insert operation that takes much longer though.
This is called amortized complexity. Each operation takes only O(1) aside for those times you need to double the size of the array. In those time you would pay O(n) but if you average it over n operations, the average time taken is only O(1) and not O(n).
Let's take an example:
We have an array of size 100 (n=100). You make 100 insert operations (to different indices) and each of them takes only O(1), of course that all get-by-index operations also take O(1) (as this is an array). On the 101 insertion, there's no more more capacity in the array so the ArrayList will create a new array, the size of 200, copy all the values to it (O(n) operations) and then insert the 101st item. Until you fill out the array to 200 items, all of the operations would take O(1).