What is the difference between ArrayList and LinkedList?

What is the difference LinkedListfrom ArrayList? And in what cases is it more convenient to use in practice LinkedList?

Asked on February 4, 2020 in Programming.
Add Comment
1 Answer(s)

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

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

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

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

The LinkedListinsertion is carried out as follows: there is an element followed by the inserted element, the links in it and the one following it are changed.

In ArrayListcreating a new array if this is no place. Those elements that are before the 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 LinkedListorder to find the element with the desired index, you need to go through the links alternately from the first element to the last (in the worst case). An ArrayListelement is obtained by simply taking an index from an array.

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

The LinkedListdeletion is similar to the insertion. In ArrayListabout the same as when adding.

As we see on average, the difficulties are the same. But I would not recommend using it LinkedList, with the exception of the situation when deleting or pasting to the beginning or end of the list predominates.

ArrayListmore predictable for the processor, in terms of data location. This is an array, and there the elements are arranged sequentially, occupying a non-discontinuous 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. There LinkedListis no such thing since the elements are located in different parts of the memory, and the processor can’t 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); } } 

The following happened on my computer:

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 it LinkedListis 14 times slower.

Answered on February 4, 2020.
Add Comment

Your Answer

By posting your answer, you agree to the privacy policy and terms of service.