Spoiler: ArrayList's insertion and query operations are much faster than LinkedList

ArrayList

characteristic

• The bottom layer is realized by array, with fast query speed and slow addition, deletion and modification speed (in theory)
• Thread unsafe

Common methods of ArrayList

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author Zhang Baoxu
 */
public class ArrayListTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(); // Create ArrayList

        list.add("Beijing"); // Add element
        list.add("Shanghai");
        list.add("Hangzhou");
        list.add("Shenyang");
        list.add("Dongdaihe");

        System.out.println(list.toString()); // Print set

        System.out.println(list.size()); // Get collection size

        System.out.println(list.get(0)); // Gets the element of the specified subscript

        list.remove(0); // Deletes the element with the specified subscript
        list.remove("Shanghai"); // Delete the specified element

        System.out.println(list.isEmpty()); // Judge whether the set is empty

        System.out.println(list.contains("Beijing")); // Interpret whether the set contains an element

        // Iterate over collection elements
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
        // Enhanced for traversal
        for (String value : list) {
            System.out.print(value + " ");
        }
    }
}

Operations on basic data types

When you add a basic data type to the list, it will be automatically boxed into a packing type

List<Integer> lit = new ArrayList<>();
lit.add(12);
lit.add(25);
lit.add(99);

And when we delete the specified element

lit.remove(12);

Because 12 is a basic data type, this deletion method deletes elements with subscript 12

Therefore, you need to change the deletion statement to convert the 12 strong to the packaging type

lit.remove((Integer)12);

In this way, the element with 12 in the list can be deleted correctly

ArrayList source code analysis

The underlying uses arrays to hold elements

transient Object[] elementData;

Default capacity: 10

private static final int DEFAULT_CAPACITY = 10;

ArrayList construction method

When a list is created and no elements are added to the list, the capacity is 0

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

add() method (capacity expansion)

1. When there is no element in the list, the capacity is expanded to 10 after adding an element

public boolean add(E e) {
    // Initially, the size is 0, so 1 is passed in
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // At first, the array is empty, so the condition holds
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // Let minCapacity = the maximum number between the two
        // DEFAULT_CAPACITY is the default capacity of 10, and the parameter passed in by minCapacity is 1
        // So minCapacity = 10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // Then call this method, and the passed in parameter is 10
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // Number of modifications, plus one
    modCount++;

    // overflow-conscious code
    // The initial array length is 0, so 10-0 > 0 holds
    if (minCapacity - elementData.length > 0)
        // Call this method
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // The original array length is 0
    int oldCapacity = elementData.length;
    // New array length = original length + (original length divided by 2) = 0 + 0 / 2 = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 0 - 10 < 0
    if (newCapacity - minCapacity < 0)
        // So the new array length is assigned = 10
        newCapacity = minCapacity;
    // 10 - a large number > 0 does not hold, so it will not be executed
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // This method is then called to copy the array
    // The original array is given a new length of 10 and copied into this array to realize the expansion of the array
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Therefore, the operation of expanding the array to 10 when adding an element at the beginning is realized here

Then perform the remaining operations of the add() method, add the value to the array, and increase the size by one

Sort out the process again

• First call the add() method
• Then call the ensureCapacityInternal() method to determine whether the element in the list is empty. If it is empty, the parameter of capacity expansion is 10
• Then call the ensueexplicitcapacity () method to determine whether the minimum capacity is greater than the length of the array. If it is not greater than, there is no need to expand the capacity. If it is greater than, expand the capacity and call the grow(minCapacity) method
• Then call the grow(minCapacity) method of the, give the length of the expansion, and then use the array copy method to expand the capacity
• Finally, execute the add() method to add the value to the array, and increase the size by one

2. When there are elements in the list, but the size of the array is not exceeded, add elements to the list

(if there is an element in the set at this time, size=1, and the length of the array is 10)

// First, call the add method to add
public boolean add(E e) {
    // Judge whether capacity expansion is required. The input parameter is 2
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // The array is not empty, so the condition does not hold
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // Then call this method directly
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // Number of modifications plus one
    modCount++;

    // overflow-conscious code
    // 2 - 10 > 0, the condition is not tenable, and the downward execution is not allowed
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Finally, the add() method is executed

// Add a new element e to the position of size, and then add one to the length size
elementData[size++] = e;

3. When there are elements in the list and the length is full, the second expansion is required

(if current array size = 10)

// First call the add() method to add
public boolean add(E e) {
    // For capacity expansion, the input parameter is 11
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // The array is not empty, so the condition does not hold
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // Call this method directly, and the passed in parameter is 11
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // Number of modifications plus one
    modCount++;

    // overflow-conscious code
    // 11 - 10 > 0, the condition holds, and the grow method is called
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // Original array length = 10
    int oldCapacity = elementData.length;
    // New array length = 10 + (10 / 2) = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // The condition of < 11 - 15 does not hold
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 15 - large number > 0 condition does not hold
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // Therefore, directly execute this method to copy the original array and also copy it to the original array (equivalent to overwrite)
    // The copy length is 15, which realizes the expansion of the array
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Finally, execute the add() method, add the element to the back, and then add one to size

According to the code

int newCapacity = oldCapacity + (oldCapacity >> 1);

Expand the capacity when adding elements for the first time. The size of each expansion is 1.5 times the original size (moving one bit to the right is to divide by 2)

remove() method

If there are 10 elements, delete the element with subscript 3

public boolean remove(Object o) {
    // First judge whether the incoming object is null
    if (o == null) {
        // If it is null, it will traverse the array again to find whether there are elements with null value
        for (int index = 0; index < size; index++)
            // When an element with null value is found, it is quickly deleted, and then true is returned, indicating that the deletion is successful
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // If the object passed in is not null, it is also traversed
        for (int index = 0; index < size; index++)
            // A matching object was found in the array
            if (o.equals(elementData[index])) {
                // Then use the quick delete method to delete the found element with index
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    // Number of modifications plus one
    modCount++;
    // Number of times the element needs to be moved 10 - 3 - 1 = 6
    // 0 1 2 3 4 5 6 7 8 9
    // Because there are six elements behind position 3, after deletion, these six elements must move forward one bit
    int numMoved = size - index - 1;
    // If you need to move elements
    if (numMoved > 0)
        // Using the array copy method, start from the position of index+1 and move the following elements forward by one bit (that is, forward overwrite)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // After moving, you need to clear the value of the last element, and then reduce the size by one to complete the deletion operation
    elementData[--size] = null; // clear to let GC do its work
}

LinkedList

characteristic

• The bottom layer is realized by linked list, which has fast insertion and deletion speed (theoretically) and fast query speed
• LinkedList can be used to implement stack, queue and other data structures

LinkedList common methods

import java.util.*;

/**
 * @author Zhang Baoxu
 */
public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("I"); // Add element
        linkedList.add("Love");
        linkedList.add("You");
        linkedList.add("Very");

        linkedList.remove("Very"); // Delete the specified element

        linkedList.size(); // Get list length

        linkedList.get(0); // Gets the element of the specified subscript

        linkedList.contains("Love"); // Determines whether the specified element is included

        linkedList.indexOf("I"); // Gets the subscript of the specified element

        linkedList.set(1, "love"); // Modify the element of the specified subscript

        // Convert list to array
        String[] strings = linkedList.toArray(new String[0]);
        System.out.println(Arrays.toString(strings));

        // for loop traversal
        for(int i = 0; i < linkedList.size(); i++) {
            System.out.print(linkedList.get(i) + " ");
        }
        System.out.println();

        // Enhanced for traversal
        for (String s : linkedList) {
            System.out.print(s + " ");
        }
        System.out.println();

        // Iterator traversal
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

        // List iterator traversal (reverse traversal)
        ListIterator<String> listIterator = linkedList.listIterator(linkedList.size());
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previousIndex() + " : " + listIterator.previous() + " ");
        }
    }
}

LinkedList source code analysis

Basic properties

Construction method

public LinkedList() {
}

Linked list length

transient int size = 0;

Head pointer

transient Node<E> first;

Tail pointer

transient Node<E> last;

add() method

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    // Create a temporary pointer to last, that is, l is the last node
    final Node<E> l = last;
    // Create a node, the precursor pointer points to l, the element is e, and the subsequent node points to null
    final Node<E> newNode = new Node<>(l, e, null);
    // Make the last pointer point to the new node
    last = newNode;
    // When l is empty, it indicates that the linked list is empty. Add it directly and make the header pointer point to the new node
    // At this time, there is only one node. last points to it and first points to it
    if (l == null)
        first = newNode;
    else
        // When l is not empty, it indicates that there are elements in the linked list, so the subsequent pointer of L points to the new node
        // At this time, the connection of the two-way linked list is completed (the second part completes the precursor pointer pointing to l)
        l.next = newNode;
    size++;
    modCount++;
}

remove() method

public boolean remove(Object o) {
    // First determine whether the element to be deleted is null
    if (o == null) {
        // If so, traverse the linked list to find the node with null node value
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // Call this method to delete elements when found
                unlink(x);
                return true;
            }
        }
    } else {
        // If the element to be deleted is not null, you can also traverse the linked list to find this element
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                // Call this method to delete elements when found
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    // Take out the value, successor node and predecessor node of the node
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // If the precursor node is empty, it means that the header node is to be deleted
    if (prev == null) {
        // So direct the header pointer to the next one and skip the original header node
        first = next;
    } else {
        // Otherwise, the intermediate node is to be deleted
        // After a long time, point the subsequent pointer of the predecessor node of the node to be deleted to the subsequent node of the element to be deleted
        // That is to point its front to its back and skip it by itself
        prev.next = next;
        // Then make the precursor node of the element to be deleted null and release the jump precursor pointer
        x.prev = null;
    }

    // The above is the modification precursor, and the following is the modification successor
    // When the subsequent node of the element to be deleted is empty, this node is the tail node
    if (next == null) {
        // Therefore, the pointer directly leading its tail points to the previous one and skips the last node
        last = prev;
    } else {
        // Otherwise, the intermediate node is deleted
        // Point the precursor pointer of the last node of that node to the precursor node of that node, and skip it by itself
        next.prev = prev;
        // Then set the subsequent pointer of that node to null and release this pointer
        x.next = null;
    }

    // The precursor pointer is released, and the subsequent pointer is released. Now release the value of this node and set the value to null
    x.item = null;
    size--; // The length of the linked list minus one
    modCount++; // Number of modifications plus one
    return element; // Returns the deleted element
}

Test the performance of ArrayList and LinkedList

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

/**
 * Test the performance of ArrayList and LinkedList.
 *
 * @author Zhang Baoxu
 */
public class PerformanceTest {
    // A million times
    static final int QUERY_COUNT = 10000000;
    static List<String> arrayList = new ArrayList<>();
    static List<String> linkedList = new LinkedList<>();
    public static void main(String[] args) {
        // insert
        PerformanceTest.arrayListInsert();
        PerformanceTest.linkedListInsert();
        // query
        PerformanceTest.arrayListQuery();
        PerformanceTest.linkedListQuery();
    }

    /**
     * Test ArrayList insertion performance
     */
    public static void arrayListInsert() {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < QUERY_COUNT; i++) {
            arrayList.add(String.valueOf(i));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList Insert elapsed time: " + (endTime - startTime));
    }

    /**
     * Test LinkedList insertion performance
     */
    public static void linkedListInsert() {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < QUERY_COUNT; i++) {
            linkedList.add(String.valueOf(i));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList Insert elapsed time: " + (endTime - startTime));
    }

    /**
     * Test ArrayList query performance
     */
    public static void arrayListQuery() {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < QUERY_COUNT; i++) {
            arrayList.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList Query consumption time: " + (endTime - startTime));
    }

    /**
     * Test LinkedList performance
     */
    public static void linkedListQuery() {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < QUERY_COUNT; i++) {
            linkedList.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList Query consumption time: " + (endTime - startTime));
    }
}

result

ArrayList Insert elapsed time: 96
LinkedList Insert elapsed time: 1684
ArrayList Query consumption time: 8
LinkedList Query consumption time: It's been a long time, but I haven't finished it

conclusion

Although the bottom layer of ArrayList is array and the bottom layer of LinkedList is linked list, the insertion operation of ArrayList is indeed more efficient than that of LinkedList

Because the bottom layer of ArrayList uses elementdata = arrays copyOf(elementData, newCapacity); This is a native method, so it is more efficient

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

When the execution times were modified, the previous test was one million times, and now it is modified to 10000 times

ArrayList Insert elapsed time: 3
LinkedList Insert elapsed time: 2
ArrayList Query consumption time: 1
LinkedList Query consumption time: 48

It can be seen that when the execution times are small, the difference between the two insertion operations is not obvious, but the query operation is still faster in ArrayList

When the execution times are large, the insertion efficiency of ArrayList is higher than that of LinkedList

summary

ArrayList bottom layer is implemented by array, and LinkedList bottom layer is implemented by linked list

The query operation of ArrayList is faster than that of LinkedList

Theoretically, the insertion operation of ArrayList is slower than that of LinkedList

In fact: the insertion operation of ArrayList is faster than that of LinkedList

Because the bottom layer of ArrayList uses elementdata = arrays copyOf(elementData, newCapacity); This is a native method, so it is more efficient