Java ArrayList 不服来辩

[guguji]

get(int index) 方法时间复杂度 O(1)，如何做的到？ - 如果底层是基于数组，那么数组为什么可以根据索引快速访问到数据？

remove(int index) 方法时间复杂度 O(N2) - 如果有大批量的数据在 list 中，且要删除其中一个元素，请问如何优化？ - 就基于 ArrayList 来做，不该变成 LinkedList 这种？

[deplivesb]

op 的 blog 和他的三个帖子，看出来就是个 xx

[Ericcccccccc]

重新学下组成原理?

[issakchill]

为啥不问问神奇的 chatgpt?

[coderxy]

我原来面试别人的时候，不少人分不清数组跟链表的区别的时候我的心理活动跟现在一模一样的

[oneisall8955]

钓鱼贴

[maxssy]

1. ArrayList 的首个元素的地址是已知的
2. ArrayList 底层实现在内存上表现为各个元素顺序排放的数组
3. ArrayList 每个元素的内存占用大小是已知的
所以
get 在取得索引后可以通过公式: `目标元素的地址 = 首元素地址 + 索引 * 每个元素的内存占用大小` 来取得, 所以时间复杂度是 O(1)

又因为各元素是顺序排放的, remove 某个元素后需要重新排列整个数组, 所以是 O(n)

[cyndihuifei]

为什么这种问题都搞不清楚还要发技术文章

[dragondove]

@xaplux 实际上 LinkedList 已经基本没有适合使用的地方了，具体可以看这个知乎回答 https://www.zhihu.com/question/563680801/answer/2750393567

[zengmingyang96]

数组为什么可以根据索引快速访问到数据? 因为内存支持随机读取 😂

[v2eb]

@coderxy 真有这种人嘛😂

[neptuno]

我一般都是钻到内存里面，自己去找地址

[BeautifulSoap]

本来以为 lz 想要问的是内存电路是怎么寻址的，实但仔细想想 lz 可能真的连数组是啥都不懂。。。

[oneisall8955]

@dragondove 偶尔还是会用到的，不确定数量情况下

[dk7952638]

看这标题，以为来到了贴吧

[xiangbohua]

你说了几个问题，你都没给结论，辩论啥

[haolongsun]

没上过数据结构？底层是数组，再细说是对数组首地址的引用，快速访问到素就是首地址+偏移量*数组元素 sizeof,这就是 O(1)，再多说就是 arraylist 的结构就是一个指向堆上数组的指针，一个 len ，一个 cap 。

[BanGanExpert]

@v2eb 以前本身业务需求多，JavaWeb 上手不又难，造成很多基础不扎实，不清楚基本的数据结构知识，很多人也能进入行业做开发。当然现在新人水平普遍是专业对口毕业的，自然很大程度上都没这个情况了。我以前面试人一般第一个问题就是，你写 Java 用了哪些线性结构的集合实现，分别在哪种场景，除了当普通集合还能干嘛（ Stack 、Heap 、Queue ）。

[xhinliang]

挺好，又 block 一个人

[strrng]

OP 感觉多少是有点搞笑了😄

[zcm3579]

辩了个勾巴 , 脑残就不要发帖