Java ArrayList和LinkedList的时间复杂度的问题

Question

在看ArrayList和LinkedList比较的时候，都说前者查找快，后者增删快，在（JDK1.8）看到add(int index, E element)方法时 发现 ArrayList实现中采用了System.arraycopy 没有使用任何循环，那它的时间复杂度不是应该是O(1)吗？但网上说它的时间复杂度是O(n) ,难道System.arraycopy本身的时间复杂度是O(n)?

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++;
 }

另外，LinkedList的add(int index, E element)方法时，看到for循环遍历，那它的时间复杂度不是应该是O(n)吗？那我们通常所说的ArrayList和LinkedList比较的时候，都说前者查找快，后者增删快是指什么条件下呢？

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

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(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;
        }
    }

Answer 1

数组是一块连续的内存，System.arraycopy(elementData, index, elementData, index + 1, size - index)为了挪一个位置给新元素，其底层实现是把index到size的元素一个个往后挪，有多少个元素就需要挪多少次，所以时间复杂度是O(n).
ArrayList查询快是说其随机访问的能力强，就像get(index)其实就是直接访问数组的index下标处的元素，而LinkedList则不然，你也看到了，LinkedList需要遍历才能找到index的位置，所以较ArrayList慢。。
LinkedList增删快是指其移除数据的能力强，只需要断开前后链就行，而ArrayList则需要通过System.arraycopy挪动元素位置把移除的位置覆盖掉以保证数组容器完整。
LinkedList的add(int index, E element)不是O(1)不表示其增删能力差，而是因为其随机访问能力差
你要把方法和操作分开来看，增删是一个操作，随机访问也是一个操作。并不是说add(int index, E element)就表示他仅有一个增删操作，add(int index, E element)是随机访问操作和增删操作的结合。增删快慢和随机访问能力强弱是说的相应的操作快慢，而不是说方法执行速度。