C# - 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

Would the LinkedList< T> structure work for you? It's not (in some cases) as intuitive as a straight array, but is very quick.

• AddLast to append to the end
• AddBefore/AddAfter to insert into list
• AddFirst to append to the beginning

It's not so quick for random access however, as you have to iterate over the structure to access your items... however, it has .ToList() and .ToArray() methods to grab a copy of the structure in list/array form so for read access, you could do that in a pinch. The performance increase of the inserts may outweigh the performance decrease of the need for random access or it may not. It will depend entirely on your situation.

There's also this reference which will help you decide which is the right way to go:

http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list

Answer 3

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).

Answer 4

What is "good enough" for you? What exactly do you want to do with that data structure?

No array structure (i.e. O(n) access) allows insertion in the middle without an O(n) runtime; insertion at the end is O(n) worst case an O(1) amortized for self-resizing arrays like ArrayList.

Maybe hashtables (amortized O(1) access and insertion anywhere, but O(n) worst case for insertion) or trees (O(log(n)) for access and insertion anywhere, guaranteed) are better suited.

Answer 5

If speed is your problem, I don't see how the selected answer is any better than using a raw Array, although it resizes itself, it uses the exact same mechanism you would use to resize an array (and should take just a touch longer) UNLESS you are always adding to the end, in which case it should do things a bit smarter because it allocates a chunk at a time instead of just one element.

If you often add near the beginning/middle of your collection and don't index into the middle/end very often, you probably want a Linked List. That will have the fastest insert time and will have great iteration time, it just sucks at indexing (such as looking at the 3rd element from the end, or the 72nd element).