Удалить элементы List <String>внутри HashMap за постоянное время

Question

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

Я пытаюсь реализовать алгоритм стабильного брака .

У меня есть men = HashMap<String, List<String>, где я l oop больше men.keySet()

Когда определенное условие выполнено, я получаю ключ, и я должен удалить первый элемент списка с этим ключом:

int someCondition = listIWantToModify;
List<String> temp = men.get(listIWantToModify);
temp.remove(0);
men.replace(listIWantToModify, temp)

Я хочу удалить первый элемент из одного из списков внутри HashMap. Происходит то, что я получаю java.util.ConcurrentModificationException, что, как я полагаю, происходит из-за того, что я и удаляю, и получаю элементы из Списка в одном и том же l oop. Когда я вызываю следующий код:

List<String> replaceWithP = men.get(currentPartner);
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);

Я пытался сделать следующее:

List<String> replaceWithP = new ArrayList<>(men.get(currentPartner));
replaceWithP.remove(0);
men.replace(currentPartner, replaceWithP);

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

Могу ли я в любом случае изменить список внутри в постоянное время, не получая исключения, или мне нужно переосмыслить всю структуру моей реализации?

Если это так, я хотел бы получить некоторые предложения по как это сделать.

Answer 1

Первый элемент ArrayList не может быть удален за постоянное время. Последний может быть. Эта операция удаляет запись с карты за постоянное время:

List<String> temp = men.get(currentPartner);
temp.remove(temp.size()-1);

Если вам нужно удалить первый элемент, вам следует использовать другую структуру данных, например ArrayDeque.

Answer 2

Вам не нужна строка men.replace в первом примере. Вы напрямую изменяете список, который находится на карте. Нет необходимости вводить тот же список снова.