Overview
A dynamic array is a data structure that stores elements in an array-like contiguous region and manages its capacity automatically or through explicit resizing. When the current capacity is exhausted, it allocates a larger region and transfers the existing elements.
Purpose
Dynamic arrays combine efficient indexed access with flexible collection size. They are useful when the number of elements changes during program execution and is not known in advance.
Key concepts
name: Core idea; description: The central focus of dynamic arrays is the capability described here: A dynamic array is a resizable array that maintains indexed access while allowing its allocated capacity to grow when additional elements are required.; name: Problem context; description: Dynamic Arrays is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using dynamic arrays, check its assumptions, input requirements, expected output, and resource constraints.
Complexity
operation: Indexed access; time: O(1); operation: Append without resizing; time: O(1); operation: Append with resizing; time: O(n) for copying n existing elements.; operation: Append over a long sequence; time: Amortized O(1) under a suitable geometric growth policy.; operation: Insert at an arbitrary position; time: O(n) in the general case because elements may need to shift.; operation: Search; time: O(n) for an unsorted dynamic array.
Worked example
initialState: elements: 5; 10; size: 3; operation: Append 20.; resizing: The array has no free capacity, so a larger allocation is created. For an illustrative doubling strategy, capacity changes from 3 to 6.; finalState: elements: 5; 10; size: 4; explanation: The existing elements are transferred to the new allocation, and the new value is inserted. Two capacity slots remain unused.
Applications
Managing user lists of unknown size.; Collecting search results.; Building application histories.; Storing records retrieved from APIs.; Implementing stacks and other structures.; Maintaining dynamically changing collections.
Advantages
Flexible size.; Fast indexed access.; Good memory locality.; Convenient append operations.; Less manual memory management than fixed-size arrays.