首页 > 试题广场 >

以下关于链表和数组说法正确的是（）

[不定项选择题]

以下关于链表和数组说法正确的是（）

```
new出来的数组也在堆中
```

数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)

数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)

对于add和remove，ArrayList要比LinkedList快

查看正确选项

黑大—欧豪

A：堆内存是用来存放由new创建的对象和数组，

栈内存是用来存放在函数中定义的一些基本类型的变量和对象的引用变量，

例子：new函数和malloc函数申请的内存在堆；

局部变量存放在栈；函数调用参数，函数返回值，函数返回地址存放在栈

B：链表与数组插入和删除时间复杂度都是O (n)

C：数组利用下标 index 定位，时间复杂度为O(1) “无论有序数组，还是无序数组”

链表定位元素时间复杂度O(n)； “最好情况下第一个就是即o(1)，最坏情况o(n)，取最坏情况o(n)。”

D：数组：查询速度快，增删元素慢；

链表：查询速度慢，增删元素快；

发表于 2022-07-01 20:47:27 回复(2)

努力努力再努力的小蚂蚁

链表只有删除插入首尾节点的时间复杂度才是O(1)，在中间插入删除因为要先查找到相应位置才能插入删除，所以时间复杂度也到了O(n)

发表于 2022-05-26 11:41:16 回复(7)

小夥

数组从栈中分配空间，链表从堆中分配空间

数组也可以是new的，链表也可以是用数组模拟的~~

发表于 2019-03-16 23:46:53 回复(2)

牛客650726674号

ArrayList 底层实现就是数组，且ArrayList实现了RandomAccess，表示它能快速随机访问存储的元素，通过下标 index 访问，只是我们需要用 get() 方法的形式，数组支持随机访问，查询速度快，增删元素慢；
LinkedList 底层实现是链表， LinkedList 没有实现 RandomAccess 接口，链表支持顺序访问，查询速度慢，增删元素快

发表于 2020-03-15 22:34:32 回复(0)

smile_ll

..new 出来的东西不应该都是堆中的吗

发表于 2019-03-15 09:19:29 回复(4)

疾风剑豪无e烦

数组分配的空间不是在堆中吗？？？

发表于 2019-03-16 10:34:26 回复(5)

Algernomn

数组在插入删除的时候，要移动元素，复杂度为o(n)。
链表尽管不需要移动元素，只用改变指针关系，但是要插入或删除第i个节点，必须先找到第i-1个节点，复杂度为o(n)。
总体完成一次操作，大家都是o(n)的复杂度，为什么说，要频繁删除插入操作时，选链表？

答:
因为这个O(n)内涵不同，分别是写O(n)和读O(n)。
数组擅长读取，链表擅长写入。
写入要先读取定位，再写入。
读取场景：任意序位读取，复杂度：数组O(1)，链表O(n)。
写入场景：任意序位写入，定位复杂度：数组O(1)，链表O(n)；写入复杂度：数组O(n)，链表O(1)。
在写入场景中，数组链表的复杂度是定位写入复杂度之和，都是O(n),但写入比定位的O(n)慢很多，所以两个表面看起来一样的O(n)的实际时间还是差很多。
所以说链表和数组的插入删除时间复杂度都是o(n)，链表写入效率高。

发表于 2022-09-27 14:37:19 回复(0)