Java链表: Removing Largest Element Using Iterator

Question

如何从java中的链表中删除最大元素？我知道我可以使用 get() 或 remove() 函数来检索/删除元素。但我想让它变得高效。我想使用迭代器。你知道我该怎么做吗？请注意，我不想创建自己的链表。我什至不想对我的链接列表进行排序。

我可以对此进行线性搜索吗？如果是这样，我如何跟踪指向最大元素的指针(或迭代器)。任何帮助将不胜感激。

Answer 1

链接列表(除非排序)并不是您在此处尝试执行的操作的最佳结构，因为除了进行线性搜索并删除最大元素之外，您别无选择

Integer biggest = Integer.MIN_VALUE;
for(Integer e : myList){
   if(biggest < e)
        biggest = e;
}
myList.remove(biggest);

这将是 O(n)，即使您必须再次扫描以删除最大的，如果您使用自己的 LinkedList，则第二次扫描是可以避免的，因为 java.util.LinkedList 隐藏了其 Entry 类并且不允许您修改指针；但这将是错误的优化方法，因为如果您使用类似堆的结构，在 java 中将是 PriorityQueue 类，您可以获得 O(log(n)) 并将代码减少为:

return myPriorityQueue.poll();