LinkedList is 1000 times slower than ArrayList? (GIF + Performance evaluation)

Array and linked list are two kinds of data structure commonly used in programs, and also one of the interview questions. However, for many people, just vaguely remember the difference between the two, may still remember not necessarily right, and every time to the interview, have to take out these concepts back again, rather some trouble. This article will start with the execution process diagram and performance evaluation, so that you can understand and remember the difference between the two more deeply. After this in-depth study, I believe you will remember deeply.

An array of

Before we get started, what is an array?

Arrays are defined as follows:

An Array is a data structure consisting of a collection of elements of the same type, allocated a contiguous chunk of memory for storage. The index of an element can be used to calculate the corresponding storage address of the element.

The simplest type of data structure is a one-dimensional array. For example, a 32-bit integer array with indexes 0 through 9 can be used as a storage address at 2000,2004,2008… In 2036, 10 variables are stored, so the element indexed with I is the 2000+4× I address in memory. The memory address of the first element of the array is called the first address or base address.

Simply put, an array is a data structure consisting of a contiguous chunk of memory. One of the key words in this concept is “contiguous”, which reflects the fact that arrays must be made up of a single contiguous memory.

Array data structure, as shown below:

The process of adding an array is shown below:

Advantages of arrays

The “contiguous” nature of an array makes it fast to access. Because it is stored continuously, it is stored in a fixed location, so it is fast to access. For example, 10 rooms are occupied by age order, when we know that the first house is occupied by 20 year olds, then we know that the second house is occupied by 21 year olds, and the fifth house is occupied by 24 year olds…… And so on.

Disadvantages of arrays

Misfortune lies where happiness lies. Array continuity has both advantages and disadvantages. The advantages have been mentioned above, but the disadvantages are that it requires a high level of memory, so you have to find a contiguous chunk of memory.

Another disadvantage of arrays is that they are slow to insert and delete. If we insert or delete data at the end of an array, we move all subsequent data, which incurs some performance overhead. The deletion process is shown in the following figure:

The list

A linked list is a data structure that complements an array. It is defined as follows:

Linked list is a common basic data structure. It is a linear list, but it does not store data in a linear order. Instead, it stores Pointers to the next node in each node. Because they do not have to be stored sequentially, linked lists can be inserted at O(1) complexity, which is much faster than the other linear sequential lists, but it takes O(n) time to find a node or access a node with a specific number, whereas sequential lists take O(logn) and O(1) time, respectively.

In other words, a linked list is a data structure without continuous memory storage. The linked list elements have two attributes, one is the value of the element, and the other is a pointer, which marks the address of the next element.

The data structure of the linked list is shown below:

The process of adding a linked list is shown below:

Classification of the list

Linked lists fall into the following categories:

Singly linked list
Two-way linked list
Circular linked list

Singly linked list

A one-way linked list contains two fields, an information field and a pointer field. This link points to the next node in the list, and the last node points to an empty value. The list we showed above is a one-way list.

Two-way linked list

A bidirectional list is also called a doubly linked list. In a bidirectional list, there is not only a pointer to the next node, but also a pointer to the previous node, so that you can access the previous node from any node, and of course, the latter node, or even the whole list.

The structure of a bidirectional linked list is shown below:

Circular linked list

The first node in a circular list is preceded by the last, and vice versa. The borderless nature of circular lists makes it much easier to design algorithms on such lists than on regular lists.

The structure of a circular linked list is shown below:

Why are there single and double linked lists?

One might ask, why do we have two-way lists when we already have one-way lists? What are the advantages of bidirectional lists?

This starts with the deletion of a linked list. If a one-way linked list wants to delete an element, it needs to find not only the deleted node, but also the node before the deleted node (usually called a precursor), because it needs to change the pointer of next in the last node, but because it is a one-way linked list, Therefore, the deleted node does not store the related information of the previous node, so we need to query the linked list again to find the previous node, which brings certain performance problems, so there is a bidirectional linked list.

List advantages

The advantages of linked lists can be roughly divided into the following three:

Linked lists have a high memory utilization ratio and do not require continuous memory space. Even if there is memory fragmentation, it does not affect the creation of linked lists.
Linked lists can be inserted and deleted quickly without the need to move a large number of elements like arrays.
Linked list size is not fixed, can be very convenient for dynamic expansion.

List disadvantages

The main disadvantage of linked list is that it cannot be searched randomly and must be traversed from the first one, which has low search efficiency and the time complexity of linked list query is O(n).

The performance evaluation

Now that you know the basics of arrays and linked lists, let’s move on to performance evaluation.

Before we start, let’s clarify the test objectives. We only need to test six points:

Performance test for add operations from head/middle/tail;
Performance tests from the head/middle/tail of the query.

Add and delete operations are basically the same in terms of execution time. For example, adding an array requires moving the following elements, and deleting the following elements is also the same. The linked list is the same, adding and deleting are to change the information of itself and connected nodes, so we combine the test of adding and deleting into one, and use the add operation to test.

Test instructions:

In the Java language, arrays are represented byArrayList, and the linked list representsLinkedList, so we use these two objects for testing;
In this article we will use the Oracle official recommended JMH framework for testing. Click here to see more about JMH.
The test environment of this article is JDK 1.8, MacMini, Idea 2020.1.

1. Add performance tests to the header

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime) // Test completion time
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // Preheat times and time
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // Number of tests and time
@Fork(1) // start 1 thread
@State(Scope.Thread)
public class ArrayOptimizeTest {

    private static final int maxSize = 1000; // Test the number of cycles
    private static final int operationSize = 100; // Number of operations


    private static ArrayList<Integer> arrayList;
    private static LinkedList<Integer> linkedList;

    public static void main(String[] args) throws RunnerException {
        // Start the benchmark
        Options opt = new OptionsBuilder()
                .include(ArrayOptimizeTest.class.getSimpleName()) // The test class to import
                .build();
        new Runner(opt).run(); // Execute the test
    }

    @Setup
    public void init(a) {
        // Start the execution event
        arrayList = new ArrayList<Integer>();
        linkedList = new LinkedList<Integer>();
        for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); }}@Benchmark
    public void addArrayByFirst(Blackhole blackhole) {
        for (int i = 0; i < +operationSize; i++) {
            arrayList.add(i, i);
        }
        // To avoid JIT ignoring unused result calculations
        blackhole.consume(arrayList);
    }

    @Benchmark
    public void addLinkedByFirst(Blackhole blackhole) {
        for (int i = 0; i < +operationSize; i++) {
            linkedList.add(i, i);
        }
        // To avoid JIT ignoring unused result calculationsblackhole.consume(linkedList); }}Copy the code

As can be seen from the above code, we initialize ArrayList and LinkedList before testing, and add 100 elements from the header. The result is as follows:

As you can see from the above results, the average execution (completion) time of LinkedList is approximately 216 times faster than the average execution time of ArrayList.

2. Add a performance test

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime) // Test completion time
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // Preheat times and time
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // Number of tests and time
@Fork(1) // start 1 thread
@State(Scope.Thread)
public class ArrayOptimizeTest {
    private static final int maxSize = 1000; // Test the number of cycles
    private static final int operationSize = 100; // Number of operations

    private static ArrayList<Integer> arrayList;
    private static LinkedList<Integer> linkedList;

    public static void main(String[] args) throws RunnerException {
        // Start the benchmark
        Options opt = new OptionsBuilder()
                .include(ArrayOptimizeTest.class.getSimpleName()) // The test class to import
                .build();
        new Runner(opt).run(); // Execute the test
    }

    @Setup
    public void init(a) {
        // Start the execution event
        arrayList = new ArrayList<Integer>();
        linkedList = new LinkedList<Integer>();
        for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); }}@Benchmark
    public void addArrayByMiddle(Blackhole blackhole) {
        int startCount = maxSize / 2; // Calculate the middle position
        // Insert the middle part
        for (int i = startCount; i < (startCount + operationSize); i++) {
            arrayList.add(i, i);
        }
        // To avoid JIT ignoring unused result calculations
        blackhole.consume(arrayList);
    }

    @Benchmark
    public void addLinkedByMiddle(Blackhole blackhole) {
        int startCount = maxSize / 2; // Calculate the middle position
        // Insert the middle part
        for (int i = startCount; i < (startCount + operationSize); i++) {
            linkedList.add(i, i);
        }
        // To avoid JIT ignoring unused result calculationsblackhole.consume(linkedList); }}Copy the code

As can be seen from the above code, we initialize ArrayList and LinkedList before testing, and add 100 elements from the middle. The result is as follows:

As you can see from the above results, the average execution time of LinkedList is about 54 times faster than the average execution time of ArrayList.