Is LinkedList really faster to insert data than ArrayList?

The experiment

JDK version 1.8, test platform MBP2016

Insert data at the end of data

The test code

package com.lly.springtest1.collection;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @ClassName ICollection
 * @Description TODO
 * @Author lly
 * @Date 2019/3/5 9:29 AM
 * @Version 1.0
 **/
@Slf4j
public class ICollection {

    public static void test() {
        LinkedList<String> links = new LinkedList<>();
        int len = 6553631;
        log.info(len + "");
        long btime = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            links.add("sss");
        }
        long etime = System.currentTimeMillis();
        log.info("Time :{}, size :{}", etime - btime, links.size());

        long btime1 = System.currentTimeMillis();
        ArrayList<String> arrays = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            arrays.add("sss");
        }
        long etime1 = System.currentTimeMillis();
        log.info("Time :{}, size :{}", etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); }}Copy the code

The test results

Inserts data into the array header

package com.lly.springtest1.collection;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @ClassName ICollection
 * @Description TODO
 * @Author lly
 * @Date 2019/3/5 9:29 AM
 * @Version 1.0
 **/
@Slf4j
public class ICollection {

    public static void test() {
        LinkedList<String> links = new LinkedList<>();
        int len = 100000;
        log.info(len + "");
        long btime = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            links.addFirst("sss");
        }
        long etime = System.currentTimeMillis();
        log.info(Time :{}, LinkedList size :{}", etime - btime, links.size());

        long btime1 = System.currentTimeMillis();
        ArrayList<String> arrays = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            arrays.add(0,"sss");
        }
        long etime1 = System.currentTimeMillis();
        log.info(Time :{}, ArrayList size :{}, etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); }}Copy the code

Inserts data in the middle of an array

package com.lly.springtest1.collection;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @ClassName ICollection
 * @Description TODO
 * @Author lly
 * @Date 2019/3/5 9:29 AM
 * @Version 1.0
 **/
@Slf4j
public class ICollection {

    public static void test() {
        LinkedList<String> links = new LinkedList<>();
        int len = 10000;
        log.info(len + "");
        long btime = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            links.add(links.size() / 2, "sss");
        }
        long etime = System.currentTimeMillis();
        log.info(Time :{}, LinkedList size :{}", etime - btime, links.size());

        long btime1 = System.currentTimeMillis();
        ArrayList<String> arrays = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            arrays.add(arrays.size() / 2, "sss");
        }
        long etime1 = System.currentTimeMillis();
        log.info(Time :{}, ArrayList size :{}, etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); }}Copy the code

The insertion efficiency of Linkedlist is 20 times slower than ArrayList

Now let me systematically test other orders of magnitude data, plus random insertion tests

public static void test(int listSize, int type) {
        LinkedList<String> links = new LinkedList<>();
        log.info("Array length :{}, insert mode {}", listSize, type);
        long btime = System.currentTimeMillis();
        for (int i = 0; i < listSize; i++) {
            switch (type) {
                case 0:
                    links.addFirst("Test data");
                    break;
                case 1:
                    links.add(links.size() / 2, "Test data");
                    break;
                case 2:
                    links.addLast("Test data");
                    break;
                default:
                    Random random = new Random();
                    int rd = random.nextInt(links.size()+1);
                    links.add(rd, "Test data");
            }

        }
        long etime = System.currentTimeMillis();
        log.info("Time :{}ms, size :{}", etime - btime, links.size());

        long btime1 = System.currentTimeMillis();
        ArrayList<String> arrays = new ArrayList<>();
        for (int i = 0; i < listSize; i++) {
            switch (type) {
                case 0:
                    arrays.add(0, "Test data");
                    break;
                case 1:
                    arrays.add(arrays.size() / 2, "Test data");
                    break;
                case 2:
                    arrays.add("Test data");
                    break;
                default:
                    Random random = new Random();
                    int rd = random.nextInt(arrays.size()+1);
                    arrays.add(rd, "Test data");
            }

        }
        long etime1 = System.currentTimeMillis();
        log.info("Time :{}ms, ArrayList size :{}", etime1 - btime1, arrays.size());

    }
Copy the code

The test results

• Insert experimental data in the header of the collection

  

• Insert experimental data in the middle of the set

• Insert experimental data at the end of the set

  

• Inserts data at random locations in the collection

Source code analysis

Insert at the specified position

LinkedList source

 public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
Copy the code

• Check whether the length of the linked list is exceeded, or throw an error
• If you are inserting the last position, use linkLast instead of iterating through the query
• The node method is used to find the node to which the index points. First check whether the index is greater than size/2. If the index is greater than size/2, start from the end of the index
• Once found, a node object is new, setting the pointer to the problem LinkedList: the main performance is to traverse the list looking for index

ArrayList source

 public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
Copy the code

• RangeCheckForAdd determines whether an index is valid
• EnsureCapacityInternal Determines whether capacity expansion is required
• Arraycopy is a native method that copies all the elements of an array to the next place relative to index
• ElementData assigns an element to the array index element

ArrayList: The main factors that affect the performance of ArrayList are expansion and array replication. However, when the size is very large, the impact of array expansion will be reduced, and the efficiency will be improved at this time. At this time, if we insert data in the middle part, the position we want to insert is I, and the array length is N, then we need to change the n-I data after I.

Insert in the head

LinkedList source

public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
Copy the code

As you can see, the LinkedList is not iterated directly in the header, so it is very efficient, reflecting the high efficiency of LinkedList insertion

ArrayList (ArrayList)

Insert at the tail

LinkedList source

  public boolean add(E e) {
        linkLast(e);
        return true;
    }
   void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
Copy the code

LinkedList: New a Node object with the passed value, and then a tail pointer to the new Node

ArrayList source

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
Copy the code

ArrayList: If the capacity of the array exceeds and needs to be expanded, it is directly assigned to the array elements if no expansion is required

Conclusion: ArrayList is faster than LinkedList when the amount of data is increasing. Reason: When the amount of data is large, ArrayList can get a large amount of new space every time it expands, which solves the disadvantage of frequent expansion in the early stage. Although LinkedList has tail pointer, But every time you add, you turn the object new into a Node.

conclusion

Data volume \ Insert position	The head	In the middle	The tail	random
best	The efficiency of flat	The efficiency of flat	The efficiency of flat	The efficiency of flat
thousand	LinkedList insert fast	The efficiency of flat	The efficiency of flat	ArrayList into fast
wan	LinkedList insert fast	ArrayList into fast	The efficiency of flat	ArrayList into fast
One hundred thousand	LinkedList insert fast	ArrayList into fast	ArrayList into fast	ArrayList into fast
One million	LinkedList insert fast	ArrayList into fast	ArrayList into fast	ArrayList into fast

• LinkedList is faster when the data volume is small, because ArrayList is frequently expanded. ArrayList is faster when the data volume is large, because ArrayList is expanded by its current capacity *1.5. A single expansion of a large capacity provides a lot of space. ArrayList is significantly more efficient than LinkedList when it does not need to be expanded, because direct assignment of array elements does not require new Node
• LinkedList is faster to insert data at the head, because LinkedList takes very little time to traverse the insertion location, whereas ArrayList requires a System. Arraycopy of all the elements in the original array
• The further into the middle, the less efficient the LinkedList is, because it traverses from both ends to the middle, and the longer the index traverses the middle, so ArrayList is likely to be more efficient than LinkedList
• ArrayList is more efficient the further it is inserted, because the array needs to copy less data, so arrayCopy is faster. Therefore, it is more efficient to insert data LinkedList at the head than ArrayList. Tail-inserted data ArrayList is more efficient than LinkedList
• InkedList can implement queue, stack and other data structures, which is its advantage