c# - C#中集合数据类型的比较

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。




Improve this question




有谁知道对不同 C# 集合类型的一个很好的概述？我正在寻找显示哪些基本操作的内容，例如 Add , Remove , RemoveLast等支持，并提供相对性能。

对于各种泛型类，它会特别有趣 - 如果它显示例如。如果 List<T> 之间的性能存在差异哪里T是一个类，其中 T是一个结构。

对于抽象数据结构，比较链表，哈希表等等，开始将是一个不错的备忘单。谢谢!

Answer 1

以下内容原文摘自MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc (但此链接已失效)。



如上图所示，内容最初以表格形式提供(StackOverflow 不支持)。

鉴于图像不容易在下面编入索引，这是信息到列表的某种粗略的编程转换:

大批

添加到末尾: O(n)

从末尾删除: O(n)

在中间插入: O(n)

从中间移除: O(n)

随机访问: O(1)

按顺序访问: O(1)

搜索特定元素: O(n)

备注:最有效地使用内存；在数据大小固定的情况下使用。

列表

添加到末尾: best case O(1); worst case O(n)

从末尾删除: O(1)

在中间插入: O(n)

从中间移除: O(n)

随机访问: O(1)

按顺序访问: O(1)

搜索特定元素: O(n)

备注:实现已针对速度进行了优化。在许多情况下，List 将是最佳选择。

收藏

添加到末尾: best case O(1); worst case O(n)

从末尾删除: O(1)

在中间插入: O(n)

从中间移除: O(n)

随机访问: O(1)

有序访问: O(1)

搜索特定元素: O(n)

备注: List 是更好的选择，除非公开暴露为 API。

链表

添加到末尾: O(1)

从末尾删除: O(1)

在中间插入: O(1)

从中间移除: O(1)

随机访问: O(n)

按顺序访问: O(1)

搜索特定元素: O(n)

备注:许多操作很快，但要注意缓存一致性。

堆

添加到末尾: best case O(1); worst case O(n)

从末尾删除: O(1)

在中间插入: N/A

从中间移除: N/A

随机访问: N/A

按顺序访问: N/A

搜索特定元素: N/A

备注:不应出于性能原因选择，而是出于算法原因选择。

队列

添加到末尾: best case O(1); worst case O(n)

从末尾删除: O(1)

在中间插入: N/A

从中间移除: N/A

随机访问: N/A

按顺序访问: N/A

搜索特定元素: N/A

备注:不应出于性能原因选择，而是出于算法原因选择。

字典

添加到末尾: best case O(1); worst case O(n)

从末尾删除: O(1)

在中间插入: best case O(1); worst case O(n)

从中间移除: O(1)

随机访问: O(1)*

按顺序访问: O(1)*

搜索特定元素: O(1)

备注:虽然有序访问时间是常数时间，但由于查找键的开销，它通常比其他结构慢。