Mar*_*ald 14 java collections performance big-o
我在Java类中有一个私有LinkedList,并且经常需要检索列表中的最后一个元素.列表需要扩展,所以我试图决定在进行更改时是否需要保留对最后一个元素的引用(实现O(1))或者如果LinkedList类已经通过getLast()调用那样做了.
LinkedList.getLast()的大O成本是多少,是否记录在案？(即我可以依赖这个答案,还是我不做任何假设并缓存它,即使它是O(1)？)
dou*_*lep 27
它是O(1)因为列表是双重链接的.它保持对头部和尾部的引用.
来自文档:
索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准.
它是O(1),你不应该缓存它.getLast方法只返回header.previous.element,因此没有计算,也没有遍历列表.当您需要在中间找到元素时,链接列表会变慢,因为它从一端开始并一次移动一个元素.
| 归档时间： |
|
| 查看次数： |
8977 次 |
| 最近记录： |