ArrayList
ArrayList是一个动态数组,也是我们最常用的集合。
ArrayList 把很多数组操作的细节封装了起来,包括上一篇提到的插入、删除时迁移数据等。
ArrayList 还有一个优势就是支持动态扩容。
我们都知道数组在定义的时候是需要指定大小的,以便于分配连续的内存空间。
如果定义的时候是申请了20的数组,那么存储第21个数据时,就要重新分配一块更大的内存空间,将原来的数据复制过去,然后将新的数据插入。
ArrayList 底层已经实现扩容逻辑,每次存储空间不足的时候,都会自动扩容1.5倍大小。
扩容操作涉及内存申请和数据迁移,如果能事先确定存储数据的大小,最好在创建ArrayList的时候指定数据的大小。
ArrayList 支持根据下标进行随机查询,时间复杂度为O(1)。
LinkedList
LinkedList是一个双向链表,不支下标随机查询。
所有的操作都是要按照双向链表的需要执行。
在列表中索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。
这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
ArrayList与LinkedList的区别和适用场景
Arraylist:
优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
缺点:因为地址连续, ArrayList要移动数据,所以插入和删除操作效率比较低。
LinkedList:
优点:LinkedList基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址,对于新增和删除操作add和remove,LinkedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
缺点:因为LinkedList要移动指针,所以查询操作性能比较低。
适用场景分析:
当需要对数据进行对此访问的情况下选用ArrayList,当需要对数据进行多次增加删除修改时采用LinkedList。
领取专属 10元无门槛券
私享最新 技术干货