Как избежать исключения ConcurrentModificationException при рекурсивном удалении на основе итераторов из LinkedList?

Question

Я пытался эффективно создавать деревья, присваивая дочерний элемент его родителю, а затем удаляя его с помощью it.remove():

for (OgOrganizationTreeDTO parent : parents) {
    setChildren(parent, organizationTree);
}

Вот реализация setChildren функции

private void setChildren(OgOrganizationTreeDTO root, List<OgOrganizationTreeDTO> allOrganizations) {
    if (allOrganizations.isEmpty()) {
        return ;
    }
    Iterator<OgOrganizationTreeDTO> it = allOrganizations.iterator();
    while (it.hasNext()) {
        OgOrganizationTreeDTO potentialChild = it.next();
        if (potentialChild.getIdParentId() != null && potentialChild.getIdParentId().equals(root.getId())) {
            root.addChild(potentialChild);
            it.remove();
            setChildren(potentialChild, allOrganizations);
        }
    }
}

Я использую LinkedList и получаю ConcurrentModificationException.Я решил проблему, передав копию allOrganizations в рекурсивную функцию setChildren, например, new LinkedList<>(allOrganizations), но часть копирования занимает O(n) время, и я этого не хочу.

Я также пытался использовать LinkedBlockingQueue, но обнаружил, что удаление занимает O(n) время.

Я хочу воспользоваться удалением LinkedList O(1), поэтому каждый раз, когда я добавляю дочерний элемент и повторяю его, список уменьшается.

Я также успешно реализовал решениес HashSet, помечая отдельные узлы как видимые, и устанавливая базовый случай на hashSet.size() == allOrganizations.size(), но я все еще продолжаю повторяться по списку того же размера, так что это не поможет мне другим.

Есть ли какие-либоспособ достижения моей цели с использованием LinkedList O(1) remove, или есть еще более эффективный альтернативный подход к этому?

Answer 1

Ну, я не знаю, как сделать это с рекурсией, потому что вы фактически создаете новый итератор в каждом рекурсивном вызове (allOrganizations.iterator () - создает новый экземпляр итератора).Поэтому, когда вы вызываете delete, вы изменяете коллекцию для других итераторов, и именно поэтому она выдает это исключение.

• Одним из решений будет использование некоторого CopyOnWriteList, который допускает одновременное изменение, но это простоПередав копию списка, не изменяя ее, это потребует дополнительной памяти.

• Другим решением будет добавление некоторого свойства в класс OgOrganizationTreeDTO, который помечает, если эта строка уже обработана.В этом случае вместо удаления элемента из списка вы просто отметите его как обработанный.

• Но в любом случае, так как вы спрашиваете о производительности и большом O, я могу предложить вам другое решение, которое имеет O (n) сложность.Конечно, есть некоторый компромисс с большим объемом используемой памяти, но это стандартная проблема памяти и сложности ...

  private static void setChildrenMap(OgOrganizationTreeDTO root, 
       List<OgOrganizationTreeDTO> allOrganizations) {
  
    Map<Integer, OgOrganizationTreeDTO> organizationsMap = new HashMap<>();
    organizationsMap.put(root.getId(), root);
  
    for (OgOrganizationTreeDTO element : allOrganizations) {
      organizationsMap.put(element.getId(), element);
    }
  
    for (OgOrganizationTreeDTO element : allOrganizations) {
       organizationsMap.get(element.getParentId()).addChild(element);
    }
  
  }
  

По сути, выбор элемента из хэш-карты - это постоянное время, поэтому мыиспользуют это, чтобы найти требуемого родителя.Возможно, вам придется добавить некоторые проверки, если вы ожидаете, что элементы с неверными данными, потому что organizationsMap.get(element.getParentId()) может вернуть ноль