本文提到的实现均是基于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。
网友评论