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

Question

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

我想这很简单LinkedList,但考虑到我对大字节缓冲区的兴趣,我怀疑每个节点的内存成本可能对我的需求而言过于昂贵.

我的理解是法线List具有缓冲支持,其容量通常大于实际数据.当数据填充缓冲区时,将创建一个新缓冲区,并将旧内容传输到新缓冲区.这对于追求结束非常有用,但对于一开始的增长却是可怕的.我的测试,附加/插入一百万个随机整数到List:

• 列出附加时间0.014秒.
• 列出零插入时间173.343sec

Answer 1

具有列表形式但针对两端插入和移除而非针对中间插入和移除进行优化的数据结构称为deque,它是"Double Ended QUEue"的缩写.这些天我不知道标准库是否包含deque.

如果您对构造不可变deques的技术感兴趣,我建议您阅读,以增加复杂性的顺序:

• 我关于不可变数据类型的系列文章,特别是这一篇:https://blogs.msdn.microsoft.com/ericlippert/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended -队列/
• 这个很棒的问题和答案:实现一个不可变的双端队列作为一个平衡的二叉树？
• Chris Okasaki的书"Purely Functional Data Structures"描述了如何通过巧妙地使用惰性构造和memoization在所有操作中创建一个O(1)的双端队列

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