How does ArrayList differ from LinkedList?

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

LinkedList this is a normal linked list consisting of nodes. In each node, references to the next/previous node and the 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, the insertion is performed as follows: the element that should be followed by the inserted element is found, the links in it and the one following it are changed.

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

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 ArrayList, the element is obtained by simply taking an index from the array.

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

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

As we see on average, the difficulties are the same. But I wouldn't recommend using LinkedList, except for the exception to the situation when, is dominated by deleting or inserting at the beginning or end of the list.

ArrayList more predictable for the processor, in terms of data location. This is an array, and there the elements are arranged sequentially, occupying a non-contiguous area of memory. This is good, because it allows you to load data into the processor caches without cache miss'ов. The processor is not idle, waiting for data from RAM. With LinkedList there is no such thing, because the elements are located in different parts of memory, and you can predict the location of the next element is beyond the power of the processor.

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);
   }
} 

On my computer, I got 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 selecting ArrayList as a list implementation, it should be understood that the operation of adding elements may cause the array size to increase, 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 list public ArrayList(int initialCapacity).

If you can't estimate the estimated number of items that will be stored in the collection and for you there is no need to access the elements by index, then it is better to pay attention to LinkedList.

It is really important to understand how different types of collections differ, but in practice, for most applications, where we are talking about 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. A much more important point is the choice of the interface of the collection that 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.