ArrayList和LinkedList的区别、优缺点

2020-6-19

ArrayList的底层是基于数组实现的，而LinkedList底层是基于双向链表实现的。

一般来说都知道数组查询快，链表增删快。但是对于我这种新手来说，这种特性，也只是作为知识储备，没有灵活运用过。

最近开发中有使用到List存取东西，由于业务要求，需要对list进行改造，或者在头部，或者在尾部，要插入元素，保证每个list长度相等。几个小的list要再存入一个大的list中。

对于小的list来说，如果使用ArrayList，在插入元素时会很麻烦，虽然在尾部添加元素和删除元素，ArrayList所用的时间是一样的，但是在集合中或者头部添加元素，插入点之后的每个元素需要往后挪一位，这是比较耗费时间的。而LinkedList它在插入、删除集合中任何位置的元素所花费的时间都是一样的，但是它根据索引查询一个元素的时候却比较慢。

因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以他的特点就是寻址读取数据比较容易，插入和删除比较困难。所以在需要查询的时候不妨使用ArrayList。

以下是我摘抄的ArrayList和LinkedList的缺点

如下:

对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。

在ArrayList集合中添加或者删除一个元素时，当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。

LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。

ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

2020-7-20 新增

之前对数组和链表的理解不够，现增加以下知识点

1.为什么数组查询快，链表增删快

首先，在创建数组时，向内存申请一块连续的内存空间，假设该数组长度为5，内存中分配给该数组的地址以00开头，那么顺序往下为00-04，在查询的时候，你通过数组下标可以查询任意你想查询的那个元素，比如查03，那么你找到00了，只要将下标加3，即是03了。但是如果要插入元素，比如在数组头插入元素，那个首先要保证连续的内存空间够不够长，如果不够，要先迁移到足够长的连续内存中，然后修改下标。

然后链表在内存上当然是不连续的了，但是链表中每个元素会存储指向下一个元素的地址，这就是查询慢的原因。因为在内存上不连续，你必须通过第一个元素得到第二个元素的地址，通过第二个元素得到第三个元素的地址，依此往复。那么链表增删快的原因，就在于只需要修改指向下一个元素的地址就好了。