In this post we will implement a dynamic array similar to the ones seen in other programming languages like the std::vector in C++ and ArrayList in Java.
Our header file will contain the structure for our dynamic array and a function to initialize it. Let’s also define the initial capacity here.
A Closer Look at the Struct
The first member of our struct is the array where we will put all the data. To make its data type generic, we use a void pointer. You can think of the void** as an array that can hold any data type.
The second and third member is used for tracking the capacity and the number of items stored in our array.
The rest of the struct members are function pointers for adding, removing, and freeing the allocated memory of our array.
Now it’s time to implement the functionality. Our dynamic array should be able to add and remove elements and resize automatically if needed. We will also need to implement a function for handling the initialization and freeing the allocated memory.
Before adding data to the array, first we need to check if it can still fit. If not we have to resize it. For our implementation, we will double the total capacity every time we need to resize.
Removing an Item and Back swap
For our implementation we just swap the last item of our array to the index to be removed then assign a NULL value to the last item.
One disadvantage of this implementation is that it will change the ordering of the items. But if the sorting is not important, this implementation has the advantage of having a consistent time complexity regardless of the array size.
Let’s try it out
Now that we’re done with the implementation, it’s now time to use it in a test program.
And here is the output
Thanks for reading. Have a nice day!