get(int index) 方法时间复杂度 O(1),如何做的到? - 如果底层是基于数组,那么数组为什么可以根据索引快速访问到数据?
remove(int index) 方法时间复杂度 O(N2) - 如果有大批量的数据在 list 中,且要删除其中一个元素,请问如何优化? - 就基于 ArrayList 来做,不该变成 LinkedList 这种?
1
Masoud2023 134 天前 ![]() 你这个问题应该回学校好好学学数据结构,而不是在这不服来辩
|
2
thevita 134 天前 ![]() 要辩你应该先陈述自己的观点,不应该是问句
ps: remove(int index) 复杂度 O(N2) 写错了吧。remove(Object o) 才是 O(N^2) |
![]() |
3
me1onsoda 134 天前 ![]() 那么数组为什么可以根据索引快速访问到数据?
大哥,数组存的数据在内存是连续的,当然可以根据索引来快速检索 |
5
emSaVya 134 天前 ![]() 这位更是重量级。
|
![]() |
6
gangoogle 134 天前 ![]() 数组在内存里面 第一个位置 0x0 第二个 0x2 我想取第 10 个元素直接 0x0+9 不就直接拿到了吗。。。。
|
![]() |
7
xaplux 134 天前
额,哪来的勇气啊,数组存储是连续的
get 根据下标直接可以寻址了 remove 时间复杂度是 O(n) ,主要是删除一个元素后,其之后的元素要移动啊,如果删除的是最好一个元素,复杂度可以做到 O(1) |
8
a0210077 134 天前
服,请参考数据结构的数组章节
|
![]() |
9
xaplux 134 天前
ArrayList 和 LinkedList 的使用场景是不一样的,鱼和熊掌不可兼得,所以要权衡
如果需要频繁删除,那用 LinkedList 相对 ArrayList 要合适 |
10
fresco 134 天前
这不是大学的内容么
|
11
PVXLL 134 天前 ![]() 震惊~
|
13
Ayanokouji 134 天前
不会的话,虚心请教不行吗,非要起这么一个标题找喷
|
![]() |
14
hidemyself 134 天前
我怀疑你是来钓鱼的。
|
16
Deeymmm 134 天前
挺好,又 block 一个人
|
![]() |
17
xtreme1 134 天前
钓的是_, 没的是_
|
![]() |
18
swczxf 134 天前 via iPhone
这是不是叫民科
|
![]() |
19
Jrue0011 134 天前
额,看历史发帖和回复也不应该啊
|
![]() |
20
mdn 134 天前
不服来辩 === 求求大家告诉我答案
|
21
deplivesb 134 天前
op 的 blog 和他的三个帖子,看出来就是个 xx
|
22
Ericcccccccc 134 天前
重新学下组成原理?
|
23
issakchill 134 天前
为啥不问问神奇的 chatgpt?
|
24
coderxy 134 天前
我原来面试别人的时候,不少人分不清数组跟链表的区别的时候我的心理活动跟现在一模一样的
|
![]() |
25
oneisall8955 134 天前 via Android
钓鱼贴
|
![]() |
26
maxssy 134 天前 ![]() 1. ArrayList 的首个元素的地址是已知的
2. ArrayList 底层实现在内存上表现为各个元素顺序排放的数组 3. ArrayList 每个元素的内存占用大小是已知的 所以 get 在取得索引后可以通过公式: `目标元素的地址 = 首元素地址 + 索引 * 每个元素的内存占用大小` 来取得, 所以时间复杂度是 O(1) 又因为各元素是顺序排放的, remove 某个元素后需要重新排列整个数组, 所以是 O(n) |
27
cyndihuifei 134 天前
为什么这种问题都搞不清楚还要发技术文章
|
![]() |
28
dragondove 134 天前 ![]() @xaplux 实际上 LinkedList 已经基本没有适合使用的地方了,具体可以看这个知乎回答 https://www.zhihu.com/question/563680801/answer/2750393567
|
29
zengmingyang96 134 天前
数组为什么可以根据索引快速访问到数据? 因为内存支持随机读取 😂
|
![]() |
31
neptuno 134 天前 via iPhone
我一般都是钻到内存里面,自己去找地址
|
![]() |
32
BeautifulSoap 134 天前 via Android
本来以为 lz 想要问的是内存电路是怎么寻址的,实但仔细想想 lz 可能真的连数组是啥都不懂。。。
|
![]() |
33
oneisall8955 134 天前
@dragondove 偶尔还是会用到的,不确定数量情况下
|
![]() |
34
dk7952638 134 天前
看这标题,以为来到了贴吧
|
![]() |
35
xiangbohua 134 天前
你说了几个问题,你都没给结论,辩论啥
|
36
haolongsun 134 天前
没上过数据结构?底层是数组,再细说是对数组首地址的引用,快速访问到素就是首地址+偏移量*数组元素 sizeof,这就是 O(1),再多说就是 arraylist 的结构就是一个指向堆上数组的指针,一个 len ,一个 cap 。
|
37
BanGanExpert 134 天前
@v2eb 以前本身业务需求多,JavaWeb 上手不又难,造成很多基础不扎实,不清楚基本的数据结构知识,很多人也能进入行业做开发。当然现在新人水平普遍是专业对口毕业的,自然很大程度上都没这个情况了。我以前面试人一般第一个问题就是,你写 Java 用了哪些线性结构的集合实现,分别在哪种场景,除了当普通集合还能干嘛( Stack 、Heap 、Queue )。
|
![]() |
38
xhinliang 134 天前
挺好,又 block 一个人
|
![]() |
39
strrng 134 天前
OP 感觉多少是有点搞笑了😄
|
![]() |
40
zcm3579 134 天前
辩了个勾巴 , 脑残就不要发帖
|
![]() |
41
Cooky 134 天前
看来裁员裁的还不够多
|
![]() |
42
makelove 133 天前
你不适合这个职业,趁早转行
|
43
zhch602 133 天前 via iPhone
这时候就看出来第一门语言学 C 的好处了——不会问出这种弱智问题
|
44
Yadomin 133 天前 via Android
可见科班出身的必要性
|
45
idealhs 133 天前 ![]() 跟个弱智一样
|
![]() |
46
IvanLi127 133 天前 via Android
什么鬼。。。这问题能问得出口?这属于话不会说,代码也不懂写。
|
![]() |
47
Qzier 133 天前 via iPhone
培训班出来的?没学过数据结构吗?
|
48
NoKey 133 天前
为啥不问问神奇的 chatgpt?
|
![]() |
49
learningman 133 天前 via Android
搞 Java 搞的
|
50
kachu673 133 天前
原来真有程序员不懂这些东西。。。可见科班的重要性了
|
51
4kingRAS 133 天前
类似你找车位,数组就是车位有刷编号,那不就 O (1) 找到了吗
|
52
kylix 133 天前
OP 抛了问题后,匿了
|
![]() |
53
czzhengkw 133 天前
|
54
githmb 133 天前
啊?
|
55
ignore 132 天前
啊?
|
![]() |
56
VinsonGuo 132 天前 via iPhone
@maxssy remove 也不是 On ,因为是对数组整体 arraycopy ,跑 benchmark 性能和 linkedlist 差不多
|
![]() |
57
qwerthhusn 132 天前
不要直接喷 OP ,有可能真的答不出来,之前就有司马面试官问到为啥数组能够快速访问数据,我感觉他是想往底层 JVM 指令甚至操作系统,计算机组成原理上问。
Java 字节码中访问数组的指令是 aload (对象引用数组), bload ( boolean 数组),iload ( int 数组)等,就是访问 arr[n]其实只用到一个 JVM 指令,JVM 栈顶是数组的地址和 n 这个 int 数字,然后执行 xload 指令,弹出这两个东西,得到结果,将值压入栈,栈顶就是 arr[n]的值。所以数组元素的访问只有一个 JVM 指令,无论 n 多大。 JVM 是虚拟机,xload 指令由 JVM 实际调用的什么呢?会不会有可能虽然 java 字节码只是一个指令,但是 jvm 解释后传递给下层的时候又变成循环了呢? 我也编不出来了,什么操作系统虚拟内存/物理内存,内存页,甚至到 CPU 指令如何存取内存数据等等,都忘光了。反正就是从高层到底层,访问 arr[n]不会随着 n 变大出现时间增长。 |
![]() |
58
good1uck 132 天前 via Android
很多人答不上技术问题
然后就挑 op 的标题态度问题 同样的问题问在 stackoverflow 你们觉得会有这么多事 b 跳出来教育人么 |
60
chaosz 132 天前
钓鱼的吧
|
![]() |
62
rOrange 131 天前
好好读读源码,连 linkedList 作者都发帖说不用 linkedList
|
63
lyxeno 131 天前
@qwerthhusn 这么一看,操作系统和 JVM 帮普通的程序员做了太多太多了
|
![]() |
64
lmq2582609 131 天前
可以看看数据在内存中是如何布局的
|
65
fengyouliang 127 天前
玩会原神吧
|
66
guguji OP 嗐 原来大家都在第一层~(我感觉没表达清楚问题),匿了匿了 害怕
|