引言

java集合框架图

        基于Java集合框架图，本文针对List集合的主要实现类 ArrayList和LinkedList从实现原理、特点、核心功能实现细节角度进行分析总结，目的是深入的了解其性能特点和适应场景，合理的优化使用；学习它们的架构设计思想和算法思想，编写更高效的代码。

ArrayList：基于数组实现的非线程安全的自动扩容列表。特点是实现了RandomAccess接口，随机访问效率高，但需要维护内存空间的连续性，内存利用率低。集合在添加和删除元素时会创建更大的数组，采用数组复制的方式把原有数据拷贝到新数组，完成自动扩容。

ArrayList的初始化及扩容方案？

ArrayList默认初始容量为10，初始数组为空。

初始数组为空，初始容量为10

缺省构造器与指定容量初始化构造器

缺省与指定容量构造器

下面重点关注下add方法，先进行容量确认逻辑（其中modCount用于遍历操作，快速失败检测），再将元素加入集合，同时集合元素数量size值加1。

添加元素add

接着进入ensureCapacityInternal 方法(容量确认)，具体了解扩容与否，如何扩容？

最小容量：minCapacity是集合的最小容量，也就是当前添加一个元素后，集合中实际元素的数量。比如没添加之前，集合中已经存在5个元素了，此时minCapacity =size+1 =5+1 = 6 ，就是说集合最少需能够容纳6个元素。如果集合中无任何元素，则最小容量就是Math.max(DEFAULT_CAPACITY, minCapacity)两者的最大值10，此时minCapacity是1。

最小容量确认

扩容与否判断：集合最小容量大于集合容量时进行扩容。

扩容与否判断

扩容：对原始集合容量每次扩大1.5倍（其中>>1相当于整数除以2操作）。然后使用Arrays.copyOf数组拷贝方法，将原数据拷贝到新生成的数组中。

        扩容时会发生数据溢出（超过int最大值）变为负数，那么newCapacity = minCapacity。

        接着进一步判断newCapacity 是否超出当前虚拟机允许分配的最大长度限制？如果minCapacity>MAX_ARRAY_SIZE值时，则返回newCapacity = Integer.MAX_VALUE；否则newCapacity = MAX_ARRAY_SIZE。这个逻辑说明集合最后一次扩容后的newCapacity实际长度只能是两者之一，不存在中间值（貌似个别VM会预留8个长度，则只能分配到MAX_ARRAY_SIZE，不预留也只能最大分到int最大值）。

扩容

数据拷贝：本地方法完成原数据拷贝到新数组。

LinkedList ：本质上是双向链表，比较值得关注的是其还实现了Deque接口，使其同时具备了队列和栈的性质。LinkedList主要包括3个成员first、last和size。size是指双向链表实际结点的个数，first和last是分别指向双向链表的第一个和最后一个结点的引用。

LinkedList如何解决随机访问元素时间复杂度高？

        LinkedList特点是内存利用率高，但随即访问的性能较比ArrayList差。LinkedList之所以采用双向链表而非单链表实现，也是采用了空间换性能的方式，来降低查询操作的时间复杂度。比如：当在链表中查询某个固定索引位置的结点时，如果采用单链表实现只能从头至尾遍历查找，时间复杂度是O(n)；但采用双链表实现，根据当前链表中实际结点个数size和要查找的索引进行比较，索引小于size一半时说明要查找的元素离链表第一个结点更近，采用从头向尾遍历，反之离最后一个结点更近，从尾结点开始向前遍历。这种查找算法会比单链表从头至尾遍历减少一半的查找概率，提高了查找性能。如下图所示，size>>1相当于size/2。

查找固定索引位置的结点

总结

        ArrayList和LinkedList是工作中比较常用的有序队列，提供了丰富的针对元素的增加、删除、查找、遍历操作。ArrayList支持动态扩容，但最大能存储int最大值数量的元素；LinkedList由于实现了Deque双端队列接口，使其拥有了队列和栈的特点。modCount属性的作用是在集合遍历时提供快速失败检测机制（即遍历集合时，如果发生了添加或删除元素操作，则会抛出ConcurrentModificationException异常）。在实际使用场景中应综合考虑各自集合的实现特点、数据规模、操作特点、内存占用等因素，合理取舍。

        当随机访问元素操作明显大于增删改时，优先考虑ArrayList，使用时应注意集合在添加、删除元素时，动态的被动扩容会造成大量数据复制的额外开销，甚至在未指定初始容量时，如果集合元素数量过大，甚至引起OOM。因此如果能够提前预估容量，可以在集合初始化时指定容量进行优化。（默认初始容量是10，每次扩容1.5倍。因此集合存储1千个元素需要进行11次扩容，1万个元素需要进行17次扩容）

        当需要频繁对集合中的元素进行添加、删除操作时，优先考虑LinkedList，它天然支持动态扩容且内存利用率高。但频繁进行元素删除操作有可能造成GC频繁、内存碎片。