How do Dynamic Arrays actually work ?

Abhiru Karki — Wed, 25 Dec 2024 16:28:36 +0000

Dynamic Arrays might seem simple at first glance, but their inner workings will open your eyes 👀.

But first of all, let's start with the basics.

What are Dynamic Arrays ?

Dynamic Arrays are resizable arrays that can automatically adjust their size when elements are added ➕ or removed ➖.

Unlike Static Arrays which has a fixed size that is determined during compile time, the size of Dynamic Arrays can be adjusted during run time as per the need.

But are Dynamic Arrays really Dynamic ?

Actually Dynamic Arrays are built on top of Static Arrays. Surprising right ? Let's dive deeper 🤿

The Working Mechanism ⚒️

Suppose we have a Dynamic Array myArr[3] = {2, 4, 6} which is already full.

Now, If you want to add a new element to the array according to Dynamic Array, you may think that a new slot will be added to the existing array and the element is then after inserted into it. What if I tell you "YOU ARE WRONG" ? 🤨

The Moment of Truth ✅

What actually happens is that a new array is created with double or greater capacity than the existing array ( no worries, will explain the reason for this too ) , and all of the existing elements are shifted to the new array, as well as new elements, and then the pointer head 🫵 is shifted from the previous array to the new array 🫵, and the previous array is deallocated if necessary.

Now why the new array has double or much greater capacity than the previous array ? 🤨

It's simple.
So that we don't run out of space frequently, which would require us to create a new array every time we add a single new element, increasing the time complexity of the process. Instead, why not just create a little larger but not too large new array to balance the time and space complexity ?

So yeah that was it 🤷

Now you know how Dynamic Arrays actually work. Understanding the mechanics of dynamic arrays is crucial for efficient programming.