JavaのLinkedListとArrayListの追加の方法の違い

Java 11.0.2
一般的にListへの要素の追加はLinkedListは前へのポインタと後ろへのポインタを付け替えるだけ、ArrayListはメモリへの再割り当てが行われると言われています。（言われてますよね？）
中身がどのように実装されているか気になったのでJavaのソースを調べてみました。

LinkedListから

add

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

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

indexは添字です。
sizeってのはListのサイズを表してます。
サイズは添字+1なので、一番最後につけるときは単純に最後のポインタの次に追加される要素を設定するだけのようです。
翻って、途中に追加する場合は以下のように指定のノードの前に追加するようです。指定のノードの前の要素を新要素に、新要素の次の要素を指定のノードに設定する実装です。

linkBefore

    /**
     * Inserts element e before non-null Node succ.
     */
    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++;
    }

で、気になるnode(index)の実装が以下

node

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    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;
            return x;
        }
    }

LinkedList.get(int index)の実装と同じように指定のIndexへたどり着くまで一つずつループしてます。
Indexが最大値の半分以上か、以下かを判断してループの効率化は行っているようです。
見るに、100万の要素があった場合、50万に追加するのが一番パフォーマンスが悪いみたいです。

続いてArrayList

add

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

this.elementというのはArrayListの実態の配列です。sizeというのが実態の配列のサイズです。
追加したときにsize = s + 1;してるんで、常にこのifは真になる気もしますが。。。
elementDataを戻しているgrow()が以下です。

grow

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

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

    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

SystemクラスやArraysクラスを使って配列をコピーして、その隙間に新規要素を差し込んでいるようです。
1から10までの要素があって、5番目に新要素を差し込もうとすると元の配列+1のサイズのコピー配列を作成後、6から11番目に元の配列の5から10番目をコピーして、5番目に新要素を入れている実装です。

ちょっと調べて気になったのでまとめてみました。