I use a lot of lists and arrays but I have yet to come across a scenario in which the array list couldn't be used just as easily as, if not easier than, the linked list. I was hoping someone could give me some examples of when the linked list is notably better.
Linked List vs Array – When to Use Each Data Structure
arraylistarrayslinked-listlist
Related Solutions
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.
Both store a sequence of elements, but using different techniques.
An array stores elements in successive order in memory, i.e. it looks like follows:
--------------------------------------------------------------------------------------
| item 1 | item 2 | item 3 | ... ... | item x | //here comes other stuff
--------------------------------------------------------------------------------------
This means, elements are one after another consecutive in memory.
A ((doubly) linked) list, on the other hand, stores the items the following way: It creates an own "list item" for each element; this "list item" holds the actual element and a pointer/reference/hint/etc to the next "list item". If it is doubly linked, it also contains a pointer/reference/hint/etc to the previous "list item":
------------
------------ ---------- | item 4 |
| item 1 | | item 2 | | next ---+----...
| next ---+------->| next | ------------
------------ ---+------ ^
| |
| |
v |
---------- |
| item 3 | |
| next --+---+
----------
This means, the elements can be spread all over the memory and are not stored at specific memory locations.
Now that we know this, we can compare some usual operations on sequences of elements:
Accessing an element at a specific index: Using an array, we simply compute the offset for this index and have the element at the index.
This is very cheap. With a list on the other hand, we do not know a priori where the element at index is stored (since all elements can be anywhere in memory), so we have to walk the list item by item until we find the element at the index. This is an expensive operation.
Adding a new element at the end of the sequence: Using an array this can lead to the following problem: Arrays are usually of fixed size, so if we have the situation that our array is already completely filled (see
//here comes other stuff
), we probably cant put the new element there because there might already be something else. So, maybe we have to copy the whole array. However, if the array is not filled, we can simply put the element there.Using a list, we have to generate a new "list item", put the element into it and set the
next
pointer of the currently last element to this new list item. Usually, we store a reference to the currently last element so that we don't have to search through the whole list to find it. Thus, inserting a new element is no real problem with lists.Adding a new element somewhere in the middle: Let's first consider arrays: here, we might get into the following situation: We have an array with elements 1 to 1000:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
Now, we want to insert
4.5
between4
and5
: This means, we have to move all elements from5
to1000
one position right in order to make space for the4.5
:1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free || vv 1 | 2 | 3 | 4 | 4.5 | 5 | 6 | ... | 999 | 1000 | free
Moving all these elements, is a very expensive operation. So better don't do this too often.
Now we consider, how a list can perform this task: Let's say we have currently the following list:
1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
Again, we want to insert
4.5
between4
and5
. This can be done very easily: We generate a new list item and update the pointers/references:1 -> 2 -> 3 -> 4 5 -> ... -> 999 -> 1000 | ^ +-> 4.5 -+
We have simply created a new list element and generated sort of "bypass" to insert it - very cheap (as long as we have a pointer/reference to the list item the new element will be inserted after).
So, let's sum up: Linked lists are really nice when it comes to inserting at random positions (as long as you have a pointer to the adequate list item). If your operation involves adding lots of elements dynamically and traversing all elements anyway, a list might be a good choice.
An array is very good when it comes to index accesses. If your application needs to access elements at specific positions very often, you should rather use an array.
Notable things:
Solving the fixed-size problem for arrays: As mentioned before, (raw) arrays are usually of fixed size. However, this problem is nowadays no real point anymore, since almost all programming languages provide mechanisms to generate arrays that grow (and possibly shrink) dynamically - just as needed. This growing and shrinking can be implemented such that we have amortized runtime of O(1) for inserting and removing elements (at the end of the array) and such that the programmer doesn't have to call
grow
andshrink
explicitly.Since lists provide such nice properties for insertions, they can be used as underlying data structures for search trees, etc. I.e. you construct a search tree, whose lowest level consists of the linked list.
Best Answer
Linked lists are preferable over arrays when:
you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
you don't need random access to any elements
you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
you need indexed/random access to elements
you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array
you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.
Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.