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的實現不允許拷貝迭代器指向特定的元素以後去除