Как сохранить ссылку на элементы из коллекции для доступности O (1) в Java

Question

Я новичок в Java. Я попытался сохранить итераторы элементов LinkedList на карте и удалить их позже:

Map<Integer, Iterator<Integer>> map = new HashMap<>();
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1);
map.put(1, list.iterator());
list.addFirst(2);
map.put(2, list.iterator());

Iterator<Integer> iter = map.get(1);
iter.next();
iter.remove(); // list is supposed to be [2]

Однако возникает ConcurrentModificationException. Я думаю, что как только я добавляю «2» в список, итератор «1» истекает, верно?

В C ++ list<int>::iterator представляет указатель узла из связанного списка, который остается постоянным и доступен всякий раз, когда в список добавляются новые узлы. Я немного запутался в этом в Java.

Извините за путаницу. Теперь я знаю, что Iterator обычно используется в итерациях, а не для «определения местоположения» элемента, что немного отличается от такового в C ++.

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

Есть ли какой-либо связанный вид Коллекции или Утилита? Или, может быть, мне придется самому реализовать DeLinkedList и DeLinkedNode. Заранее спасибо.

Answer 1

Вместо LinkedList используйте ConcurrentLinkedDeque. В этом случае итераторы будут работать так, как вы надеетесь. ConcurrentLinkedDeque.

Answer 2

Если вы хотите упорядочить, а также вставить и удалить связанный список O (1) вместе с поиском O (1) таблицы ha sh, LinkedHashSet, вероятно, ваш лучший bet.

A LinkedHashSet - это Set, сохраняющий порядок вставки. Таким образом, вы можете делать такие вещи, как:

import java.util.LinkedHashSet;

...

LinkedHashSet<Integer> set = new LinkedHashSet();
set.add(2);
set.add(1);

set.remove(1);

Несколько предостережений:

• Это Set, поэтому вы не сможете хранить более одной копии элемента.
• Нет эквивалента addFirst. Пункты всегда добавляются в конец.