首页 > 试题广场 >

下面程序的运行结果（） &nbs...

[单选题]

下面程序运行完之后，t2与t3的关系为（）

        Object obj=new Object();
        List aList=new ArrayList();
        List bList=new LinkedList();
        
        long t1=System.currentTimeMillis();
        for(int i=0;i<50000;i++){
            aList.add(0,obj);
        }
        long t2=System.currentTimeMillis()-t1;
        
        t1=System.currentTimeMillis();
        for(int i=0;i<50000;i++){
            bList.add(0,obj);
        }
        long t3=System.currentTimeMillis()-t1;

```
t2
```
```
t2=t3
```
```
不确定
```
```
t2>t3
```

查看正确选项

silencewmy

ArrayList内部是动态数组实现，在增加空间时会复制全部数据到新的容量大一些的数组中。而LinkedList内部为双向链表，可以按需分配空间，扩展容量简单，因此LinkedList用时少。

发表于 2019-03-17 00:33:26 回复(8)

越刷题越幸运

List aList=newArrayList();

List bList=newLinkedList();

aList.add(0,obj); //0代表下标，obj代表对象。每个对象都插入到下标0的位置。

bList.add(0,obj);

此题考察的是ArrayList和LinkedList的特征：同样是新增5000个对象，LinkedLIst比ArrayList更快。

ArrayList：增删慢，查询快。

由于是数据组实现，需要连续的内存空间，如果删除数组中间的值，为了保证下标的有效性，需要将后面的数据往前移，所以删除慢。

当插入A对象到B对象的前面时，需要将B对象和B对象之后的所有对象后移一位，再插入A对象。所以插入慢。

数组的大小是固定的，如果数组满了，需要重新分配空间，new一个新数组并copy旧数据之后再增加新数据，所以增加慢。

因为是连续内存空间，可以通过下标查询数据，所以查询快。

LInkedList：增删快，查询慢。

由于是链表实现，当前节点的next指向下一个节点，prev指向上一个节点，不需要连续的内存空间，所以增删快。

因为不是连续内存空间，所以不能使用下标查询，只能通过next遍历，所以查询慢。

编辑于 2019-09-14 18:43:47 回复(4)

去冰

粗心了，没注意到有aList和bList。以为两次for循环都是操作的alist。 aList是ArrayList(add慢)， bList是LinkedList（add快）。答案明了。

发表于 2019-03-14 16:54:29 回复(0)

做错就掌嘴

有图有真相：

ArrayList 容量不够需要扩容，依次扩容1.5倍，并且插入数据需要用到数组的copy，Linklist 不需要扩容，插入仅需要链表擅长的插入操作即可，故LinkList的操作时间低。

但是如果讲究尾部插入的话，数据量小的情况下可能难分伯仲，但是在插入数据量大的情况下，ArrayList的效率是要高于LinkList的，因为，数据量大之后，扩容不是很频繁，仅需要尾部插入即可，但是LinkList需要每次进行链表节点指针的指向调整操作，所以大量数据的尾部插入，ArrayList的效率是要高于LinkList的，下图是数据量较大时的比较：

如有错误欢迎指出，必当虚心改正~

发表于 2020-12-08 12:43:12 回复(2)

MountainsZhu

关于linkedlist和arraylist的插入速度不能一棒子打死。如果都是从尾部插入，即直接add数据，在数据量大的时候应该arraylist要快一点，因为后面的1.5倍扩容会随着数据量增大而越来越慢(0.5倍的量变大了)，但是就单个插入操作来说数组还是比双向链表快一些的。数据量小就差不多了。此题是头插，就大不一样了，双向链表头插时间复杂度是O(1)，而数组要先把数全往后挪一下再将值放在0位置，就算不考虑扩容，时间复杂度也是O(n)，所以这时候链表要比数组快的多。

发表于 2021-03-07 18:07:48 回复(0)

诸葛小愚

粗心看成尾插法了。。。

https://juejin.im/post/5c7dd5ece51d457cb60884d9?tdsourcetag=s_pctim_aiomsg

发表于 2019-04-10 22:59:28 回复(4)

谁给我offer谁就是大厂

说实话，排前面的评论说的或多或少都有问题，因为他们都默认，只要是插入ArrayList就一定比LinkedList慢。原因也很简单，ArrayList插入元素会涉及到扩容，如果是指定位置插入，还可能会引起数组元素的大面积移动，而LinkedList只需要改变指针指向就行。但是这种认知是错的。但本题也确实应该选D。下面给大家介绍原因：

在这道题所给的场景中是符合LinkedList比ArrayList快这个场景的。首先本题中并未声明ArrayList的初始容量。所以在50000次的插入中就一定会涉及到数组的扩容。其次，因为add方法中指明了插入下标为0，所以这是一个头插的插入。头插，尾插，中间插这三个模式中，ArrayList表现最糟糕的就是头插。因为每次头插都会涉及到当前数组所有元素的后移。只要是头插，数据量越大，ArrayList的表现就越糟糕。这是本题应该选D的原因。

如果不是头插而是中间插入。代码如下：

//        测试arraylist与linkedlist的插入性能
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        Random random = new Random();

        System.out.println("ArrayList开始插入"+LocalTime.now());
        for (int i=0;i<100000;i++){
            arrayList.add(random.nextInt(arrayList.size()), i); /*测试中间插入*/
        }
        System.out.println("ArrayList插入结束"+LocalTime.now());

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);

        System.out.println("LinkedList开始插入"+LocalTime.now());
        for (int i=0;i<100000;i++){
            linkedList.add(random.nextInt(linkedList.size()), i); /*测试中间插入*/
        }
        System.out.println("LinkedList插入结束"+LocalTime.now());

测试结果：

。十万数据量的中间插入，ArrayList仅耗费353毫秒，而LinkedList花费了11秒。原因是因为LinkedList每次中间插入都要进行时间复杂度为On的遍历，并且LinkedList还在维护内部的Node节点和指针变量，这都会给他带来额外的性能开销，数据量越大，额外的性能开销也就越大，所以中间插入时，数据量越大，LinkedList与ArrayList的差距也就越大。

尾插。尾插中LinkedList和ArrayList都有一个名为lastIndexOf的方法。如果我们直接调用只穿入要添加的数值的add方法，其实也是尾插。测试尾插时，我把循环次数调到了100万次。先给大家说结果，ArrayList略优于LinkedList。如图：。我前面说过，LinkedList维护了Node节点和指点，这会给他带来额外的性能开销。所以当数据量足够大时，LinkedList就会因为这个原因导致性能不如ArrayList。但是在尾插法的场景下，即便是把循环调到1000万次，他们的差距也很小，所以头插和中间插才是他们主要的性能差距和可比较的点。

发表于 2022-08-14 12:04:35 回复(0)

牛客318481161号

这个题最后既没有输出也没有返回，怎么确定运行结果就一定是什么，虽然知道考点，但是答案总觉得有问题

发表于 2020-11-06 08:33:25 回复(1)

开始冒险之旅

LinkedList：是链式结构实现，插入删除快。

ArrayList：是数组结构实现，检索速度快。

对于ArrayList：

arr<=>数组查询快！！本质上是【数组】，所以检索速度快！
末尾插入，删除效率高，插入，删除位置越靠前，效率越低，向最前插入，删除效率最低。

对于LinkList：

插入，删除速度较快，而且位置对插入，删除效率影响不大。
本质上是链表

发表于 2020-12-05 16:04:22 回复(0)

稳稳201907111504894

直接插入数据，往数组末尾连续加，速度比链表快。但是插入的数据量太大，涉及到数组扩容，所以ArrayList耗时多

发表于 2019-09-25 00:06:51 回复(3)

郭乾亮

ArrayList<T>底层是动态数组结构:查询快,增(add)删慢;

LinkedList<T>底层是链表结构:查询慢,增(add)删块。

发表于 2021-07-16 19:48:16 回复(0)

许你清安L

数组列表头插，会移动数据链表列表投插，不存在移动数据操作，更快

发表于 2021-06-08 22:52:23 回复(0)

DaMeng的牛客网账户

这道题考察了ArrayList与LinkedList的特性，ArrayList底层是一个具有扩容机制的数组，1.7为饿汉式，1.8为懒汉式，数组会分配一块连续的内存空间，知道下标可以在O(1)时间内找到元素，但是添加和删除时得考虑移动元素（末尾除外），性能较差，LinkedList底层为链表，添加和删除只需移动指针，故添加和删除性能高于数组

发表于 2020-08-19 22:14:03 回复(0)