可以快速调整大小的数组

Question

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

• 系统.数组 - 将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就是您的朋友.插入和删除是O(1),查找是O(n).

Answer 2

您应该使用通用列表<>(System.Collections.Generic.List).它以不变的摊销时间运作.

它还与Arrays共享以下功能.

• 快速随机访问(您可以访问O(1)中列表中的任何元素)
• 它很快就会循环
• 在开始或中间插入和删除对象的速度很慢(因为它必须复制整个列表的副本)

如果您需要在开头或结尾快速插入和删除,请使用链接列表或队列