随风起飞
2021-09-29 13:40
采纳率: 100%
浏览 198

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

在看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;
        }
    }
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

4条回答 默认 最新

相关推荐 更多相似问题