随风起飞 2021-09-29 13:40 采纳率: 100%
浏览 608
已结题

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条回答 默认 最新

  • yue_hu 2021-09-29 14:21
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(3条)

报告相同问题?

问题事件

  • 系统已结题 10月7日
  • 已采纳回答 9月29日
  • 创建了问题 9月29日

悬赏问题

  • ¥15 帮我解决一下膳食平衡的线性规划模型的数据实例
  • ¥40 万年历缺少农历,需要和阳历同时显示
  • ¥250 雷电模拟器内存穿透、寻基址和特征码的教学
  • ¥200 比特币ord程序wallet_constructor.rs文件支持一次性铸造1000个代币,并将它们分配到40个UTXO上(每个UTXO上分配25个代币),并设置找零地址
  • ¥15 关于Java的学习问题
  • ¥15 如何使用chatgpt完成文本分类任务?
  • ¥15 已知速度v关于位置s的等式,怎么转化为已知位置求速度v的等式
  • ¥15 我有个餐饮系统,用wampserver把环境配置好了,但是后端的网页却进去,是为什么,能不能帮远程一下?
  • ¥15 R运行没有名称为"species"的插槽对于此对象类"SDMmodelCV"
  • ¥20 基于决策树的数字信号处理,2ask 2psk 2fsk的代码,检查下报错的原因