dynamisches-array

ArrayList (Dynamic Array)

In short: A list that’s internally based on an array that grows automatically (and typically never automatically shrinks) once more space is needed than is currently available.

In more detail: Once the internal array is full, a larger new array is automatically created on the next insert and the previous content is copied over — invisible to the user of the list. This preserves the fast index access of an array, while the size no longer has to be fixed in advance like for a classic array. Frequent inserting in the middle of the list, though, remains slower than with a linked list.

In Depth

The trick behind a dynamic array lies in its growth strategy: once the internal array is full, the implementation typically doubles the capacity (or increases it by a similar factor), instead of growing by just exactly one element:

Capacity 4, full -> create a new array with capacity 8, copy all 4 elements over
Capacity 8, full -> create a new array with capacity 16, copy all 8 elements over

This may seem wasteful (often more space is reserved than is currently needed), but it’s the reason why inserting at the end still stays very fast on average: a single copy-over is expensive (O(n)), but happens less and less often as the list grows — the cost is spread across many individual insert operations (“amortised complexity”), so inserting at the end still costs O(1) on average, even though an expensive copy-over occurs occasionally in between.

numbers = []          # the list starts empty or with a small internal capacity
numbers.append(1)     # practically always O(1) - occasionally this triggers an internal copy-over

The difference between “size” (the number of elements actually contained) and “capacity” (the size of the internally reserved array) is important for understanding why a dynamic array sometimes occupies more memory than would be needed for the current elements. Some implementations therefore offer an explicit method to free up excess capacity again, when a program knows the list won’t grow further.

The limitation from the underlying array still remains: inserting or deleting in the MIDDLE of the list (not at the end) still requires shifting all subsequent elements — that stays O(n), regardless of the clever growth strategy. Anyone mainly inserting/deleting in the middle is better served by a linked list.

See also: Arrays, List, LinkedList