LinkedList的幻觉

用Java这么多年，以为了解LinkedList，ArrayList的差异，没想到今天发现有些事情是幻觉。

一直觉得LinkedList.add()比ArrayList.add()要快，因为ArrayList在内部数组大小不足时会扩大数组（初始值10，每次增大50%+1），但是今天在代码review时一位同事提出了质疑（thx，gavin）。

当时争论很激烈，没有定论。回到家我做了个性能测试，发现在只对队尾添加元素的话，n（循环add(Object)）不大的情况下，LinkedList的性能不比ArrayList强，甚至在n=30万时要慢得4倍多。

应该是由于LinkedList内部新建Entry保存双向关联造成的性能损耗。

 

所以在大多数情况下，ArrayList是最佳选择，只有需要大规模中间插值的场合下，LinkedList才需要被考虑。

流行的单纯算法分析，O（1）、O（n）、O（n/2）都敌不过实际性能测试。

 

另外，同事sam的随机子列表算法被证明是具有随机性的（依我的观察，固定参数下还是有点不均匀），但是性能却比不上更简单的随机碰撞检测法，在采样数n的情况下，性能最慢估计会有n平方/2倍。

为了杀灭碰撞法亿万分之一的死循环概率，这么干实在是有点闲得慌啊。:)

评论

2 楼 AlwenS 2010-12-13  

平摊分析应该能很好的解决楼主的疑惑。

一个连续的n次操作集合的代价 != n * 每次操作的代价。

1 楼 liangguanhui 2010-11-10  

LinkedList应该只是插入删除的时候有优势，追加和查询还是ArrayList占优。