How do Dynamic Arrays work?

Dynamic arrays are a type of data structure that allows for flexible and efficient management of collections of elements. Unlike static arrays, which have a fixed size determined at the time of declaration, dynamic arrays can grow or shrink in size as needed during program execution. Here’s a detailed explanation of how dynamic arrays work:

Memory Allocation and Resizing

Initial Allocation

When a dynamic array is first created, it allocates a certain amount of memory to hold a specific number of elements. This initial size is often small, and the array can expand as more elements are added.

Adding Elements

When an element is added to a dynamic array, the array checks if there is enough allocated memory to accommodate the new element. If there is enough space, the element is simply added. If the array is full, it needs to resize itself to accommodate the new element. This resizing typically involves:

1. Allocating a new block of memory, usually double the size of the current array to reduce the frequency of resizing operations.
2. Copying the existing elements to the new memory block.
3. Adding the new element to the array.
4. Deallocating the old memory block.

This process ensures that adding elements to a dynamic array is efficient on average, even though individual resizing operations can be costly in terms of time and memory.

Removing Elements

When elements are removed from a dynamic array, the array may shrink to free up unused memory. This is often done to avoid wasting memory when the array holds significantly fewer elements than its capacity. The array might shrink when the number of elements falls below a certain threshold, such as half of its current capacity.

Accessing Elements

Elements in a dynamic array are accessed using their index, similar to static arrays. The index provides a direct way to access any element in constant time $$O(1)$$, making dynamic arrays efficient for random access.

Built-in Methods and Properties

Dynamic arrays in many programming languages come with built-in methods that facilitate their manipulation. For example, in JavaScript, the Array object provides methods like push() to add elements, pop() to remove elements, splice() to add or remove elements at specific positions, and the length property to get the current number of elements in the array[1][4][6].

Example in JavaScript

Here’s a simple example demonstrating the use of a dynamic array in JavaScript:

let dynamicArray = [1, 2, 3]; // Initial array with 3 elements

// Adding elements
dynamicArray.push(4); // Adds 4 to the end of the array
dynamicArray.push(5); // Adds 5 to the end of the array

// Removing elements
dynamicArray.pop(); // Removes the last element (5)

// Accessing elements
let elementAtIndex2 = dynamicArray[2]; // Retrieves the element at index 2 (3)

// Using splice to add and remove elements
dynamicArray.splice(1, 0, 6); // Inserts 6 at index ...