JAVA集合框架整理（四） - ArrayList和LinkedList的区别

旧城等待， 2022-05-10 13:52 124阅读 0赞

ArrayList和LinkedList都是实现了List接口的容器类，用于存储一系列的对象引用。他们都可以对元素的增删改查做操作。

对于ArrayList，它在集合的末尾删除或者添加元素所用的时间是一致的，但是在列表中间的部分添加或删除时所用的时间就会大大增加。但是它的根据索引查找元素的时候速度很快。

对于LinkedList则相反，它在添加、删除集合中的任何位置的元素所花费的时间是一样的，但是它根据索引查询一个元素的时候却比较慢。

ArrayList的实现原理：

*  ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。
 *  底层使用数组实现。
 *  该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种操作的代价很高。
 *  采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
 *  remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC。

LinkedList的实现原理：

*  LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
 *  底层的数据结构是基于双向链表的，该数据结构我们称为节点。
 *  双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。
 *  它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到。

ArrayList和LinkedList的大致区别有以下几点：

*  ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表结构；
 *  对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针；
 *  对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据；

ArrayList和LinkedList在性能上的优缺点：

*  对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的，对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配，而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象；
 *  在ArrayList集合中添加或者删除一个元素，当前的列表所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的；
 *  LinkedList集合不支持高效的随机访问（RandomAccess），因为可能产生二次项的行为；
 *  ArrayList的空间浪费主要体现在list列表的结尾预留一定的空间容量，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。

**所以进行查操作时用ArrayList，而进行增删操作时最好用LinkedList**