Java中LinkedList.getLast（）的时间复杂度是多少？

performance collections java big-o

2022-09-02 20:03:40

我在Java类中有一个私有LinkedList，并且经常需要检索列表中的最后一个元素。列表需要扩展，所以我试图决定当我进行更改时（以实现O（1））时，我是否需要保留对最后一个元素的引用，或者LinkedList类是否已经通过getLast（）调用来执行此操作。

LinkedList.getLast（）的O大O成本是多少？它是否被记录下来？（即，我可以依赖这个答案，还是应该不做任何假设并缓存它，即使它是O（1）？）

答案 1

它是 O（1），因为列表是双联的。它保留对头部和尾部的引用。

从文档中：

索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引者为准。

答案 2

它是 O（1），您不必缓存它。getLast 方法只是返回，因此没有计算，也没有遍历列表。当您需要在中间查找元素时，链表会变慢，因为它从一端开始，一次移动一个元素。header.previous.element