Dynamic Array

A dynamic array is a resizable array-backed data structure that expands its storage when its current capacity is exhausted. It provides constant-time indexed access in the typical case while making occasional resize operations more expensive.

A dynamic array stores elements in a contiguous backing array. Its logical `size` is the number of elements currently stored, while `capacity` is the amount of storage available before another expansion is required.

When an insertion would exceed the current capacity, the implementation allocates a larger backing array and copies the existing elements into it. The growth policy determines how frequently this happens; common implementations grow by a multiplicative factor rather than by exactly one element.

Access by index is efficient because the location of an element can be calculated directly from its index. Appending is usually `O(1)`, but a resize can require `O(n)` copying. Across many appends, those occasional expensive operations are spread over the sequence, giving amortized `O(1)` append time for typical geometric-growth implementations.

In Java, `ArrayList` is the standard general-purpose dynamic-array collection. It maintains insertion order, permits duplicate elements, and supports efficient indexed reads. It is usually preferred over the legacy synchronized `Vector` when built-in thread safety is not specifically required.

Key points

• Indexed reads are typically `O(1)` because elements are stored in an array.
• Appending is amortized `O(1)` but can be `O(n)` when resizing occurs.
• Resizing requires allocating a new backing array and copying elements.
• `size` counts stored elements; `capacity` describes available backing storage.
• Java's `ArrayList` is the common dynamic-array implementation.

Interview questions

What is a dynamic array, and why is array indexing fast?

A dynamic array uses an array as its backing storage but can replace that storage with a larger array when it runs out of capacity. Because elements occupy array positions, the address of an element can be computed directly from its index. Therefore indexed access is typically `O(1)`. The tradeoff is that resizing requires copying existing elements.

Why is adding to a dynamic array considered amortized `O(1)`?

Most append operations simply place the new element into an unused slot, so they take constant time. Occasionally, capacity is exhausted and the implementation must allocate a larger array and copy the existing elements, which takes `O(n)`. With geometric growth, these expensive copies occur infrequently enough that their cost is spread across many insertions. Thus the average cost per append over a long sequence is amortized `O(1)`.

What happens internally when an `ArrayList` needs more capacity?

The implementation obtains a larger backing array and copies the existing elements into it. The new element can then be placed in the newly available storage. The old backing array becomes eligible for garbage collection once there are no remaining references to it. The exact growth policy is an implementation detail and should not be assumed unless the relevant Java implementation specifies it.

When would you choose `ArrayList` over `LinkedList`?

`ArrayList` is generally useful when the workload needs frequent indexed access or iteration over a sequence. Its contiguous storage gives good cache locality and constant-time indexed reads. Insertions or removals in the middle can require shifting elements, so that workload changes the tradeoff. The choice should therefore follow the dominant operations rather than relying only on the names of the data structures.

How can you reduce resizing overhead when using an `ArrayList`?

If the approximate number of elements is known in advance, the list can be created with an appropriate initial capacity. This can reduce the number of backing-array reallocations and element copies during growth. It does not change the fundamental indexed-access behavior or the amortized append complexity. The capacity should still be chosen reasonably because reserving substantially more memory than needed has a memory cost.