首页 > 试题广场 >

以下关于链表和数组说法正确的是()

[不定项选择题]
以下关于链表和数组说法正确的是()
  • 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 回复(1)
链表只有删除插入首尾节点的时间复杂度才是O(1),在中间插入删除因为要先查找到相应位置才能插入删除,所以时间复杂度也到了O(n)
发表于 2022-05-26 11:41:16 回复(7)
数组从栈中分配空间,链表从堆中分配空间
数组也可以是new的,链表也可以是用数组模拟的~~

发表于 2019-03-16 23:46:53 回复(2)
  • ArrayList 底层实现就是数组,且ArrayList实现了RandomAccess,表示它能快速随机访问存储的元素,通过下标 index 访问,只是我们需要用 get() 方法的形式, 数组支持随机访问, 查询速度快, 增删元素慢;
  • LinkedList 底层实现是链表, LinkedList 没有实现 RandomAccess 接口,链表支持顺序访问, 查询速度慢, 增删元素快
发表于 2020-03-15 22:34:32 回复(0)
..new 出来的东西不应该都是堆中的吗
发表于 2019-03-15 09:19:29 回复(4)
数组分配的空间不是在堆中吗???
发表于 2019-03-16 10:34:26 回复(5)
数组在插入删除的时候,要移动元素,复杂度为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)
单说数组有歧义,静态数组是在栈中开辟内存,链表一般是在堆中分配空间,静态链表除外
发表于 2019-03-22 16:44:23 回复(0)
我认为A存在问题,JDK里面添加了栈上分配:即如果没有发生逃逸的方法内对象,则可以在栈上分配
发表于 2022-03-23 11:10:52 回复(0)
单链表删除最后一个元素的时间复杂度是O(N) 啊

发表于 2019-11-18 20:12:19 回复(4)
这道题也太不清晰,new分配的都在堆中,在函数内部定义的都在栈里
发表于 2019-10-10 20:44:15 回复(0)
数组不是可以根据下标访问吗?如果从栈中分配空间,那么要取出来的时候岂不是要一个一个出吗???不懂,求解。
发表于 2019-03-26 16:37:44 回复(0)
这个题目不严谨,应该说清楚是只是定义了还是已经初始化了
发表于 2019-03-26 11:36:45 回复(0)
链表有单向(o n)和双向链表(o 1)
发表于 2022-07-20 22:28:32 回复(0)
堆内存是用来存放由new创建的对象和数组,即动态申请的内存都存放在堆内存。
发表于 2021-10-29 11:20:02 回复(0)
我觉得应该要说静态数组是从栈中分配出来的,这是对于那些C、C++那些的。
不过在Java中是new出来的,可以看做是一个对象,对象是从堆分配出来的嘛。
——这是我的见解
发表于 2020-04-01 22:47:22 回复(0)
栈上数组由系统自动分配。 比如函数声明局部变量的时候系统自动在栈上开辟空间。 堆上数组需要程序员自己申请,并指明大小。
发表于 2019-05-06 15:24:05 回复(0)
new 出来的就都在堆里面 对于插入和删除元素来说,链表的确比顺序表简单,但是他的优势在于不用移动大量元素。 但是要在指定的位置进行插入和删除,必须也要先遍历找到他的前驱节点。所以时间复杂度不可能为O(1)
发表于 2023-05-29 10:53:37 回复(0)
单单只是插入删除的话,链表肯定O(1),B对
发表于 2022-10-29 11:50:29 回复(0)
array list底层是数组 linked list底层是链表 链表插入或删除 笼统上讲是需要从头遍历到目标位置再进行插入或删除
发表于 2022-09-27 21:38:53 回复(0)