为什么在LinkedLists中添加特定索引的速度比在ArrayLists中慢
Fin*_*man 5 java performance linked-list arraylist
我正在检查此图表,其中包含列表之间的性能比较:
而且我发现在特定索引处添加和删除元素的速度ArrayList比在a中执行速度快得多LinkedList.这个图表错了吗？a的整体思想LinkedList是改进这样的操作,同时以降低的迭代性能付费.但是这个图表似乎表明Java的实现LinkedLists做得非常糟糕.
我应该相信图表吗？如果是这样,为什么Java LinkedLists表现如此糟糕？
Jon*_*eet 13
LinkedList的整个想法是改进这样的操作,同时以降低的迭代性能付费.
不,链接列表的想法是在最后添加或删除或开始非常便宜...或者如果你已经有一个节点对象的引用,添加或删除它也非常便宜.(我不认为Java API会暴露节点,但是像.NET这样的其他平台会这样做.)
要在链表中的索引处添加,实现首先必须导航到该索引处的节点...这是O(n)操作.一旦它到达那里,添加便宜.因此,在开始附近添加索引(或以智能实现结束)是便宜的,但在中间附近添加索引是昂贵的.
有了ArrayList,费用来自:
- 将现有元素复制到您要添加的索引之外
- 复制整个事情就是缓冲区不够大
- @JBNizet:这意味着它不能弥补直接访问节点的不足,但它总比没有好. (2认同)
| 归档时间： |
|
| 查看次数： |
321 次 |
| 最近记录： |