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

相关文章

何谓重构？为何重构？ Spring中@NotNull、@NotBlank、@NotEmpty的区别 SpringBoot和SpringCloud版本对应 JAVA之从线程安全说到锁 SpringBoot启动概述（SpringBoot2.1.7）