本文提到的实现均是基于jdk 1.8，其他版本可能不同。 如果文章有错的地方欢迎指正，大家互相交流 , 欢迎评论大家一起讨论技术。

一、数组和链表介绍

数组和链表是两种基本的数据结构，虽然均是作为线性的数据结构，但是在内存存储上的表现不一样，所以也有各自的特点。

1.1、数组的特点

数组中5个学生连坐一起

• 在内存中，数组是一块连续的区域。对内存要求较高，因为只能分配连续的内存空间，零碎的内存空间小于数组申请的空间时利用不上。

• 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。

• 插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。

• 随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给定地址的数据。

• 不利于扩展，数组定义的空间不够时要重新定义数组

1.2、链表的特点

链表中散列分布的5个学生

• 在内存中可以存在任何地方，不要求连续。

• 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。

• 增加数据和删除数据很容易。 因为只需要将下一个数据的地址修改一下就好，不用像数组要移动数据。

• 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起。

• 不指定大小，扩展方便。链表大小不用定义，数据随意增删。

1.3、数组和链表总结

数组的优点

• 随机访问性强、查找速度快（要说明的是这指的是通过下标访问，而如果要通过数据值来范围，也是跟链表一样需要遍历数组的）

数组的缺点

• 插入和删除效率低

• 可能浪费内存

• 内存空间要求高，必须有足够的连续内存空间

• 数组大小固定，不能动态拓展

链表的优点

• 插入删除速度快

• 内存利用率高，不会浪费内存

• 大小没有固定，拓展很灵活

链表的缺点

• 不能随机查找，必须从第一个开始遍历，查找效率低

建议

对性能不敏感时，随便用哪个都可以，但是对性能有要求时，随机访问多新增删除少时建议用数组，相反，建议用链表

二、Collection集合体系的继承树

Collection集合体系的继承树

三、ArrayList源码赏析

3.1、插入元素，赏析扩容

插入元素，赏析扩容

ArrayList的底层实现是数组，而数组长度是固定的，ArrayList长度却是可变长的，其实ArrayList底层用的是扩容的手段，简单来说就是当容量不够时，将元素拷贝到一个长度更长的新数组。

所以ArrayList在插入元素时，先做的是数组扩容，因为新增一个元素，所以minCapacity = size+1，如果是第一次插入，则minCapacity默认为10，意思是ArrayList不可能一个一个的扩容，因为容量扩展的开销太大呀，若minCapacity > 当前的容量时才会进行扩容，否则不需要扩容直接插入元素即可。到这里，我们可以得知minCapacity 可以理解成客户端本次插入元素需要的最小容量的意思。minCapacity 其实也不是最终要扩容的数量，因为这只是客户端要求存放元素的最少容量，可是ArrayList也有自己的原则，它默认扩容0.5倍，若minCapacity 较大将按minCapacity 来扩容，否则就是扩容0.5倍。

3.2、移除元素，赏析对象回收细节

移除元素，赏析对象回收细节

第505行：elementData[--size] = null; // clear to let GC do its work，主动断开了栈与堆的连接，之后该对象就失去了引用，GC才能进行回收，不然没用的对象一直占用内存可能会导致内存溢出与内存泄露。

3.3、总结及建议

ArrayList的底层实现原理相对不难，难点主要是扩容。虽然每次扩容默认增大0.5倍，但是扩容涉及到元素复制到新数组，开销是比较大的。所以建议：

当预计到插入元素较多时，在实例化时利用public ArrayList(int initialCapacity)构造函数指定初始容量，若是在插入元素的过程中才知道接下来插入元素操作频繁，可以用public void ensureCapacity(int minCapacity)方法扩容。

四、Vector与ArrayList的区别

Vector是jdk1.2的类了，比较老旧的一个集合类。

注释上写着是jdk 1.2的类

Vector底层也是数组，实现原理跟ArrayList几乎一样，与ArrayList最大的区别就是：同步(线程安全)

还有个区别ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。

Vector是同步的，我们可以从方法上就可以看得出来~

方法上都有synchronized

五、LinkedList实现原理

LinkedList节点内部类

该LinkedList内部类，就是ArrayList的节点类。根据属性，可以猜到LinkedList的底层实现应该是个双向链表，没错，就是双向链表。

知道了节点对象后，只要懂得链表的知识，加上逻辑思维能力，自己实现一个简单的LinkedList应该不是难事，所以LinkedList就不多说了。

最后，要补充一下的就是：从上面的Collection继承树中可以看到，LinkedList除了实现List接口外，还实现了Deque接口，Deque接口是个双向队列。因此，LinkedList除了能够存放元素外，还可以实现队列和栈的功能，可谓是一个功能强大的类。

六、总结

其实集合的源码看起来并不是很困难，遇到问题可以翻一翻，应该是能够看懂的。

ArrayList、LinkedList、Vector算是在面试题中比较常见的的知识点了。下面我就来做一个简单的总结：

ArrayList

• 底层实现是数组

• ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍

• 在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList

底层实现是双向链表[双向链表方便实现往前遍历]

Vector

底层是数组，现在已少用，被ArrayList替代，原因有两个：

  Vector所有方法都是同步，有性能损失。

  Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存**。**

总的来说：查询多用ArrayList，增删多用LinkedList。