c# - 可以快速调整大小的数组

Question

我正在寻找一种数组数据类型，它可以轻松添加项目，而不会影响性能。

• System.Array - Redim Preserve 将整个 RAM 从旧的复制到新的，速度与现有元素的数量一样慢
• System.Collections.ArrayList - 够好吗？
• System.Collections.IList - 够好吗？

Answer 1

简单总结几个数据结构:

System.Collections.ArrayList:无类型数据结构已过时。请改用 List(of t)。

System.Collections.Generic.List(of t):这表示一个可调整大小的数组。这个数据结构在幕后使用了一个内部数组。只要底层数组尚未填充，将项目添加到 List 的复杂度为 O(1)，否则调整内部数组的大小并复制元素的复杂度为 O(n+1)。

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

添加项目只有在添加到列表后面时才有效率。在中间插入会强制数组向前移动所有项目，这是一个 O(n) 操作。删除项目也是 O(n)，因为数组需要向后移动项目。

System.Collections.Generic.LinkedList(of t):如果您不需要对列表中的项目进行随机或索引访问，例如您只打算添加项目并从头开始迭代最后，LinkedList 就是你的 friend 。插入和删除是 O(1)，查找是 O(n)。