This is an introduction to dynamic array and its implementation
An array is a contiguous area of memory of equal-size elements. Array length is usually fixed, which means you need to specify the number of elements your array can hold ahead of time.
A dynamic array is an array which has an important feature: auto-resizing. With this feature, you can easily expand your array by adding more elements in it, so that you do not need to determine the size ahead of time.
In this tutorial, we will discuss about the implementation of dynamic array by using regular fixed length array.
Below is the thinking process for the design of dynamic array:
- Pre-Create an array with a given size (e.g. an array with size 10). All the elements in this pre-created array are
- Use this pre-created array to represent our dynamic array. So now we have a dynamic array with size 0, and a potential maximum size of 10.
- When we want to append a new element into the dynamic array, we can keep assigning elements to the empty slots of the array, until the array is full.
- When the array is full, and we want to append more elements into the array, what we can do is: create a new array with a larger size (e.g. an array with size 20); then copy the 10 elements in the first array into the new array, and now we can use the new array to represent our dynamic array; now we have a dynamic array with size 10, and a potential maximum size of 20.
The main features we need for this dynamic array class include the followings:
- Get the length of the array
- Access an element in the array
- Append a new element to the array
- Pop the element from the end of the array
- Read/update an element in dynamic array —
- Append in the end of dynamic array:
- If the size of the dynamic array is less than capacity:
- If the size of the dynamic array reached capacity:
O(n)to copy the n elements into the new array; however, after this operation, the next n appends will have time complexity of
O(1)each. So, the amortized time complexity is
(O(n) + O(1) * n) / n = O(2)which is still constant