Java中ArrayList为什么比LinkedList查询速度快?

2020年5月16日 2832点热度 0人点赞 0条评论

ArrayList从原理上就是数据结构中的数组,也就是内存中一片连续的空间,这意味着,当我get(index)的时候,我可以根据数组的(首地址+偏移量),直接计算出我想访问的第index个元素在内存中的位置。写过C的话,可以很容易的理解。

LinkedList可以简单理解为数据结构中的链表(说简单理解,因为其实是双向循环链表),在内存中开辟的不是一段连续的空间,而是每个元素有一个[元素|下一元素地址]这样的内存结构。当get(index)时,只能从首元素开始,依次获得下一个元素的地址。

用时间复杂度表示的话,ArrayList的get(n)是o(1),而LinkedList是o(n)。

guest
0 评论
Inline Feedbacks
查看所有评论