适用于Java集合的快速获取和快速删除

Question

我想知道是否有适合“快速”获取（按索引）和“快速”删除的java接口。“快速”是指比更好O(n)。

编辑：只有从集合中随机选择一个元素时才需要get方法。另外，标题应该说“收藏”而不是“界面”。

Answer 1

平衡二叉搜索树具有 O(log n) 次“获取”和“删除”操作。哈希表在 O(1) 时间内实现这些相同的操作。在 Java 中，您可以使用TreeMap或HashMap类。例如：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(0, "hello");
map.put(1, "world");
map.remove(0);

如果您不关心项目的顺序，您可以使用ArrayList. 自然地“得到”是 O(1)。要删除一个项目，将最后一个项目移动到您删除的项目的位置，这会给您一个 O(1) 的“删除”。那是：

temp = list.remove(list.size()-1);
return list.set(index, temp);