【 note 】 this article translation: Java ArrayList vs LinkedList | Baeldung

1. An overview of the

For collections, the Java Standard library provides a number of options to choose from. Among these options are two well-known List implementations called ArrayList and LinkedList, each with its own properties and use cases. In this tutorial, we’ll see how both are implemented. We will then evaluate the differences for each application.

2. ArrayList

Internally, ArrayList uses arrays to implement the List interface. Because arrays are fixed size in Java, ArrayList creates an array with some initial capacity. During this process, if we need to store more items than the default capacity, it replaces that array with a new, larger one. To better understand its properties, let’s evaluate this data structure in terms of its three main operations: add items, get items by index, and drop items by index.

Add 2.1.

When we create an empty ArrayList, it initializes its backup array with the default capacity (currently 10) :

Adding a new item when the array is not full is as simple as assigning the item to a specific array index. The array index is determined by the current array size, because we are actually appending to the list:

backingArray[size] = newItem;
size++;
Copy the code

Thus, in the best and general case, the time complexity of the addition operation is O(1), which is very fast. However, as the backup array becomes full, adding implementations becomes less efficient:

To add a new item, we should first initialize a new, larger array and copy all existing items into the new array. We can only add a new item after copying the current element. So, in the worst case, time is O(n), because we have to copy n elements first. Theoretically, the running time for adding new elements is the amortization constant. In other words, it takes O(n) time to add n elements. However, some single additions may not perform well because of the replication overhead.

2.2 access by index

Accessing items through indexes is the real beauty of ArrayList. To retrieve the item with subscript I, we simply return the item with the ith subscript in the backup array. Therefore, the time complexity of access through index operations is always O(1).

2.3. Delete by index

Suppose we want to remove index 6 from the ArrayList, which corresponds to element 15 in our backup array:

After we mark the desired element as deleted, we should move all subsequent elements back one index. Obviously, the closer the element is to the beginning of the array, the more elements we should move. Thus, the time complexity is O(1) in the best case and O(n) in the average and worst cases.

2.4. Applications and Limitations

In general, ArrayList is the default choice for many developers when a List implementation is needed. In fact, this is actually a wise choice when the number of reads far exceeds the number of writes. Sometimes we need to read and write equally frequently. If we do estimate the maximum number of possible items, using an ArrayList still makes sense. If this is the case, we can initialize the ArrayList with initial capacity:

int possibleUpperBound = 10 _000;
List<String> items = new ArrayList<>(possibleUpperBound);
Copy the code

This estimation prevents a lot of unnecessary copying and array allocation.

Additionally, arrays are indexed by Java int values. Therefore, it is impossible to store more than 2 ^ 32 elements in a Java array, and therefore, the same is true in an ArrayList.

3. LinkedList

LinkedList, as the name suggests, uses a collection of linked nodes to store and retrieve elements. For example, here is the Java implementation with four elements added:

Each node maintains two Pointers: one to the next element and one to the previous element. To extend this, a bidirectional list has two Pointers to the first and last item. Again, let’s evaluate this implementation against the same basic operations.

Add 3.1.

To add a new node, first we should link the current last node to the new node:

Then update the last pointer:

Since both operations are simple, the time complexity of the addition operation is always O(1).

3.2. Access by index

LinkedList, unlike ArrayList, does not support fast random access. Therefore, to find elements by index, we should manually traverse parts of the list.

In the best case, when the requested item is near the beginning or end of the list, the time complexity will be as fast as O(1). However, on average and in the worst case, we might end up with O(n) access times because we have to check many nodes one after the other.

3.3. Delete by index

To remove an item, we should first find the requested item and then unlink it from the list. Thus, the access time determines the time complexity — that is, O(1) in the best case and O(n) in the average and worst cases.

3.4. The application

LinkedLists are more appropriate when the add rate is much higher than the read rate. In addition, it can be used for read-intensive scenarios when most of the time we want the first or last element. Notably, LinkedList also implements a Deque interface that enables efficient access to both ends of the collection. Often, if we know their implementation differences, we can easily pick one for a particular use case. For example, suppose we are going to store a large number of time series events in a list-like data structure. We know we’re getting emergencies every second. In addition, we need to check all events regularly and provide some statistics. For this use case, LinkedList is a better choice because the add rate is much higher than the read rate. In addition, we read all items, so we can’t exceed the O(n) limit.

4. Conclusion

In this tutorial, we first delve into how ArrayList and LinkLists are implemented in Java. We also evaluated different use cases for each of them.