The test results

Without further ado, let’s start with the test results. The authors compared the time taken to find 100,000 elements by inserting them at the head, tail, and middle of ArrayList and LinkedList. Here is the result. The head and middle inserts were tested on tables that already had 100,000 elements.)

	insert	To find the
ArrayList tail	26ms	4ms
The ArrayList head	2887ms	3ms
Among the ArrayList	1936ms	4ms
LinkedList tail	28ms	9ms
LinkedList head	15ms	11ms
Among the LinkedList	12310ms	11387ms

The test results

• The lookup performance of an ArrayList is absolutely superb, no matter where the elements are being queried
• With the exception of tail-insertions (the further back the insertion, the better), arrayLists perform poorly at other locations
• LinkedList is great for top and bottom lookup and insert performance, but in the middle it’s nowhere near as good and not on the same order of magnitude as ArrayList

Source code analysis

We put ArrayList and LinkedList in Java as a kind of implementation of sequential list and bidirectional list respectively, so before source analysis, we will briefly review the key concepts of sequential list and bidirectional list in data structure

• Sequence table: You need to apply for contiguous memory space to store elements. You can directly find the logical location of elements by physical location in memory. Inserting or deleting an element in the middle of a sequence requires moving all elements after that element forward or backward.
• Bidirectional linked list: there is no need to acquire contiguous memory space to store elements, and the preceding and subsequent elements need to be found by the pointer to the beginning and end of the element. (To find elements, you need to traverse the list from beginning to end until the target element is found.) Inserting or deleting elements in a bidirectionally linked list does not require moving the elements, just changing the leading and trailing Pointers of the related elements.

So we subconsciously think that arrayLists are fast to find, slow to add and delete. LinkedList is slow to find, fast to add and delete. But is this really the case? Let’s take a look.

The test program

The test program code is basically no nutrition, I will not post it here, but the results of the program should be posted to facilitate analysis one by one.

The results

Insert 100000 elements into the end of ArrayList: 26ms Insert 100000 elements into the end of ArrayList: 28ms Insert 100000 elements into the head of ArrayList: 859ms Insert 100000 elements into the head of ArrayList: 26ms Insert 100000 elements into the end of ArrayList: 28ms Insert 100000 elements into the head of ArrayList: 859ms Insert 100000 elements into the head of ArrayList: 15ms ArrayList: 1848ms LinkedList: 18981ms ArrayList header: 7ms LinkedList header 100000 elements: 11ms ArrayList tail 100000 elements: 12ms LinkedList tail 100000 elements: 9ms ArrayList middle 100000 elements: 13ms Time to read 100000 elements in the middle of LinkedList: 11387ms

ArrayList is inserted at the end

The source code

The add (E, E) method

    public boolean add(E e) {
        // Check whether the capacity needs to be expanded
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // Add elements directly to the tail
        elementData[size++] = e;
        return true;
    }
Copy the code

As you can see, the end of the ArrayList can be inserted directly without additional operations.

Insert the end of LinkedList

The source code

The header and tail nodes are defined in the LinkedList

    /** * Pointer to first node. */
    transient Node<E> first;

    /** * Pointer to last node. */
    transient Node<E> last;
Copy the code

The add(E E) method, which calls the linkLast(E E) method

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

LinkLast (E E) method, you don’t need to go through the whole list from the beginning when inserting the tail, because the tail has been saved in advance, so you can insert the element directly after the tail

    /** * Links e as last element. */
    void linkLast(E e) {
        // Save the original endpoint
        final Node<E> l = last;
        // Create a new node whose head points to last
        final Node<E> newNode = new Node<>(l, e, null);
        // Set the end node to newNode
        last = newNode;
        if (l == null)
            first = newNode;
        else
            // Modify the old tail to point to the new tail
            l.next = newNode;
        size++;
        modCount++;
    }
Copy the code

conclusion

ArrayList and LinkedList perform almost identically for tail inserts

ArrayList header inserted

The source code

Add (int index, E Element) method, you can see that the element is moved by calling the system’s array copy method. So, the further forward you insert, the more elements you have to move

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

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // Copy all elements at the beginning of index to the beginning of index+1.
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // Insert elements
        elementData[index] = element;
        size++;
    }
Copy the code

LinkedList header inserted

The source code

The add(int index, E element) method checks whether the insertion is at the end, if it is called linkLast(), otherwise it is called linkBefore(), then does it really need to start all over again? Let’s take a look

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

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

The node() method is the key. This function is used to find the index of the element. If the index is less than half of size, the node() method is used to find the index of the element. I’m just going to start from the beginning. Otherwise, traverse from the tail. As you can see, for LinkedList, the closer the elements of the operation are to the center, the less efficient they become

    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            returnx; }}Copy the code

The job of this function is simply to insert elements into their respective positions, and the key work is done in the Node () method

    void linkBefore(E e, Node<E> succ) {
        // assert succ ! = null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
Copy the code

conclusion

• For LinkedList, head insert time and tail insert time are O(1)
• But for an ArrayList, each insertion of the header requires a size-1 element shift, which is surprisingly efficient
• But ArrayList is nearly 10 times faster than LinkedList if all inserts are in the middle

ArrayList, LinkedList search

• There’s nothing to be said for an ArrayList, no matter where it’s located, it’s directly indexed to the element, order 1 time.
• For LinkedList lookups, the core method is the node() method mentioned above, so head-to-tail lookups are extremely fast and inefficient as you move closer to the middle

digression

The first time in nuggets wan-blog, hope to share some interesting knowledge to everyone!