A dynamic size array, often simply called a dynamic array, is a data structure that behaves like an array but can automatically grow or shrink in size as elements are added or removed.
According to the reference, a dynamic array, also known by names such as growable array, resizable array, dynamic table, mutable array, or array list, is a random access, variable-size list data structure that allows elements to be added or removed. It's a fundamental data structure available in the standard libraries of many modern programming languages (like ArrayList in Java, std::vector in C++, or list in Python).
How Dynamic Arrays Work
Unlike static arrays, which have a fixed size determined at the time of creation, dynamic arrays can change their capacity during runtime. This flexibility is achieved through a clever mechanism:
- Internal Array: A dynamic array typically uses a static array internally to store elements.
- Capacity vs. Size: It keeps track of two numbers: the current size (number of elements stored) and the capacity (the size of the internal static array).
- Resizing: When you add an element and the current size equals the capacity, the dynamic array allocates a new, larger static array (often doubling the current capacity). It then copies all the elements from the old array to the new one and discards the old array. Similarly, some implementations may shrink the internal array if the size becomes significantly smaller than the capacity.
This resizing operation, while occasionally costly (as it involves copying elements), allows the array to accommodate more elements than initially planned.
Key Characteristics
Based on the definition and common implementations:
- Variable Size: Can grow or shrink at runtime. This is their defining feature.
- Random Access: Like static arrays, elements can be accessed directly using their index (e.g.,
array[5]) in constant time, O(1). This is explicitly mentioned in the reference ("random access"). - Allows Additions/Removals: Elements can be easily added to the end or inserted/removed at specific positions (though insertion/removal in the middle can be slower).
- Efficiency:
- Accessing elements by index is very fast (O(1)).
- Adding an element to the end is typically fast on average (amortized O(1)), because resizing happens infrequently.
- Inserting or removing elements from the beginning or middle can be slower (O(n)) because elements need to be shifted.
Dynamic vs. Static Arrays
Here's a simple comparison:
| Feature | Static Array | Dynamic Array |
|---|---|---|
| Size | Fixed at creation | Variable, can change at runtime |
| Memory | Fixed allocation | Can reallocate and copy during growth |
| Adding Items | Must fit within initial size | Can grow to accommodate more items |
| Complexity (Access) | O(1) | O(1) |
| Complexity (Adding to End) | N/A (fixed size) | Amortized O(1) |
| Complexity (Insert/Remove Middle) | O(n) (if possible/supported) | O(n) |
Practical Uses
Dynamic arrays are widely used because they offer a good balance between the speed of static arrays for access and the flexibility of linked lists for size changes:
- Storing collections of items where the exact number isn't known beforehand.
- Implementing other data structures like stacks and queues.
- As the default list implementation in many programming languages.
In essence, a dynamic array gives you the benefits of an array's fast indexed access while abstracting away the complexity of managing its underlying memory size manually.
