如何在Java中使用嵌套迭代器从LinkedList中删除元素

Question

我正在尝试从Java的无序链表中删除重复元素（这是《破解面试》一书中的问题）。

我正在使用同一个List对象上的嵌套迭代器，但在删除项目时出现了ConcurrentModificationException错误。这是我的代码：

Iterator<String> i = list.iterator();   
String curr;
while (i.hasNext()) {
    curr = i.next();
    Iterator<String> j = list.iterator();
    while (j.hasNext()) {
        String runner = j.next();
        if (curr == runner){
            j.remove();
        }
    }
}

这本书中的解决方案使用了LinkedListNode对象，它使得只需改变节点的指针就可以实现，但是否有办法仅使用java.util.LinkedList来解决这个问题？

编辑： 挑战在于不使用临时缓冲区来完成，否则另一个列表就可以解决问题。

- user1796659

---

我会将需要被移除的节点添加到另一个列表中。当你用两个迭代器遍历整个列表后，从主列表中移除那些也在你的“待移除”列表中的项。 - Steve Smith

这仍然使用另一个集合，但是当您迭代列表时，可以将元素添加到“Set”中。如果“Set.add”方法返回false，则从列表中删除该元素。以这种方式执行操作意味着您不必多次迭代列表（一次用于查找重复项，第二次及以上用于删除所有重复项）。 - Slaw

另外，不要使用==比较String，应该使用equals或equalsIgnoreCase。 - Slaw

为什么不直接这样做呢 list.stream().distinct().collect(Collectors.toList());？ - Victor Gubin

@VictorGubin，.distinct() 调用会在内部创建一个临时的 LinkedHashSet。挑战在于不使用临时缓冲区来完成此操作。我的答案提供了一种方法来实现这一点。 - DodgyCodeException

Answer 1

如果您不使用迭代器或foreach循环，就不会收到ConcurrentModificationException异常。例如，您可以像这样做：

List<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 1, 2, 3));

for (int i = 0; i < list.size() - 1; i++) {
    for (int j = i + 1; j < list.size(); j++) {
        if (list.get(i).equals(list.get(j))) {
            list.remove(j);
            j--;
        }
    }
}

System.out.println(list); // [1, 2, 3]

- Golov Pavel

---

谢谢你的回答！如果包括从列表中检索项目，这个程序的运行时间会是多少？ - user1796659

对不起，您能重新表达一下问题吗？ - Golov Pavel

由于链表的属性，我假设使用 list.get(i) 的运行时间为 O(i)。在此基础上，这个算法的总运行时间是多少？ - user1796659

我猜它的时间复杂度是O(n^3)，因为list.get(i)的时间复杂度是O(n/2) ~ O(n)，而我们有嵌套循环，时间复杂度为O(n^2)，因此我们有O(n*n^2)O(n^3)。这不是最好的算法，但它没有使用其他缓冲区。如果我错了，请纠正我。 - Golov Pavel

Answer 2

以下是一个O（N^2）的算法，它不使用任何临时附加集合。从最后一个元素到第二个元素迭代回来，如果列表的当前元素已经在列表中较早地出现，则删除当前元素。

public static void removeDuplicates(List<?> list) {
    ListIterator<?> iter = list.listIterator(list.size());
    for (int index = list.size() - 1; index > 0; index--) {
        Object element = iter.previous();
        if (list.subList(0, index).contains(element))
            iter.remove();
    }
}

测试：

@Test
void removeDuplicatesShouldRemoveAllDuplicates() {
    List<Integer> list = new LinkedList<>(Arrays.asList(1,2,1,3,1,4,5,5,1));
    Main.removeDuplicates(list);
    assertEquals(Arrays.asList(1,2,3,4,5), list);
}

- DodgyCodeException