What is the difference between ArrayList and LinkedList?

ArrayList based on a regular array. This collection dynamically increases the size of the array if there is not enough space when calling the add(T element) , addAll(Collection<T> other) methods. It can also reduce it if the size is larger than the number of stored elements, using the trimToSize() method

LinkedList is a regular linked list consisting of nodes. At each node, links to the next / previous node and value are stored. In the list itself, there are links to the last and first node, as well as the size.

To evaluate these data structures, one can resort to the asymptotic complexity of performing operations:

  | ArrayList | LinkedList add (в начало) | O(n) | O(1) add (в середину) | O(n) | O(n) add (в конец списка) | O(n) | O(1) 

In LinkedList insertion is carried out as follows: the element is located, followed by the element to be inserted, the links in it and the one following it change.

A new array is created in ArrayList if there is no space in the current one. Those elements that are before being inserted, remain in place, or are copied to a new one. Next, the inserted element is added. Then the remaining elements that were in the original are copied.

 get (первый элемент) | O(1) | O(1) get (из середины) | O(1) | O(n) get (последний элемент) | O(1) | O(1) 

In LinkedList to find an element with the desired index, you need to go through the links one by one from the first element to the last (in the worst case). In an ArrayList getting an item happens by simply taking an index from an array.

 delete (первый элемент) | O(n) | O(1) delete (из середины) | O(n) | O(n) delete (последний элемент) | O(1) | O(1) 

In LinkedList deletion is the same as insertion. In ArrayList , approximately, as well as when adding.

As we see on average, the difficulties are the same. But I would not recommend using LinkedList , except for the situation when deletion or insertion at the beginning or end of the list prevails.

ArrayList more predictable for the processor, in terms of the location of the data. This is an array, and there the elements are arranged in series, occupying a continuous area of ​​memory. This is good, as it allows loading data into processor caches without cache miss'ов . The processor is not idle, waiting for data from RAM. With LinkedList there is no such, because the elements are located in different memory areas, and it’s impossible to predict the location of the next element.

Code showing the difference in performance:

 @Fork(1) @Warmup(iterations = 10) @Measurement(iterations = 10) @BenchmarkMode(Mode.AverageTime) @Threads(1) @State(Scope.Benchmark) @OutputTimeUnit(TimeUnit.MILLISECONDS) public class PerformanceTest { private static List<Object> arrayList; private static List<Object> linkedList; private static final int count = 100_000; public static void main(String[] args) throws Exception { Main.main(args); } @Setup public static void setup() { arrayList = new ArrayList<>(count); linkedList = new LinkedList<>(); for (int i = 0; i < count; i++) arrayList.add(new Object()); linkedList.addAll(arrayList); } @Benchmark public void removeFromLinkedList(Blackhole blackhole) throws Exception { Object object = new Object(); linkedList.remove(count / 2); linkedList.add(count / 2, object); } @Benchmark public void removeFromArrayList(Blackhole blackhole) throws Exception { Object object = new Object(); arrayList.remove(count / 2); arrayList.add(count / 2, object); } } 

My computer has the following:

 Benchmark Mode Cnt Score Error Units PerformanceTest.removeFromArrayList avgt 10 0.011 ± 0.001 ms/op PerformanceTest.removeFromLinkedList avgt 10 0.148 ± 0.001 ms/op 

The results show that LinkedList is 14 times slower.

When choosing ArrayList as the implementation of the list, it should be understood that the operation of adding elements may necessitate an increase in the size of the array, which will lead to the operation of copying all the elements from one array to another. In this regard, you should pay attention to the initial capacity, which can be specified in the constructor when creating the public ArrayList(int initialCapacity) .

If you can not estimate the estimated number of items that will be stored in the collection and you do not need to access the items by index, it is better to pay attention to LinkedList .

Understanding the difference between different types of collections is really important, but in practice for most applications, where it comes to dozens and hundreds of elements, the choice of a specific collection implementation does not play a big role both in terms of performance and in terms of memory used. Much more important is the choice of the interface of the collection you are going to use:

• java.util.Collection
• java.util.List
• java.util.Set

The choice of interface will directly affect the logic of your code. Interfaces are also better used as parameters and return types of public methods.