1 overview

This article focuses on the similarities and differences between ArrayList and LinkedList, as well as the underlying implementation of both (environment OpenJDK 11.0.10).

2 The difference between the two

Before going into the details of their underlying implementations, let’s take a quick look at the similarities and differences.

2.1 similarities

• Both have been achievedListInterfaces, all inheritedAbstractList(LinkedListIndirect inheritance,ArrayListDirect inheritance)
• It’s all thread unsafe
• Have add delete check change method

2.2 the difference between

• Different underlying data structures:ArrayListBased on theObject[]Array,LinkedListBased on theLinkedList.NodeTwo-way linked list
• Random access efficiency is different:ArrayListRandom access can do thatO(1), because elements can be found directly by subscript, andLinkedListYou need to start with an ab initio pointer, timeO(n)
• The initialization operations are different:ArrayListDuring initialization, you need to specify an initialization capacity (default is 10), andLinkedListDon’t need
• Capacity:ArrayListWhen the length is insufficient to accommodate new elements, it is expanded, andLinkedListDon’t

3 ArrayListThe underlying

3.1 Basic Structure

Object[] array is used at the bottom level, and the member variables are as follows:

private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;
Copy the code

The default initialization capacity is 10, followed by two empty arrays for both the default constructor and the constructor with the initialization capacity:

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if(initialCapacity ! =0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

        this.elementData = EMPTY_ELEMENTDATA; }}public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

Here are some more important ones, including:

• add()
• remove()
• indexOf()/lastIndexOf()/contains()

3.2 add()

There are four add() methods:

• add(E e)
• add(int index,E e)
• addAll(Collection<? extends E> c)
• addAll(int index, Collection<? extends E> c

3.2.1 Single Elementadd()

Let’s look at add(E E) and add(int index,E E ment) :

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) {
        elementData = this.grow();
    }

    elementData[s] = e;
    this.size = s + 1;
}

public boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.size);
    return true;
}

public void add(int index, E element) {
    this.rangeCheckForAdd(index);
    ++this.modCount;
    int s;
    Object[] elementData;
    if ((s = this.size) == (elementData = this.elementData).length) {
        elementData = this.grow();
    }

    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    this.size = s + 1;
}
Copy the code

Add (E E) actually calls a private method, which is added directly to the end after determining whether it needs to be expanded. Add (int index,E Element) checks whether the subscript is valid. If it is valid, it determines whether it needs to be expanded, and then calls System. Arraycopy to copy the array.

The official documentation for System.arrayCopy is as follows:

There are five parameters:

• First argument: primitive array
• Second argument: the location where the original array needs to start copying
• Third parameter: destination array
• Fourth argument: copy to the start of the target array
• Fifth parameter: the number of copies required

In other words:

System.arraycopy(elementData, index, elementData, index + 1, s - index);
Copy the code

The index () function “moves back” the element after index, leaving space for index to insert.

3.2.2 addAll()

Let’s look at two addAll() :

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        System.arraycopy(a, 0, elementData, s, numNew);
        this.size = s + numNew;
        return true; }}public boolean addAll(int index, Collection<? extends E> c) {
    this.rangeCheckForAdd(index);
    Object[] a = c.toArray();
    ++this.modCount;
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        Object[] elementData;
        int s;
        if (numNew > (elementData = this.elementData).length - (s = this.size)) {
            elementData = this.grow(s + numNew);
        }

        int numMoved = s - index;
        if (numMoved > 0) {
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        }

        System.arraycopy(a, 0, elementData, index, numNew);
        this.size = s + numNew;
        return true; }}Copy the code

In the first addAll, it determines whether expansion is needed and then directly calls the target collection to add to the tail. In the second addAll, there are a few more steps because of an extra subscript:

• First determine whether the subscript is legal
• Then determine whether the capacity needs to be expanded
• Then calculate whether the array elements need to be “moved back”, i.eifThe inside of theSystem.arraycopy
• Finally, copy the target array to the specifiedindexlocation

3.2.3 capacity

The add() method above all involves expansion, which is also known as the grow method.

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private Object[] grow() {
    return this.grow(this.size + 1);
}

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            returnminCapacity; }}else {
        return newCapacity - 2147483639< =0? newCapacity : hugeCapacity(minCapacity); }}private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {
        throw new OutOfMemoryError();
    } else {
        return minCapacity > 2147483639 ? 2147483647 : 2147483639; }}Copy the code

Grow () first calculates the capacity to be expanded using newCapacity and then calls arrays.copyof to copy the old elements and overwrite the returned values into the original array. In newCapacity, there are two variables:

• newCapacity: The new capacity is 1.5 times the old capacity by default
• minCapacity: Minimum required capacity

If the minimum capacity is greater than or equal to the new capacity, one of the following situations occurs:

• Array initialized by default construct: returnsminCapacityAnd the maximum value of 10
• Overflow: Direct throwOOM
• Otherwise, return the minimum capacity value

If not, determine whether the new capacity has reached its maximum (MAX_ARRAY_SIZE is not used), return the new capacity if it has not, and call hugeCapacity if it has.

HugeCapacity also determines whether the minimum capacity is less than 0. If it is less than 0, throw OOM. Otherwise, it is judged by the maximum value (MAX_ARRAY_SIZE).

3.3 remove()

Remove () contains four methods:

• remove(int index)
• remove(Object o)
• removeAll()
• removeIf()

3.3.1 Single elementremove()

Remove (int index) and remove(Object O) :

public E remove(int index) {
    Objects.checkIndex(index, this.size);
    Object[] es = this.elementData;
    E oldValue = es[index];
    this.fastRemove(es, index);
    return oldValue;
}

public boolean remove(Object o) {
    Object[] es = this.elementData;
    int size = this.size;
    int i = 0;
    if (o == null) {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (es[i] == null) {
                break; } ++i; }}else {
        while(true) {
            if (i >= size) {
                return false;
            }

            if (o.equals(es[i])) {
                break; } ++i; }}this.fastRemove(es, i);
    return true;
}
Copy the code

The logic of remove(int index) is relatively simple, first check the validity of subscript, then save the value of remove, and call fastRemove() to remove, while in remove(Object O), directly traverse the array, and determine whether there is a corresponding element. Return false if it doesn’t exist, or call fastRemove() if it does, and return true.

Let’s look at fastRemove() :

private void fastRemove(Object[] es, int i) {
    ++this.modCount;
    int newSize;
    if ((newSize = this.size - 1) > i) {
        System.arraycopy(es, i + 1, es, i, newSize - i);
    }

    es[this.size = newSize] = null;
}
Copy the code

If it is the last one, no need to move it. If it is not, call System. arrayCopy to “move” the array forward by 1 bit, and set the extra value to NULL.

3.3.2 rainfall distribution on 10-12removeAll()

public boolean removeAll(Collection
        c) {
    return this.batchRemove(c, false.0.this.size);
}

boolean batchRemove(Collection<? > c,boolean complement, int from, int end) {
    Objects.requireNonNull(c);
    Object[] es = this.elementData;

    for(intr = from; r ! = end; ++r) {if(c.contains(es[r]) ! = complement) {int w = r++;

            try {
                for(; r < end; ++r) {
                    Object e;
                    if(c.contains(e = es[r]) == complement) { es[w++] = e; }}}catch (Throwable var12) {
                System.arraycopy(es, r, es, w, end - r);
                w += end - r;
                throw var12;
            } finally {
                this.modCount += end - w;
                this.shiftTailOverGap(es, w, end);
            }

            return true; }}return false;
}
Copy the code

RemoveAll actually calls batchRemove(). In batchRemove(), there are four arguments with the following meanings:

• Collection<? > c: Target set
• boolean complement: If the value is specifiedtrueRepresents the reserved array contained in the target collectioncElement in, iffalseTo remove the array contained in the target collectioncThe elements in the
• from/end: Range, closed on the left and open on the right

So (c,false,0,this.size) is passed to remove the elements in the array that are in the target set C. The following is a brief description of the implementation steps:

• The null call operation is performed first
• Then find the first element that meets the requirement (in this case, find the first element that needs to be deleted)
• The index of the last element in the deleted array is also recordedw
• try/catchIt’s a protective act, becausecontains()inAbstractCollectionIn the implementation ofIteratorHere,catchCall after exceptionSystem.arraycopyCauses the already processed elements to “move” to the front
• Finally, it increases the number of modifications and callsshiftTailOverGapThis method will be explained later

3.3.3 removeIf()

public boolean removeIf(Predicate<? super E> filter) {
    return this.removeIf(filter, 0.this.size);
}

boolean removeIf(Predicate<? super E> filter, int i, int end) {
    Objects.requireNonNull(filter);
    int expectedModCount = this.modCount;

    Object[] es;
    for(es = this.elementData; i < end && ! filter.test(elementAt(es, i)); ++i) { }if (i < end) {
        int beg = i;
        long[] deathRow = nBits(end - i);
        deathRow[0] = 1L;
        ++i;

        for(; i < end; ++i) {
            if(filter.test(elementAt(es, i))) { setBit(deathRow, i - beg); }}if (this.modCount ! = expectedModCount) {throw new ConcurrentModificationException();
        } else {
            ++this.modCount;
            int w = beg;

            for(i = beg; i < end; ++i) {
                if(isClear(deathRow, i - beg)) { es[w++] = es[i]; }}this.shiftTailOverGap(es, w, end);
            return true; }}else if (this.modCount ! = expectedModCount) {throw new ConcurrentModificationException();
    } else {
        return false; }}Copy the code

If (I >=end) {if (I >=end) {if (I

• Record start subscriptbeg
• deathRowIs an array of tokens of length(end-i-1)>>6 + 1, frombegInitially, the subscript is marked (called) if an element meets the criteriasetBit)
• After the mark is deleted, the so-called deletion actually means that the following elements that do not meet the conditions are moved tobegAfter that
• callshiftTailOverGapProcess the trailing element
• returntrueIs displayed, indicating that the elements matching the conditions exist and are deleted

We doshiftTailOverGap()

RemoveAll () and removeIf() both involve shiftTailOverGap().

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, this.size - hi);
    int to = this.size;

    for(int i = this.size -= hi - lo; i < to; ++i) {
        es[i] = null; }}Copy the code

This method moves the element in the ES array forward by hi-Lo bits and sets the extra element at the end of the move to NULL.

3.4 indexOf()A series of

Include:

• indexOf()
• lastIndexOf()
• contains()

3.4.1 trackindexOf

public int indexOf(Object o) {
    return this.indexOfRange(o, 0.this.size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = this.elementData;
    int i;
    if (o == null) {
        for(i = start; i < end; ++i) {
            if (es[i] == null) {
                returni; }}}else {
        for(i = start; i < end; ++i) {
            if (o.equals(es[i])) {
                returni; }}}return -1;
}
Copy the code

IndexOf () is a wrapped method that calls the internal indexOfRange(). The logic is simple: first check whether the value to be searched is empty, if not, use equals(), otherwise use ==, return subscript if found, otherwise return -1.

3.4.2 contains()

Contains () is actually a wrapper around indexOf() :

public boolean contains(Object o) {
    return this.indexOf(o) >= 0;
}
Copy the code

The indexOf() method is called to determine whether the index returned is greater than or equal to 0, if it exists, otherwise it does not.

Rule 3.4.3lastIndexOf()

The lastIndexOf() implementation is similar to indexOf(), except that it starts at the tail and calls lastIndexOfRange() internally:

public int lastIndexOf(Object o) {
    return this.lastIndexOfRange(o, 0.this.size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = this.elementData;
    int i;
    if (o == null) {
        for(i = end - 1; i >= start; --i) {
            if (es[i] == null) {
                returni; }}}else {
        for(i = end - 1; i >= start; --i) {
            if (o.equals(es[i])) {
                returni; }}}return -1;
}
Copy the code

4 LinkedListThe underlying

4.1 Basic Structure

Let’s first look at the member variables inside:

transient int size;
transient LinkedList.Node<E> first;
transient LinkedList.Node<E> last;
private static final long serialVersionUID = 876323262645176354L;
Copy the code

One for length, one for head pointer and one for tail pointer.

Linkedlist. Node is implemented as follows:

private static class Node<E> {
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev; }}Copy the code

You can see that the LinkedList is actually implemented based on a double-linked list.

Here are some more important ones, including:

• add()
• remove()
• get()

4.2 add()

The add() method consists of six:

• add(E e)
• add(int index,E e)
• addFirst(E e)
• addLast(E e)
• addAll(Collection<? extends E> c)
• addAll(int index, Collection<? extends E> c)

2linkFirst/linkLast/linkBeforeImplementation of theadd()

Let’s take a look at the four simple add() :

public void addFirst(E e) {
    this.linkFirst(e);
}

public void addLast(E e) {
    this.linkLast(e);
}

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

public void add(int index, E element) {
    this.checkPositionIndex(index);
    if (index == this.size) {
        this.linkLast(element);
    } else {
        this.linkBefore(element, this.node(index)); }}Copy the code

LinkLast (), linkFirst(), and linkBefore() are all methods that link elements to the end or head of the list. Or before a node in a linked list:

void linkLast(E e) {
    LinkedList.Node<E> l = this.last;
    LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
    this.last = newNode;
    if (l == null) {
        this.first = newNode;
    } else{ l.next = newNode; } + +this.size;
    ++this.modCount;
}

private void linkFirst(E e) {
    LinkedList.Node<E> f = this.first;
    LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
    this.first = newNode;
    if (f == null) {
        this.last = newNode;
    } else{ f.prev = newNode; } + +this.size;
    ++this.modCount;
}

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

The implementation is basically the same, one to add to the tail, one to add the header, and one to insert to the front. In addition, all three have the following operations at the end of the method:

++this.size;
++this.modCount;
Copy the code

The first represents the number of nodes plus one, while the second represents the number of changes to the list plus one.

For example, at the end of the unlinkLast method, there is code like this:

--this.size;
++this.modCount;
Copy the code

The unlinkLast operation removes the last node. When the number of nodes is decreased by 1, the number of changes to the list is increased by 1.

On the other hand, the list insertion operation usually needs to find the list position, but in none of the three link methods, there is no code for the for loop to find the insertion position. Why is this?

LinkFirst () and linkLast() do not need to traverse to find the insertion position because they hold the first and last Pointers. LinkBefore () does, however, need to find the insertion position. LinkBefore () does not have an insertion position/subscript. Instead, there is only one element value and one successor node. In other words, the successor node is the insertion position obtained through a loop. For example, the following code is called:

this.linkBefore(element, this.node(index));
Copy the code

You can see that in this.node(), a subscript is passed in and a successor node is returned, so the traversal is completed in this method:

LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) {
        x = this.first;

        for(i = 0; i < index; ++i) {
            x = x.next;
        }

        return x;
    } else {
        x = this.last;

        for(i = this.size - 1; i > index; --i) {
            x = x.prev;
        }

        returnx; }}Copy the code

The first step is to determine “which side” the subscript is on, starting from the ab initio pointer if it is near the head and traversing backwards from the tail pointer if it is near the tail.

4.2.2 Traversal implementationaddAll()

public boolean addAll(Collection<? extends E> c) {
    return this.addAll(this.size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    this.checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) {
        return false;
    } else {
        LinkedList.Node pred;
        LinkedList.Node succ;
        if (index == this.size) {
            succ = null;
            pred = this.last;
        } else {
            succ = this.node(index);
            pred = succ.prev;
        }

        Object[] var7 = a;
        int var8 = a.length;

        for(int var9 = 0; var9 < var8; ++var9) {
            Object o = var7[var9];
            LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
            if (pred == null) {
                this.first = newNode;
            } else {
                pred.next = newNode;
            }

            pred = newNode;
        }

        if (succ == null) {
            this.last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        this.size += numNew;
        ++this.modCount;
        return true; }}Copy the code

First, you can see that both addAll actually call the same method. The steps are as follows:

• First of all bycheckPositionIndexDetermine whether the subscript is valid
• Then the target set is converted toObject[]An array of
• Do some special processing, make a judgmentindexIs the range to insert in the middle or at the end
• forLoop through the target array and insert into the linked list
• Change the length of the node and return

4.3 remove()

Like add(), remove includes:

• remove()
• remove(int index)
• remove(Object o)
• removeFirst()
• removeLast()
• removeFirstOccurrence(Object o)
• removeLastOccurrence(Object o)

Of course, there are two removeAll and removeIf methods, but they are actually superclass methods, so I won’t analyze them here.

4.3.1 unlinkFirst()/unlinkLast()Implementation of theremove()

Remove (), removeFirst(), and removeLast() are actually removed by calling unlinkFirst()/unlinkLast(), where remove() is just an alias of removeFirst() :

public E remove(a) {
    return this.removeFirst();
}

public E removeFirst(a) {
    LinkedList.Node<E> f = this.first;
    if (f == null) {
        throw new NoSuchElementException();
    } else {
        return this.unlinkFirst(f); }}public E removeLast(a) {
    LinkedList.Node<E> l = this.last;
    if (l == null) {
        throw new NoSuchElementException();
    } else {
        return this.unlinkLast(l); }}Copy the code

UnlinkFirst ()/unlinkLast() :

private E unlinkFirst(LinkedList.Node<E> f) {
    E element = f.item;
    LinkedList.Node<E> next = f.next;
    f.item = null;
    f.next = null;
    this.first = next;
    if (next == null) {
        this.last = null;
    } else {
        next.prev = null; } -this.size;
    ++this.modCount;
    return element;
}

private E unlinkLast(LinkedList.Node<E> l) {
    E element = l.item;
    LinkedList.Node<E> prev = l.prev;
    l.item = null;
    l.prev = null;
    this.last = prev;
    if (prev == null) {
        this.first = null;
    } else {
        prev.next = null; } -this.size;
    ++this.modCount;
    return element;
}
Copy the code

In these two unlinks, since the positions of the head and tail Pointers have been saved, they can be removed directly in O(1). Finally, the length of the node is reduced by 1, the number of changes is increased by 1, and the old element is returned.

4.3.2 unlink()Implementation of theremove()

Remove (int index) remove(Object O) removeFirstOccurrence(Object O) removeLastOccurrence(Object O)

public E remove(int index) {
    this.checkElementIndex(index);
    return this.unlink(this.node(index));
}

public boolean remove(Object o) {
    LinkedList.Node x;
    if (o == null) {
        for(x = this.first; x ! =null; x = x.next) {
            if (x.item == null) {
                this.unlink(x);
                return true; }}}else {
        for(x = this.first; x ! =null; x = x.next) {
            if (o.equals(x.item)) {
                this.unlink(x);
                return true; }}}return false;
}

public boolean removeFirstOccurrence(Object o) {
    return this.remove(o);
}

public boolean removeLastOccurrence(Object o) {
    LinkedList.Node x;
    if (o == null) {
        for(x = this.last; x ! =null; x = x.prev) {
            if (x.item == null) {
                this.unlink(x);
                return true; }}}else {
        for(x = this.last; x ! =null; x = x.prev) {
            if (o.equals(x.item)) {
                this.unlink(x);
                return true; }}}return false;
}
Copy the code

RemoveFirstOccurrence (Object O) = remove(Object O) removeFirstOccurrence(int index) = remove(int index) Then find the node by subscript and unlnk.

In remove(Object O), it is necessary to check whether the value of the element is null first. The effect of the two loops is actually equivalent, removing the first element encountered with the same value as the target. In removeLastOccurrence(Object O), the code is basically the same, except that remove(Object O) traverses from the beginning pointer, while removeLastOccurrence(Object O) traverses from the tail pointer.

Unlink (); unlink(); unlink(); unlink(); unlink();

E unlink(LinkedList.Node<E> x) {
    E element = x.item;
    LinkedList.Node<E> next = x.next;
    LinkedList.Node<E> prev = x.prev;
    if (prev == null) {
        this.first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        this.last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    --this.size;
    ++this.modCount;
    return element;
}
Copy the code

The implementation logic is similar to unlinkFirst()/unlinkLast(), delete in O(1), which only contains some simple special operations, finally reduce the length of the node by 1, and increase the number of changes by 1, and finally return the old value.

4.4 get()

The get method is relatively simple and provides three external methods:

• get(int index)
• getFirst()
• getLast()

Where getFirst() and getLast() save the first and last Pointers, then return O(1) :

public E getFirst(a) {
    LinkedList.Node<E> f = this.first;
    if (f == null) {
        throw new NoSuchElementException();
    } else {
        returnf.item; }}public E getLast(a) {
    LinkedList.Node<E> l = this.last;
    if (l == null) {
        throw new NoSuchElementException();
    } else {
        returnl.item; }}Copy the code

While get(int index) takes O(n) time:

public E get(int index) {
    this.checkElementIndex(index);
    return this.node(index).item;
}
Copy the code

This.node () = this.node(); this.node() = this.node(); this.node() = this.node();

5 concludes

• ArrayListBased on theObject[]The implementation,LinkedListBased on double linked list implementation
• ArrayListRandom access is more efficient thanLinkedList
• LinkedListProvides thanArrayListMore insertion methods, and head-to-tail insertion efficiency is higherArrayList
• The methods for deleting elements are not exactly the same,ArrayListOffers uniqueremoveIf()And theLinkedListOffers uniqueremoveFirstOccurrence()As well asremoveLastOccurrence()
• ArrayListtheget()Method is alwaysO(1)And theLinkedListonlygetFirst()/getLast()forO(1)
• ArrayListThe two core methods aregrow()As well asSystem.arraycopy, the former is the capacity expansion method, the default is 1.5 times capacity expansion, the latter is the copy array method, is anativeMethod, insert, delete, and so on
• LinkedListMany of these methods need to be evaluated from head to tail to create comparisonsArrayListSimple, no initialization is required, and no capacity expansion is involved

Appendix: An experiment on insertion and deletion

LinkedList is generally considered to be more efficient than ArrayList when it comes to insert and delete, but this is not the case. Here is a small experiment to test insert and delete times.

Related instructions:

• Number of tests: 1000
• Array length: 4000 W, 40W, 4000W
• Test array: randomly generated
• Insert and delete subscripts: randomly generated
• Result value: average time of 1000 insertions and deletions

Code:

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args){
        int len = 40 _0000;
        Random random = new Random();
        List<Integer> list = Stream.generate(random::nextInt).limit(len).collect(Collectors.toList());
        LinkedList<Integer> linkedList = new LinkedList<>(list);
        ArrayList<Integer> arrayList = new ArrayList<>(list);

        long start;
        long end;

        double linkedListTotalInsertTime = 0.0;
        double arrayListTotalInsertTime = 0.0;

        int testTimes = 1000;
        for (int i = 0; i < testTimes; i++) {
            int index = random.nextInt(len);
            int element = random.nextInt();
            start = System.nanoTime();
            linkedList.add(index,element);
            end = System.nanoTime();
            linkedListTotalInsertTime += (end-start);

            start = System.nanoTime();
            arrayList.add(index,element);
            end = System.nanoTime();
            arrayListTotalInsertTime += (end-start);
        }
        System.out.println("LinkedList average insert time:"+linkedListTotalInsertTime/testTimes+" ns");
        System.out.println("ArrayList average insert time:"+arrayListTotalInsertTime/testTimes + " ns");

        linkedListTotalInsertTime = arrayListTotalInsertTime = 0.0;

        for (int i = 0; i < testTimes; i++) {
            int index = random.nextInt(len);
            start = System.nanoTime();
            linkedList.remove(index);
            end = System.nanoTime();
            linkedListTotalInsertTime += (end-start);

            start = System.nanoTime();
            arrayList.remove(index);
            end = System.nanoTime();
            arrayListTotalInsertTime += (end-start);
        }
        System.out.println("LinkedList average delete time:"+linkedListTotalInsertTime/testTimes+" ns");
        System.out.println("ArrayList average delete time:"+arrayListTotalInsertTime/testTimes + " ns"); }}Copy the code

When the array length is 4000, output is as follows:

LinkedList Average Insert Time :4829.938 NS ArrayList Average Insert Time :745.529 NS LinkedList Average delete Time :3142.988 NS ArrayList Average Delete Time :1703.76 nsCopy the code

If the array length is 40W (-xmx512m -xms512m), the output is as follows:

LinkedList Average Insert Time :126620.38 NS ArrayList Average Insert Time :25955.014 ns LinkedList Average delete Time :119281.413 ns ArrayList Average Delete Time :25435.593 nsCopy the code

To change the array length to 4000W (parameter -xmx16g-xMS16g), the time is as follows:

LinkedList average insert time:5.6048377238E7 ns
ArrayList average insert time:2.5303627956E7 ns
LinkedList average delete time:5.4753230158E7 ns
ArrayList average delete time:2.5912990133E7 ns
Copy the code

Although this experiment has some limitations, it also proves that the insert and delete performance of ArrayList is not worse than that of LinkedList. In fact, as you can see from the source code (see below), ArrayList inserts and deletes take most of the time in System.arrayCopy and LinkedList takes most of the time in this.node(), both of which take O(n) time.

Arraycopy inserts and deletes faster than LinkedList. Arraycopy is faster than LinkedList’s for loop. Because the insertion/deletion position in the LinkedList is found through this.node(), this method is implemented using a simple for loop (of course, the bottom layer determines which side it is on first, starting at the head if it is near the head, starting at the tail if it is near the tail). Compared to the native C++ method implementation of system.arraycopy, it can be slower than C++, resulting in a speed difference.

If you think the article looks good, please like it.

At the same time, welcome to pay attention to wechat public number: Lingzhi Road.