c# - 搜索正确的数据结构（添加头、交换、删除……）

Question

我正在寻找一种数据结构，它提供：

1. 在前面添加一个元素
2. 交换两个元素
3. 移除元素
4. 当我添加一个元素（不是在最后一个位置）时，其他元素应该向后滑动（比如在队列中）
5. 访问每个元素
6. 通用会很好，但不是必需的

我在 MSDN 上找到的数据结构不能满足我的要求

• List并且LinkedList不提供交换方法
• 我可以用ArrayList.
• HashTable不提供订单
• Queue并且Stack不提供交换，随机访问，...

我可以编写自己的数据结构，但我不想重新发明轮子，因为 .NET 库非常庞大。

编辑：

我需要一个数据结构来提供类似的东西，比如进程优先级调度程序。第一个条目的优先级最高，最后一个条目的优先级最低。有时我必须更改元素的优先级（交换）或完全删除元素（删除）。我最近添加的元素应该具有最高优先级（这就是我将它添加到前面位置的原因）

Answer 1

您确实需要弄清楚您将多久执行一次这些操作，因为您列出了其中的极端数量。

以下是我对您的想法的看法：

• 如果您已索引 get/set，则实现交换方法是微不足道的。
• 如果您担心复制时间，然后反转您的列表，以便您可以在前面插入便宜的插入，您需要重写一些逻辑来将其拉下来，但这不会停止使用数组作为后端。

另外作为最后一点，您确定您不需要某种自动排序，因为这会使这变得更加容易。

Answer 2

听起来你正在寻找的是一个堆。

维基百科：堆

堆通常用于管理优先级，并且可以在队列顶部拥有最高优先级的项目，并根据从堆中添加或删除的具有不同优先级的项目重新排列。

这是一个具有间隔堆实现的通用集合库：

http://www.itu.dk/research/c5/