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.

I would add the nodes that need to be removed to another list. Once you've gone through the whole list with both iterators, remove the items from the main list that are also in your "to remove" list. — Steve Smith, May 14 '19 at 15:02
This still uses another collection, but as you're iterating the list you could add the elements to a `Set`. If the `Set.add` method returns false, remove the element from the list. Doing it this way means you don't have to iterate over the list multiple times (once to find duplicates, second+ to remove all duplicates). — Slaw, May 14 '19 at 15:22
Also, don't compare `String`s with `==`, use `equals` or `equalsIgnoreCase`. — Slaw, May 14 '19 at 15:23
Why don't you simply do it like this `list.stream().distinct().collect(Collectors.toList());` ? — Victor Gubin, May 14 '19 at 15:33
@VictorGubin the .distinct() call creates a temporary LinkedHashSet internally. The challenge is to do this without using a temporary buffer. My answer gives one way of doing this. — DodgyCodeException, May 14 '19 at 16:23

Golov Pavel · Accepted Answer · 2019-05-14T15:29:26.993

2

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]

edited May 14 '19 at 15:29

answered May 14 '19 at 15:26

Golov Pavel

624
5
15

Thanks for the answer! What would the runtime of this be, including retrieving the items from the list? – user1796659 May 14 '19 at 15:28
I'm sorry, can you reformulate the question? – Golov Pavel May 14 '19 at 15:31
1

Because of the properties of a linked list, I'm assuming using `list.get(i)` will have a runtime of O(i). Including this, what would be the total runtime of this algorithm? – user1796659 May 14 '19 at 15:35
I guess that it will be O(n^3), because list.get(i) takes O(n/2) ~ O(n), and we have nested loop ~O(n^2), as result we have O(n*n^2)~O(n^3). It is not the best alghorytm, but it doesn't use other buffers. If I'm wrong, please correct me. – Golov Pavel May 14 '19 at 15:40

DodgyCodeException · Answer 2 · 2019-05-15T14:21:05.367

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

How to remove elements from LinkedList with nested iterators in java

2 Answers2