在恒定时间内删除元素列表 在HashMap内部

Question

为解决我的问题而努力。我没有从列表中删除，而是创建了包含列表的类，这些类还包含一个索引，我每次都增加该索引，而不是删除第一个元素。

我正在尝试实现稳定婚姻算法。

我有一个men = HashMap<String, List<String>，我在men.keySet()上循环了>

当满足特定条件时，我会得到一个密钥，并且应该使用该密钥删除列表的第一个元素：

int someCondition = listIWantToModify;
List<String> temp = men.get(listIWantToModify);
temp.remove(0);
men.replace(listIWantToModify, temp)
我想从HashMap内的一个列表中删除第一个元素。发生的是，我得到了java.util.ConcurrentModificationException，我猜这是因为我在同一循环中从列表中删除并获取了项目。当我调用以下代码时：

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 2

），有人告诉我，当我创建新的ArrayList时，它是O（n），因此使我的算法成为O（n ^{3] >）在最坏的情况下。}

无论如何，我是否可以在恒定时间内修改列表而不发生异常，还是需要重新考虑实现的整个结构？

如果是这样，我很乐意提出一些建议。

为解决我的问题而努力。我没有从列表中删除，而是创建了包含列表的类，这些类还包含了我每次都递增的索引，而不是删除第一个...

Answer 1

在第一个示例中，您根本不需要men.replace行。您正在直接修改地图中的列表。无需再次输入相同的列表。

Answer 2

ArrayList的第一项不能在固定时间内删除。最后一个可以。此操作会在固定时间内从地图中删除条目：