Dynamic Arrays and Resizing Conceptually

Fixed arrays require you to know capacity in advance. To provide flexibility, modern languages feature Dynamic Arrays (e.g., ArrayList in Kotlin/Java, std::vector in C++, list in Python).

How can an array resize when physical RAM blocks cannot be expanded in place?

The Internal Mechanism of a Dynamic Array

A dynamic array wraps a standard fixed array with two tracking variables:

1. Size: The number of elements currently stored.
2. Capacity: The total slots available in the underlying fixed array.

Copy codeInternal State:
Size: 3, Capacity: 4
Underlying Array: [ 'A', 'B', 'C', null ]

The Growth Algorithm (Resizing Step)

When you append an item and size == capacity:

1. Allocate New Buffer: A new fixed array is allocated in the heap with a larger capacity (typically 1.5x or 2x the previous capacity).
2. Copy Elements: All existing elements are copied from the old array into the new array.
3. Deallocate Old Buffer: The old array reference is discarded (eligible for Garbage Collection).
4. Insert New Item: The new element is appended, and size increments.

Copy codeFull Capacity (4):
[ A, B, C, D ]  (Attempt to insert E)

Resize (2x -> 8):
Allocate: [ _, _, _, _, _, _, _, _ ]
Copy:     [ A, B, C, D, _, _, _, _ ]
Insert E: [ A, B, C, D, E, _, _, _ ]

Why Not Grow by +1 or a Fixed Constant?

If you grow capacity by a fixed constant (e.g., +1 or +10):

• Appending N items requires resizing O(N) times.
• Each resize copies O(k) elements.
• Total copy cost: 1 + 2 + 3 + ... + N = O(N²).
• Appending N items becomes a disastrously slow quadratic operation!

Geometric Growth and Amortized O(1) Time

By using a multiplicative growth factor (e.g., doubling capacity):

• Most add() operations take O(1) time (simple assignment into an available slot).
• Infrequently, when the array is full, an expensive O(n) copy occurs.

The Amortized Proof (Accounting Method)

Consider inserting N = 16 elements starting with capacity 1:

Copy codeInsert 1: Resize to 1 (1 copy)
Insert 2: Resize to 2 (2 copies)
Insert 3: Resize to 4 (4 copies)
Insert 5: Resize to 8 (8 copies)
Insert 9: Resize to 16 (16 copies)

Total copy operations = 1 + 2 + 4 + 8 + 16 = 31 copies
For N insertions, total copies <= 2N.
Average cost per insertion = (2N copies) / N = ~2 operations = O(1)!

Because the expensive resize occurs exponentially less frequently as the array grows, the amortized time complexity for an append operation is O(1).

Android & Mobile Engineering Optimization: Initial Capacity

In Android development, unnecessary resizes trigger memory allocation spikes and Garbage Collection pauses.

Copy code// Suboptimal: Multiple reallocations and array copies as items are loaded
val userList = ArrayList<User>() 
for (i in 0 until 1000) {
    userList.add(fetchUser(i))
}

// Optimized: Pre-size the backing buffer if item count is known or estimated
val optimizedList = ArrayList<User>(1000) // Exactly 1 allocation, 0 copies!

Summary

• Dynamic arrays provide array indexing speed with variable capacity by wrapping a fixed array.
• When full, a new array with 1.5× or 2× capacity is allocated, and elements are copied.
• Amortized time for append is O(1); worst-case for a single resizing append is O(n).