Array that can be resized fast

Question

I'm looking for a kind of array data-type that can easily have items added, without a performance hit.

• System.Array - Redim Preserve copies entire RAM from old to new, as slow as amount of existing elements
• System.Collections.ArrayList - good enough?
• System.Collections.IList - good enough?

Answer 1

You should use the Generic List<> (System.Collections.Generic.List) for this. It operates in constant amortized time.

It also shares the following features with Arrays.

• Fast random access (you can access any element in the list in O(1))
• It's quick to loop over
• Slow to insert and remove objects in the start or middle (since it has to do a copy of the entire listbelieve)

If you need quick insertions and deletions in the beginning or end, use either linked-list or queues

Answer 2

Just to summarize a few data structures:

System.Collections.ArrayList: untyped data structures are obsolete. Use List(of t) instead.

System.Collections.Generic.List(of t): this represents a resizable array. This data structure uses an internal array behind the scenes. Adding items to List is O(1) as long as the underlying array hasn't been filled, otherwise its O(n+1) to resize the internal array and copy the elements over.

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

Adding items is only efficient when adding to the back of the list. Inserting in the middle forces the array to shift all items forward, which is an O(n) operation. Deleting items is also O(n), since the array needs to shift items backward.

System.Collections.Generic.LinkedList(of t): if you don't need random or indexed access to items in your list, for example you only plan to add items and iterate from first to last, then a LinkedList is your friend. Inserts and removals are O(1), lookup is O(n).