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)是随机访问操作和增删操作的结合。增删快慢和随机访问能力强弱是说的相应的操作快慢，而不是说方法执行速度。

Answer 2

补充一下：
在看过1.8的代码后，发现ArrayList的get(index) 和 add(E)的时间复杂度确实是O(1), add(index,E)和remove(E)的时间复杂度我不太确定，没有任何遍历但都是用了System.arraycopy(elementData, index, elementData, index + 1, size - index); 这个方法；
而LinkedList的 add(E)的时间复杂度确实是O(1)，其余的get(index)、add(index,E)和remove(E)内部都是调用了node(index)方法复杂度O(n);
是不是通常说的只是get(index)和add(E)的比较，但是我听到的一直是增删比较快LinkedList，求解惑

Answer 3

题主，你可能把查找和增删的时间复杂度混到一起了。

• 仅对于按照索引位置查找，ArrayList 由数组实现，可以一步到位，因此时间复杂度是 O(1)，LinkedList 由链表实现，需要遍历链表，时间复杂度和元素所在位置有关，因此可以认为是 O(n)；
• 对于按照索引位置的增删操作，需要先查询出要增加或删除的元素位置，这个查询的时间复杂度和上述描述一致，但是对于增删操作本身，ArrayList 需要复制数组，复制的元素数和位置有关，时间复杂度可以粗略的认为是 O(n)，LinkedList 改变下个或上个位置的元素指向即可，因此时间复杂度是 O(1)；

Answer 4

1. System.arraycopy 底层做了循环，最好情况O(1) 最坏O(n)。就像上面说的挪位置
2. 如果你了解数组，和链表这两种数据结构话及它们在内存中的存储 就会明白了。
   数组在内存中是 连续存储的，只要知道其中一个元素的位置，那么其他元素的位置也就都知道了。
   链表在内存中是 随机存储的，它们之间的关联在于每个元素都保存了下一个元素的地址指针。所以就导致，我们要查找某一个元素时都需要从头节点开始依次查找
   下去，最坏的情况就是O(n)。