Как удалить элементы из LinkedList с помощью вложенных итераторов в Java - PullRequest
Новая
       17

Как удалить элементы из LinkedList с помощью вложенных итераторов в Java

3 голосов
/ 14 мая 2019

Я пытаюсь удалить дублирующиеся элементы из неупорядоченного связанного списка в Java (вопрос из интервью Cracking the Coding).

Я использую вложенные итераторы для того же объекта 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?

РЕДАКТИРОВАТЬ : Задача состояла в том, чтобы сделать это без использования временного буфера, иначе дополнительный список мог бы сработать.

Ответы [ 2 ]

2 голосов
/ 14 мая 2019

Если вы не будете использовать итераторы или циклы 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]
1 голос
/ 14 мая 2019

Ниже приведен алгоритм 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: 

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