有效地從Java的LinkedList

這裏移除項目是我使用從鏈表中刪除某個項目的僞代碼：有效地從Java的LinkedList

public static void removeByID(LinkedList<Fruit> fruits, int fruitID) { 
    for(Fruit f : fruits) { 
     if (f.ID == fruitID) { 
     fruits.remove(f); 
     return; 
     } 
    } 
}

我想這是不是很有效，因爲fruits.remove()將再次迭代在名單上。想知道是否有更好的方法來實現這一點。

來源

2014-10-31 Peter

我預計此代碼拋出[ConcurrentModificationException]（http://docs.oracle.com/javase/7/docs/api/java/util/ConcurrentModificationException.html），因爲LinkedList在迭代期間被修改。剛剛開啓了eclipse，並沒有拋出這樣的例外。我錯過了什麼？ – Gowtham 2014-10-31 17:48:01

@Gowtham它沒有這樣做的原因是'return'：'fruits.remove（）'只是將集合標記爲已修改集合，（隱藏）迭代器的下一個操作將會 - 如果有的話 - 會看到並拋出。 – zapl 2014-10-31 23:36:37

@zapl謝謝。這使得它清楚 – Gowtham 2014-11-01 06:53:13

對於java.util.LinkedList，使用Iterator。

Iterator<Fruit> it = fruits.iterator(); 
while(it.hasNext()) { 
    if(it.next().ID == fruitID) { 
     it.remove(); 
     break; 
    } 
}

這將導致只有一次遍歷。返回的Iterator可以訪問底層鏈接結構，並且可以執行刪除操作而不會迭代。

當您使用for-each循環表單時，無論如何都會隱式使用迭代器。你只是保留對它的引用，所以你可以利用它的功能。

對於O（n）插入，您也可以使用listIterator。

來源

2014-10-31 16:26:27 Radiodef

謝謝。這正是我所期待的。 – Peter 2014-10-31 17:07:20

沒有，沒有漸近複雜性。這是您使用LinkedList支付的價格：清除需要在列表中遍歷。如果你想要更高效的東西，你需要使用不同的數據結構。

如果您有單向鏈表，您實際上會進行兩次遍歷：.remove()調用需要找到給定節點的父節點，而在沒有其他遍歷的情況下，該節點無法完成。

來源

2014-10-31 16:21:44

@FabioCardoso這也需要遍歷列表（在'indexOf（）'調用內）。 – 2014-10-31 16:24:39

如果您需要可預測的迭代順序，請查看LinkedHashMap。你應該得到一個（幾乎）不變的時間刪除 – 2014-10-31 16:46:57

如果您需要訪問具有唯一屬性的集合中的元素，最好使用HashMap來代替，並使用該屬性作爲關鍵字。

Map<Integer, Fruit> fruits = new HashMap<Integer, Fruit>(); 
// ... 
Fruit f = fruits.remove(fruitID);

來源

2014-10-31 16:23:11 Kapep

正如上面的鏈表所述，通常需要遍歷任何操作。避免多次遍歷可能可以用迭代器完成。雖然，如果你能夠提前將果實與fruit.ID聯繫起來，你可能能夠加速你的操作，因爲你可以使緩慢的迭代查找無效。這仍然需要不同的數據結構，即Map（可能是HashMap）。

來源

2014-10-31 16:32:43

關於你的文章，使用HashMap似乎是一個很好的解決方案。此外，如果我們假設您還需要使用fruitID搜索水果到您的集合中，HashMap將使搜索時間幾乎不變。

關於複雜性，您可以根據您使用的數據結構找到有關Simple Notions article的更多信息。

來源

2014-10-31 17:10:41 BodXav

有效地從Java的LinkedList

回答

相關問題