CODEWITHSUNDEEP
javaiterator
user1796659
user1796659

Reputation: 79

How to remove elements from LinkedList with nested iterators in java

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.

Upvotes: 3

Views: 421

Answers (2)

DodgyCodeException
DodgyCodeException

Reputation: 6123

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

Upvotes: 1

Golov Pavel
Golov Pavel

Reputation: 672

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]

Upvotes: 2

Related Questions