ArrayList 和 LinkedList测试

ArrayList 和 LinkedList测试
1.ArrayList 和 LinkedList 新增元素操作测试
测试结果 (花费时间)：
通过这组测试，我们可以知道 LinkedList 添加元素的效率未必要高于 ArrayList。
从集合头部位置新增元素
从集合中间位置新增元素
从集合尾部位置新增元素

ArrayList>LinkedList
ArrayList<LinkedList
ArrayList<LinkedList

由于 ArrayList 是数组实现的，而数组是一块连续的内存空间，在添加元素到数组头部的时
候，需要对头部以后的数据进行复制重排，所以效率很低；而 LinkedList 是基于链表实
现，在添加元素的时候，首先会通过循环查找到添加元素的位置，如果要添加的位置处于
List 的前半段，就从前往后找；若其位置处于后半段，就从后往前找。因此 LinkedList 添
加元素到头部是非常高效的。

同上可知，ArrayList 在添加元素到数组中间时，同样有部分数据需要复制重排，效率也不
是很高；LinkedList 将元素添加到中间位置，是添加元素最低效率的，因为靠近中间位
置，在添加元素之前的循环查找是遍历元素最多的操作。

而在添加元素到尾部的操作中，我们发现，在没有扩容的情况下，ArrayList 的效率要高于
LinkedList。这是因为 ArrayList 在添加元素到尾部的时候，不需要复制重排数据，效率非
常高。而 LinkedList 虽然也不用循环查找元素，但 LinkedList 中多了 new 对象以及变换
指针指向对象的过程，所以效率要低于 ArrayList。

说明一下，这里我是基于 ArrayList 初始化容量足够，排除动态扩容数组容量的情况下进行
的测试，如果有动态扩容的情况，ArrayList 的效率也会降低。

2.ArrayList 和 LinkedList 删除元素操作测试
从集合头部位置删除元素
从集合中间位置删除元素
从集合尾部位置删除元素

测试结果 (花费时间)：
ArrayList>LinkedList
ArrayList<LinkedList
ArrayList<LinkedList
ArrayList 和 LinkedList 删除元素操作测试的结果和添加元素操作测试的结果很接近，这是
一样的原理，我在这里就不重复讲解了。

3.ArrayList 和 LinkedList 遍历元素操作测试for(;;) 循环
迭代器迭代循环
测试结果 (花费时间)：
ArrayList<LinkedList
ArrayList≈LinkedList
我们可以看到，LinkedList 的 for 循环性能是最差的，而 ArrayList 的 for 循环性能是最好
的。
这是因为 LinkedList 基于链表实现的，在使用 for 循环的时候，每一次 for 循环都会去遍
历半个 List，所以严重影响了遍历的效率；ArrayList 则是基于数组实现的，并且实现了
RandomAccess 接口标志，意味着 ArrayList 可以实现快速随机访问，所以 for 循环效率
非常高。
LinkedList 的迭代循环遍历和 ArrayList 的迭代循环遍历性能相当，也不会太差，所以在遍
历 LinkedList 时，我们要切忌使用 for 循环遍历。

One More
我们在查看 ArrayList 的实现类源码时，你会发现对象数组 elementData 使用了
transient 修饰，我们知道 transient 关键字修饰该属性，则表示该属性不会被序列化，然
而我们并没有看到文档中说明 ArrayList 不能被序列化，这是为什么？

由于 ArrayList 的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。

如果采用外部序列化法实现数组的序列化，会序列化整个数组。ArrayList 为了避免这些没
有存储数据的内存空间被序列化，内部提供了两个私有方法 writeObject 以及 readObject
来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。

因此使用 transient 修饰数组，是防止对象数组被其他外部方法序列化。