基本泛型数据结构

数据结构:

计算机程序的灵魂

数据结构选取的好坏直接决定了算法效率的高低和实现的复杂程度

数据结构的组织与访问特性,决定了算法的选取与实现

List<T>

用数组保存数据

-数据项查找复杂度为O(n)

-下标查找复杂度为O(1)

当数据空间不够时,扩大1陪空间

将数据从原有缓冲区复制到新的缓冲区中

带来O(n)的数据复制开销

最坏可能带来sizeof(T)*(n-1)的空间浪费 可以使用TrimExcess来缩紧

插入数据时最坏可能会带来n-1次数据复制

-小心InsertRange里面的效率陷阱 对于非System.Generic.ICollection<T>集合的操作

-用Insert插入多个数据可能会导致效率低下。

当删除数据时最坏可能带来n-1次数据复制,

RemoveAt,RemoveRange,RemoveAll的复杂度在同一个数量级上

对于一组数据的删除循环调用RemoveAt效率最低。

提供QuickSort排序和二分查找的方法。

对象在枚举操作时不能够被修改。

非线程安全,在多线程环境中需要竞争条件保护。

构建lock-free的List<T>

SortedList<K,V>

key与value分别保存在二个数组中,

key在数组中有序排列,保证K,v数组中的下标相同

当数据空间不够时,扩大1倍空间

将数据从原有缓冲区复制到新的缓冲区中

带来O(n)的数据复制开销

最坏可能带来sizeof(T)*(n-1)的空间浪费,可以使用TrimExcess来缩紧

以KEY检索数据时复杂度为O(log2N)

采用二分法查找

在添加/插入数据时会先通过二分查找定位

对原有缓冲区的部分数据进行移动,最坏情况下需要移动N-1个元素

非线程安全。

原文地址:https://www.cnblogs.com/chenqingwei/p/1582242.html