Dynamic Array

Dynamic arrays are the next logical extension of arrays. The dynamic array is able to change its size during program execution. This property gives the dynamic array more power in programs where the programmer does not know how much data will enter the array at any given point.

For example, if you wanted to create a program that kept track of everything you ate during the day, you would need to use a dynamic data structure (one that can grow and shrink during program execution). It needs to be dynamic because you don't know how many different things you might eat during the day. Whenever you eat something, simply append the name of the food to the end of the dynamic data structure. Here, a dynamic array would be a good choice.

Dynamic arrays give the programmer more flexibility during the execution of a program. With a normal array, if the array is completely filled during program execution, there's nothing that the programmer can do. With a dynamic array, one can keep pushing values into the array.

Dynamic arrays are typically initialized with twice the number of initial array elements. This extra space is what allows extra elements to be added to the array. So, if I wanted to make a dynamic array with the following elements, [1, 2], a dynamic array would be created with 4 spaces. This size is maintained until we've added enough elements to fill it. If we tried to add a 5th element, the array would double in size (now with a capacity of 8) and add the 5th element.

When the array needs to double in size, the original array is first copied. Then the program finds a new, larger contiguous area of memory. It then creates a new, doubly large array in that contiguous space, and saves the original array as the first half of the new array.

The following graphic shows this process. A dynamic array is initialized with a single value, 2. Then values are added that force the dynamic array to grow. The total size of the array is often called the capacity, and the size of the actual values is often called the logical size.

Dynamic Array ^[1]

This sample implementation uses realloc to resize the internal memory buffer when more space is needed. If for whatever reason realloc isn't available on your platform, then that line can be replaced with a call to malloc with the new size, a memcpy to copy the contents of the old buffer to the new one, and a free of the old buffer.

Since the item size isn't known until runtime, it is necessary to pass in pointers to the values being read and written to the array. This is where C++ would really shine. With templates, the size could be known at compile-time, and with operator overloading the standard [] array syntax could be used instead of calling functions get and set, resulting in a cleaner API.

DynamicArray.h

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#ifndef DynamicArray_h #define DynamicArray_h #include <stdlib.h> typedef struct { size_t itemSize; /* The size of a single item in the array */ size_t capacity; /* The capacity, eg how much room until resize is needed */ size_t logicalSize; /* The actual number of items, this is always <= capacity */ void *internalArray; /* The internal memory buffer that holds the items */ } DynamicArray; DynamicArray *DynamicArrayCreate(size_t itemSize); void DynamicArrayGet(DynamicArray *dynamicArray, size_t index, void *output); void DynamicArraySet(DynamicArray *dynamicArray, size_t index, const void *input); void DynamicArrayAppend(DynamicArray *dynamicArray, const void *input); void DynamicArrayDispose(DynamicArray *dynamicArray); #endif /* DynamicArray_h */

DynamicArray.c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include "DynamicArray.h" #include <assert.h> #include <string.h> #include <stdio.h> const size_t kInitialCapacity = 10; const float kGrowthFactor = 1.5; DynamicArray *DynamicArrayCreate(size_t itemSize) { DynamicArray *dynamicArray = malloc(sizeof(DynamicArray)); dynamicArray->itemSize = itemSize; dynamicArray->capacity = kInitialCapacity; dynamicArray->logicalSize = 0; dynamicArray->internalArray = malloc(itemSize * kInitialCapacity); return dynamicArray; } void DynamicArrayGet(DynamicArray *dynamicArray, size_t index, void *output) { assert(index < dynamicArray->logicalSize); size_t indexMemoryOffset = index * dynamicArray->itemSize; memcpy(output, dynamicArray->internalArray + indexMemoryOffset, dynamicArray->itemSize); } void DynamicArraySet(DynamicArray *dynamicArray, size_t index, const void *input) { assert(index < dynamicArray->logicalSize); size_t indexMemoryOffset = index * dynamicArray->itemSize; memcpy(dynamicArray->internalArray + indexMemoryOffset, input, dynamicArray->itemSize); } void DynamicArrayAppend(DynamicArray *dynamicArray, const void *input) { if (dynamicArray->logicalSize == dynamicArray->capacity - 1) { dynamicArray->capacity *= kGrowthFactor; dynamicArray->internalArray = realloc(dynamicArray->internalArray, dynamicArray->capacity * dynamicArray->itemSize); } dynamicArray->logicalSize += 1; DynamicArraySet(dynamicArray, dynamicArray->logicalSize - 1, input); } void DynamicArrayDispose(DynamicArray *dynamicArray) { free(dynamicArray->internalArray); free(dynamicArray); }

main.c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <stdio.h> #include <stdlib.h> #include <time.h> #include "DynamicArray.h" int main(int argc, const char * argv[]) { srand((unsigned int)time(NULL)); int iterations = 20; DynamicArray *dynamicArray = DynamicArrayCreate(sizeof(int)); for (int i = 0; i < iterations; i++) { int number = rand() % 10; DynamicArrayAppend(dynamicArray, &number); } for (int i = 0; i < iterations; i++) { int output; DynamicArrayGet(dynamicArray, i, &output); printf("%d\n", output); } DynamicArrayDispose(dynamicArray); return 0; }

The dynamic array introduces some important overhead in both time and space.

Time

If the dynamic array moves itself so that the entire array is contiguous (and so lookup is constant time), growing and moving the array will still take time. In the worst case asymptotically, inserting a new element takes \(O(n)\). However, it's important to look at the amortized analysis to see that the runtime is actually smaller; specifically, \(O(1)\).

\[\begin{array} &&\text{Get - O(1),} &\text{Set - O(1),} \\ &\text{Add*/Delete at end - O(1),} &\text{Add/Delete at beginning - O(n),}\end{array}\]

*amortized analysis

Space

As we saw earlier, the dynamic array can have some excess space. This excess space can be defined as \(capacity - logical size\). In the worst case, this is \(2n - n + 1\). This worst case happens just after a growth of the dynamic array. So, the space used by a dynamic array is \(O(2n)\), for a wasted space factor of \(O(n)\). This simplifies to linear space in big o notation, but it's an important factor to keep in mind when programming.

\[\begin{array} &&\text{Space - O(n)} \end{array}\]

You might think that the programmer can just make an array with an extremely large size to get around the overhead of the dynamic array. But, creating an array that is far bigger than you need is extremely wasteful of computer memory. There will be huge amount of physical disk space that sit, unused, for the duration of your program. It's important for the programmer to understand their program and whether or not it calls for an array or a dynamic array.

In Java, the dynamic array is implemented using an ArrayList. The array that this class implements can be added to. Only the logical size is printed out to the user, so the process of doubling is hidden. This is how the ArrayList works in Java:

Instantiating

1
2
3

>>> ArrayList<String> myArray = new ArrayList<String>();
>>> System.out.print(myArray);
[]

Adding

1
2
3
4
5

>>> ArrayList<String> myArray = new ArrayList<String>();
>>> myArray.add("a");
>>> myArray.add("b");
>>> System.out.print(myArray);
[a, b]

Getting

1
2
3
4

>>> ArrayList<String> myArray = new ArrayList<String>();
>>> myArray.add("a");
>>> System.out.print(myArray.get(0));
a

Setting

To set an index in the ArrayList with a specific value, that index must have had a value added to it. So, to set the value of index 1, we must have pushed two elements to the empty ArrayList.

1
2
3
4
5

>>> ArrayList<String> myArray = new ArrayList<String>();
>>> myArray.add("a");
>>> myArray.set(0, "b");
>>> System.out.print(myArray.get(0));
b

Python's list built-in type is implemented as a dynamic array. Here is how you use the list in Python:

Instantiating

1
2
3

>>> myList = []
>>> myList
[]

Adding

1
2
3

>>> myList.append('hello')
>>> myList
['hello']

Getting

Python, like in many other languages, uses 0-indexing. This means that the first index in the list is 0, not 1. So, accessing index 1 is actually indexing the second element in the list.

1
2
3

>>> myList.append('world')
>>> myList[1]
'world'

Setting

1
2
3
4
5

>>> myList
['hello', 'world']
>>> myList[0] = 'goodbye'
>>> myList
['goodbye', 'world'] 

1. coetzee, D. Wikipedia Dynamic Arrays. Retrieved April 10, 2016, from https://en.wikipedia.org/wiki/Dynamic_array