Java链接列表：使用迭代器去除最大元素

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（日志（N））和代码简化为：

return myPriorityQueue.poll(); 

Answer 2

如果你知道最大的因素是，你能做到这一点，像这样

Iterator<Integer> it = list.iterator(); 
Integer toRemove; 
while(it.hasNext()){ 
    if(toRemove.compareTo(it.next()==0){ 
     it.remove(); 
     break; 
    } 
} 

或使用list.removeFirstOccurrence（文档，删除）

什么，但LinkedList的实现不允许拷贝迭代器指向特定的元素以后去除