25.ArrayList 和 LinkedList 的区别是什么? linklist与arraylist的区别 _linklist与arraylist的区别

文章插图

文章插图
【25.ArrayList 和 LinkedList 的区别是什么? linklist与arraylist的区别】首先，底层数据结构不同
ArrayList底层基于数组实现，连续内存存储，需要预先申请分配一段连续的内存空间(创建数组对象)，适合下标访问(随机访问)，需要创建多大的数组不好确定，如果数组长度过大，会造成内存空间浪费的问题，如果数组长度过小，当数组已满时想要添加新的元素，就需要创建一个新的数组，新的数组长度是旧数组的1.5倍，并把数据从旧数组复制到新数组中，然后才能添加新的元素。创建新的数组、旧数组数据复制到新数组，都是比较重量级的操作。另外，如果不是在尾部插入、删除数据还会涉及到元素的移动，使用尾插法并指定初始容量可以极大提高性能，甚至超过LinkedList，因为LinkedList需要创建大量的node对象。
LinkedList底层基于双向链表实现，元素可以储存在分散的内存中，适合做数据插入操作及删除操作，不适合随机查询，需要逐一遍历。
其次，ArrayList和LinkedList都实现了List接口，但是LinkedList还额外地实现了Deque接口，所以LinkedList还可以当作队列来用，利用双向链表和队列的特性，还是可以当作栈来使用。