Data Structures 2/7: Dynamic Arrays

Note: Check out the entire supplemental source code for this blog series.

Dynamic Arrays

An array is arguably the simplest data structure. A dynamic array is just an array that grows indefinitely as new elements are added. When the array is rebuilt, it can make sense to create an array with a larger size than is needed to limit some future rebuilding if new elements are added. There are many different strategies to determine the size of the rebuilt array and each one boils down to a time vs. space tradeoff. The more aggressive the array grows, the fewer rebuilds it will need, but also the more space it will take.

The implementation below starts with an array of size one and doubles the size of the array anytime it needs to be rebuilt. In this implementation, the array will never shrink, but you could implement an array shrinking strategy to reduce the memory footprint should elements be removed.

Implementation

Here we can see a simple implementation of a dynamic array that implements our IDynamicSet<T> interface we defined in the first blog post of this series.

DynamicArray.cs

DynamicArrayNode.cs

Pros

• Dynamic arrays can perform insertions in Θ(1) time (unless the underlying array is full and needs to be rebuilt).

• Dynamic arrays require only Θ(n) space. Essentially, they don’t use any more space than is necessary (in theory).

• Because dynamic arrays store elements in sequential memory, they will experience optimized performance on most hardware and operating systems.

• Although it’s not part of our IDynamicSet<T> interface, dynamic arrays can easily be adapted to provide Θ(1) random access (accessing the nth element).

Cons

• If the capacity of the data structure changes significantly, the underlying array will likely need to be rebuilt many times which is a costly operation.

• Although most insertions take only Θ(1) time, if the underlying array is full and needs to be rebuilt, the insertion will take Θ(n) time.

• The underlying array must be rebuilt after every deletion.

• Even though on the surface dynamic arrays don’t use any extra space, in practice this is often not the case. Often times it makes sense to grow the underlying array to a larger size than is needed to prevent the costly rebuilding should new elements be added.

Use Cases

• Dynamic arrays are useful for a general purpose data structure. When you don’t know how the data structure will be used, a dynamic array provides decent performance and low memory overhead in almost all uses.

• Because of the optimizations associated with elements stored in sequential memory, a dynamic array will perform exceptionally well when repeatedly iterated over.

Dynamic Arrays in C#

• In C#, one of the most widely used data structure classes is System.Collections.Generic.List<T>. Because this class is offered as a general purpose dynamic set, it is implemented as a dynamic array.

Performance