Content from DOC https://q.houxu6.top/?s=When to use LinkedList instead of ArrayList in Java?
I always use it like this:
List<String> names = new ArrayList<>();
I use interfaces as type names for portability so that I can repurpose my code when I ask questions like this.
When should I use LinkedList
instead of ArrayList
or vice versa?
Summary: There are many use cases where ArrayList
and ArrayDeque
are preferred over LinkedList
. If you’re not sure, start with ArrayList
.
TLDR, accessing elements in ArrayList
takes constant time [O(1)], and adding elements takes O(n) time [worst case]. Inserting elements into LinkedList
takes O(n) time, and accessing them also takes O(n) time, but LinkedList
uses more memory than ArrayList
.
LinkedList
and ArrayList
are two different implementations of the List
interface. LinkedList
is implemented using a doubly linked list. ArrayList
is implemented using a dynamically resizable array.
Due to standard linked list and array operations, the various methods will have different algorithm run times.
For LinkedList
:
get(int index)
is O(n) (average n/4 steps), but whenindex = 0
or O(1) whenindex = list.size() - 1
(in this case, you can also usegetFirst()
code> andgetLast()
). The main advantage ofLinkedList
is one of them.add(int index, E element)
is O(n) (average n/4 steps), but whenindex = 0
orindex = list.size() - 1
is O(1) (in this case, you can also useaddFirst( )
andaddLast()
/add()
). The main advantage ofLinkedList
is one of them.remove(int index)
is O(n) (average n/4 steps), but whenindex = 0
or O(1) whenindex = list.size() - 1
(in this case, you can also useremoveFirst()
code> andremoveLast()
). The main advantage ofLinkedList
is one of them.Iterator.remove()
is O(1). The main advantage ofLinkedList
is one of them.ListIterator.add(E element)
is O(1). The main advantage ofLinkedList
is one of them.
NOTE: Many operations require n/4 steps in the average case, a constant number of steps in the best case (e.g. index = 0), and a constant number of steps in the worst case ( The middle of the list) is the number of steps n/2.
For ArrayList
:
get(int index)
is O(1). The main advantage ofArrayList
is one of them.add(E element)
is O(1), but in the worst case it is O(n) because the array must be resized and copy.add(int index, E element)
is O(n) (average n/2 steps).remove(int index)
is O(n) (average n/2 steps).Iterator.remove()
is O(n) (average n/2 steps).ListIterator.add(E element)
is O(n) (average n/2 steps).
NOTE: Many operations require n/2 steps in the average case, a constant number of steps in the best case (end of list), and a constant number of steps in the worst case (start of list ) is the number of n steps.
LinkedList
allows elements to be inserted or removed in constant time using iterators, but elements can only be accessed sequentially. In other words, you can traverse the list forward or backward, but finding a position in the list takes time proportional to the size of the list. Javadoc says* “The operation on the index list will be performed from the beginning or the end, whichever is closer is chosen”, so these methods are O(n)(n/ 4steps), but is O(1)* when index=0.
On the other hand, ArrayList
allows fast random read access, so you can get any element in constant time. However, adding or removing from anywhere but the end requires moving all following elements, either to open up space or to fill gaps. Additionally, if you add more elements than the capacity of the underlying array, a new array (1.5x the size) will be allocated and the old array copied into the new one, thus in the worst case to ArrayList
Addition is O(n), but it is constant on average.
So depending on what you intend to do, the implementation should be chosen accordingly. Iterating over either kind of list actually costs about the same. (Technically, iterating over an ArrayList is faster, but unless you’re very concerned about performance, don’t worry about that – they’re all constants.)
The main benefit of using LinkedList
is when you reuse existing iterators to insert and delete elements. These operations can be completed inO(1)time by only locally changing the list. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other hand, searching in LinkedList
means following the link in O(n) (n/2 steps), whereas in In an ArrayList
, the required position can be mathematically calculated and accessed in *O(1)* time.
Another benefit of using LinkedList
is when you add or remove elements from the beginning of the list, because these operations are O(1), whereas with ArrayList
is O(n). Note that ArrayDeque
might be a good alternative to LinkedList
for adding and removing elements from the beginning, but it is not a List
.
Also, if you have large lists, keep in mind that memory usage will vary. Each element of a LinkedList
has more overhead because pointers to the next and previous elements are also stored. ArrayLists
does not have this overhead. However, ArrayLists
occupy the same memory as the allocated capacity, regardless of whether elements are actually added.
The default initial capacity of ArrayList
is quite small (10 units from Java 1.4 to 1.8). But since the underlying implementation is an array, you have to resize the array if you want to add a large number of elements. To avoid the high cost of resizing when you know a large number of elements will be added, construct an ArrayList
with a higher initial capacity.
If you understand these two structures from the perspective of data structure, then LinkedList
is basically a sequential data structure, which contains a head node. A node is a wrapper around two components: a value of type T accepted via a generic, and another reference to the node to which it is linked. Therefore, we can assert that it is a recursive data structure (one node contains another node, which in turn has another node, and so on…). As mentioned above, adding elements in LinkedList
takes linear time.
ArrayList
is a growable array. It’s just like a regular array. Under the hood, when elements are added and the ArrayList
is full, it creates a new array of a much larger size than the previous one. Then the elements are copied from the previous array into the new array and the element to be added is also placed at the specified index.