How do Dynamic Arrays work?

Technology CommunityCategory: ArraysHow do Dynamic Arrays work?
VietMX Staff asked 3 years ago

A simple dynamic array can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array in constant time by using the reserved space until this space is completely consumed.

When all space is consumed, and an additional element is to be added, the underlying fixed-sized array needs to be increased in size. Typically resizing is expensive because you have to allocate a bigger array and copy over all of the elements from the array you have overgrow before we can finally append our item.

Dynamic arrays memory allocation is language specific. For example in C++ arrays are created on the stack, and have automatic storage duration — you don’t need to manually manage memory, but they get destroyed when the function they’re in ends. They necessarily have a fixed size:

int foo[10];

Arrays created with operator new[] have dynamic storage duration and are stored on the heap (technically the “free store”). They can have any size, but you need to allocate and free them yourself since they’re not part of the stack frame:

int* foo = new int[10];
delete[] foo;