Java LinkedHashSet 从末尾移除一些元素

Question

我正在解决一个问题，我需要存储具有无重复和维护顺序要求的元素。我选择使用 LinkedHashSet 因为它满足了我的两个要求。

假设我有这段代码:

 LinkedHashSet hs = new LinkedHashSet();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  if(hs.contains("D")){
       //do something to remove elements added after"D" i-e remove "E", "C" and "F"
       //maybe hs.removeAll(Collection<?>c) ??
   }

谁能指导我删除这些元素的逻辑？

我是否使用了错误的数据结构？如果是这样，那么什么是更好的选择？

Answer 1

如果您使用的是 LinkedHashSet，我认为您可能需要使用迭代器来执行删除操作。也就是说找到元素，然后一直移除，直到到达尾部。这将是 O(n)，但即使您编写了自己的 LinkedHashSet(带有双向链表和哈希集)，您也可以访问原始链接结构，以便可以在 O(1) 中切割链表，但是您仍然需要从 HashSet 中删除您刚刚从链表中删除的所有元素，这将再次产生 O(n) 成本。

所以总而言之，删除元素，然后保留指向该元素的迭代器，并继续向下删除元素，直到到达终点。我不确定 LinkedHashSet 是否公开了所需的调用，但您可能会弄明白。