Static vs Dynamic Arrays
Static arrays have fixed capacity, while dynamic arrays such as ArrayList or vector grow by occasionally allocating a larger backing array and copying elements.
Capacity Is Not Length
A static array has a fixed capacity chosen at creation time. If you create space for 10 integers, there are exactly 10 integer slots. The array may represent fewer meaningful values, but the allocated storage does not grow by itself.
A dynamic array separates size from capacity. Size is the number of meaningful elements. Capacity is the length of the hidden backing array. Java ArrayList, C++ vector, and similar structures expose the dynamic behavior while still relying on an ordinary array underneath.
Why Append Is Amortized O(1)
Appending is cheap while there is unused capacity: write the new value at size, then increment size. That is O(1). The expensive case happens when the backing array is full. The structure allocates a larger array, usually about double the old capacity, copies all existing elements, and then appends the new one.
That resize costs O(n) for that single operation, but it does not happen often. After doubling, there is a long run of cheap appends before the next resize. Spread the copying cost across those future appends and the average cost per append is still O(1) amortized.
Middle Operations Still Shift
Dynamic resizing solves capacity growth, not arbitrary insertion. Inserting at the front or middle requires shifting every later element one step to make room. Deleting from the front or middle requires shifting every later element left to close the gap.
That movement is why middle insertion and deletion are O(n) even for ArrayList or vector. The backing array gives fast indexing and append, but it cannot make elements teleport around gaps.
Choosing the Right Tool
Use a static array when the size is known, memory predictability matters, or primitive storage is important. Use a dynamic array when you need indexed access plus growth at the end. Most interview solutions in Java use arrays for fixed-size helper state and ArrayList when the output size is not known in advance.
If your algorithm performs many front insertions or deletions, a dynamic array is usually the wrong structure. Consider a deque, linked structure, heap, or a different algorithmic pattern depending on the access requirements.
Key Takeaways
- Static arrays have fixed capacity; dynamic arrays manage a larger backing array internally.
- Appending to a dynamic array is amortized **O(1)** because expensive resizes are rare.
- A resize is **O(n)** because existing elements must be copied into new storage.
- Insertion or deletion at the front or middle remains **O(n)** because elements shift.