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

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

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

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


除非注明,否则均为李锋镝的博客原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.lifengdi.com/archives/article/1848

分享到:

说点什么

avatar
  订阅  
提醒