集合 ArrayList,LinkedList 分析

ArrayList和LinkedList是List接口的俩个经典实现子类，在我们的开发中会经常使用它们。

简单来说，ArrayList的底层实现是一个可扩容的数组，LinkedList的底层是一个双链表。所以其中的优缺点主要是其底层的数组和双链表数据结构带来的。（信息来源：JDK1.8源码）

add 操作：

       理论上讲，数组和双链表在末尾添加元素时，排除数组扩容时间和内存等影响，数组和双链表及其代表的ArrayList和LinkedList复杂度都是常数时间O(1),当在头部添加元素时，ArrayList的效率会大大减少，而LinkedList的与末尾添加基本没变化。

（1）测试用例:向ArrayList和LinkedList的一个实例的末尾分别添加元素，测试所用时间。

根据图1-1的结果，基本符合理论结果，当向List末尾添加元素时，ArrayList和LinkedList效果相差不大。且随着实验添加元素数量不断加大，实际结果越接近理论结果。

（2）测试用例:向ArrayList和LinkedList的一个实例的头部分别添加元素，测试所用时间。

根据图1-2的结果，ArrayList随着元素数量的增多，向头部add的操作越来越消耗时间，跟期望的结果是一样的。因为ArrayList向头部添加元素会触发数据复制，向头部添加一条数据的元素理论上的时间复杂度是O(n) , n为数组的长度。