有效地从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

回答

相关问题