为索引 0 插入优化的 C# 集合？

Question

哪些 C# 集合最适合零索引插入和追加到末尾？

我想最简单的是 LinkedList，但考虑到我对大字节缓冲区感兴趣，我怀疑每个节点的内存成本对于我的需求来说可能过于昂贵。

我的理解是，一个普通的 List 有一个缓冲区支持，其容量通常大于实际数据。当数据填满缓冲区时，将创建一个新缓冲区，并将旧缓冲区的内容传输到新缓冲区。这对于追加到结尾非常有用，但对于开始时的增长却很糟糕。我的测试，将一百万个随机整数附加/插入到 List:

• 列表附加时间 0.014 秒。
• 列表零插入时间 173.343sec

Answer 1

一种数据结构具有列表形式，但在两端(而非中间)都针对插入和删除进行了优化，称为 deque，它是“Double Ended”的缩写队列”。我不知道这些天标准库是否包含双端队列。

如果您对构建不可变双端队列的技术感兴趣，我建议您按照复杂性递增的顺序阅读:

• 我关于不可变数据类型的系列文章，特别是这一篇:https://blogs.msdn.microsoft.com/ericlippert/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue/
• 这个很棒的 SO 问题和答案:Implement an immutable deque as a balanced binary tree?
• Chris Okasaki 的书“Purely Functional Data Structures”描述了如何通过巧妙地使用惰性构造和内存来创建一个在所有操作中都是 O(1) 的双端队列

如果您希望创建一个可变双端队列，使用与列表相同的技术非常简单。列表只是数组的包装器，其中数组在远端“太大”。要制作可变双端队列，您可以制作一个太大的数组，但数据位于中间，而不是小端。您只需跟踪数据的顶部和底部索引是什么，当您碰到数组的任一端时，重新分配数组并将数据复制到中间。