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为数组的长度。