java在固定时间内删除第i个元素

Question

我正在寻找一种Java数据结构，它具有以下属性：

1. 使用结构内部的索引在O(1)time中删除，同时保持元素的相对顺序（最初排序）
2. 此外，仅在结构的末尾
3. 不需要更新
4. 所有删除后的单次遍历

我尝试过的选项：

• 数组：无法在O(1)时间内删除，因为需要移位。另外，如果我使用HashSet个已删除（或未删除）的元素，那么在遍历数组时，我也必须遍历已删除的元素一次
• 链接列表：删除是O(1)（如果您有要删除的Node的引用，并且它最好是双链接列表），并且不需要移位。但是没有索引，所以我必须从头开始遍历，以确定必须删除的Node
• TreeSet：树集可以维护顺序，删除是O(1)次，但通过元素，而不是结构内部的索引

我正在寻找一个数据结构，可以帮助我在上面提到的任务，如果可能的话，在Java。如果不是内置的，那么我想知道所述数据结构的实现

---

需求： 我想解决一个问题。首先给出一个英文字符字符串，然后对该字符串执行若干操作。每个操作都有一个字符c和一个数字n，这意味着我们必须删除字符c的第n次出现

我的解决方案： 我将创建一个类型为X（我正在寻找的数据结构）的数组，长度为26（每个字符）。我会在第三个槽（从0开始）中添加每个字符，比如d，在字符串本身包含index的对象中。我将对字符串的所有字符执行此操作。如果字符串的长度为^{，则这将花费O(n)的总时间

完成后，我将开始处理查询。每个查询都要求我们删除字符n的第c个匹配项（变量，而不是实际的英文字符c），我们可以在O(1)时间内（根据需要）完成此操作。因此，每次这样的删除都需要O(q)时间，其中q是查询数

然后我们可以生成一个长度与原始字符串相同的charArray。然后遍历X类型的对象数组的每个插槽中剩余的所有元素，并将它们放在各自的位置。完成后，我们可以再次遍历这个charArray，忽略所有的空位置，并从左边的元素构造一个字符串