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 是否公开了所需的调用，但您也许可以弄清楚。