How to remove elements from LinkedList with nested iterators in java

Question

I am trying to remove duplicate elements from an unordered linked list in Java (a question from Cracking the Coding Interview).

I am using nested iterators over the same List object, but I get a ConcurrentModificationException when I remove an item. This is my code:

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();
        }
    }
}

The solution in the book uses a LinkedListNode object, which makes it possible to just change the pointers of the nodes, but is there any way to solve this using java.util.LinkedList only?

EDIT : The challenge was to do this without using a temporary buffer, otherwise an additional list would do the trick.

Answer 1

If you will not use iterators or foreach cycles, you will not receive ConcurrentModificationException. For example, you can do it like this:

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]

Answer 2

The following is an O(N^2) algorithm that doesn't use any temporary additional collections. Iterating backwards, from the last to the second element, if the current element of the list is already present earlier in the list, then remove the current element.

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:

@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);
}