ArrayLists are unordered Lists#1.3.6.1.4.1.33097.1.0.0 which are backed by Arrays#1.3.6.1.4.1.33097.1.1.0. ArrayLists benefit from their fast access time of get and set operations. ArrayLists suffer from doubling in universe size when they run out of space, and have a special type of asymptotic analysis called amortization (which is borrowed from finance) which is used to calculate the cost of this doubling.
u: This is the universe size which is equal to the number of total slots in the underlying array.
n: This is the number of items in the ArrayList.
| Operation | Asymptotic Cost |
|---|---|
| get / set | O(1) |
| add | O(1) Amortized |
| insert | O(n) |
| delete | O(n) |
| find | O(n) |
O(u) is the space cost of an ArrayList.
The actual cost of a JavaArray list depends on the Java Platform (32 vs 64) bit Java.
Exact Cost = u*4 bytes + 8 bytes
The u * 4 bytes includes a 32 bit pointer (4 bytes) for each slot in the Object array, an additional 32 bit pointer (4 bytes) to point from the ArrayList object to the Object array internally, and another 32 bit pointer (4 bytes) to reference the ArrayList object itself.
Exact Cost = u*8 bytes + 16 bytes
The u * 8 bytes includes a 64 bit pointer (8 bytes) for each slot in the Object array, an additional 64 bit pointer (8 bytes) to point from the ArrayList object to the Object array internally, and another 64 bit pointer (8 bytes) to reference the ArrayList object itself.
https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/ArrayList.html