本文介绍了Java中的LinkedList.getLast()的时间复杂度是多少?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个私人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:

这篇关于Java中的LinkedList.getLast()的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-29 11:16