C#常用数据结构

常用数据结构特征以及操作时间复杂度
数据结构 类型及备注 插入和删除 查找
Array 顺序存储的线性表、定长 不支持（这里的插入与删除指会更改表长的行为） O(N)
LinkedList 链式存储的线性表、不定长 O(1) O(N)
List 顺序存储的线性表、不定长、动态扩容 O(N)，结尾则是O(1) O(N)
Stack 栈、不定长、动态扩容 O(1) 只能访问栈顶
Queue 队列、不定长、动态扩容 O(1) 只能访问队列头部
Dictionary 保存键值对、使用开散列法、不定长、动态扩容、长度总为质数 O(1) O(1)
SortedList 保存键值对、内部使用数组实现、保持有序、不定长 O(logN) O(logN)
SortedDictionary 保存键值对、内部使用红黑树实现、保持有序、不定长 O(logN) O(logN)
HashSet 使用开散列法、不定长、动态扩容、长度总为质数、是不含值的字典，故复杂度和它完全相同 O(1) O(1)
SortedSet 内部使用红黑树实现、保持有序、不定长、是不含值的SortedDictionary，故复杂度和它完全相同 O(logN) O(logN)
如何选择数据结构
完美的数据结构应该具备较高的插入、删除效率和查找效率
对于栈和队列，直接使用对应的数据结构即可

数据源不是键值对
数据量大，没有重复数据。使用HashSet，好处是令插入、删除和查找的时间复杂度都降为常数，而且，在大数据量的情况下，O(N)和O(1)区别较明显。这里的大小是相对的，具体还要根据性能测试来确定
数据量大，但可能有重复数据；或数据量小。使用Array，List或LinkedList。当数据的数量是固定的，而且需要使用索引器时使用Array
没有重复数据，且希望集合处于有序状态：使用SortedSet，插入和删除的速度稳定，并且查找的速度提升
有重复数据，且希望集合处于有序状态：没有现成的数据结构提供，可以考虑基于数组实现一个
数据源是键值对
如果数据源是键值对，那么可选项本来就不多。首先当然是类型安全的字典，然后，如果总是希望集合处于有序状态，从SortedList和SortedDictionary中进行权衡
另外对于键值对的情况，如果你的数据源数据很少，可以考虑使用List>替代字典，在数据量小的情形，线性和常熟时间复杂度没有什么区别，但List>比字典初始化要做的事情少多了
————————————————
版权声明：本文为CSDN博主「AaronChenH」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u013457933/article/details/89075209