Java中的LinkedList.getLast（）的时间复杂度是多少？ [英] What is the time complexity of LinkedList.getLast() in Java?

问题描述

我有一个私人LinkedList在Java类&将经常需要检索列表中的最后一个元素。列表需要缩放，所以我想决定是否需要保留对最后一个元素的引用，当我进行更改（实现O（1））或如果LinkedList类已经与getLast（）调用。

LinkedList.getLast（）的big-O成本和是否有记录？我可以依靠这个答案，或者我应该没有假设和缓存它，即使它是O（1）？）

解决方案

它是O（1），因为列表是双链接的。

从文件：

该列表中的索引将从开头或结尾遍历列表，以更接近指定的索引。

I have a private LinkedList in a Java class & will frequently need to retrieve the last element in the list. The lists need to scale, so I'm trying to decide whether I need to keep a reference to the last element when I make changes (to achieve O(1)) or if the LinkedList class does that already with the getLast() call.

What is the big-O cost of LinkedList.getLast() and is it documented? (i.e. can I rely on this answer or should I make no assumptions & cache it even if it's O(1)?)

解决方案

It is O(1) because the list is doubly-linked. It keeps references to both head and tail.

From documentation:

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

这篇关于Java中的LinkedList.getLast（）的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！