At Adligo we default to the Java style definition of the word Array. A data structure with a fixed number of slots at creation which can be get or set within O(1) time. Arrays number their indices between 0 and n, where n is a positive integer defined at the Array creation time. Mostly this is in order to differentiate between JavaScript (TypeScript) Arrays, which are usually ArrayLists#1.3.6.1.4.1.33097.1.1.0 implementations.
Arrays may suffer from empty slots which contain null pointers, which waste space.
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 | Asympotic Summary |
|---|---|
| get / set | O(1) |
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. In addition Object arrays are much more expensive than primitive arrays because they use a pointer for each slot.
Exact Cost = u*4 bytes + 4 bytes
The u * 4 bytes includes a 32 bit pointer (4 bytes) for each slot in a Object array, and a 32 bit pointer (4 bytes) to reference the Array Object itself.
Exact Cost = u*2 bytes + 4 bytes
The u * 2 bytes includes 16 bits for each short in the array, and a 32 bit pointer (4 bytes) to reference the Array Object itself.
Exact Cost = u*8 bytes + 8 bytes
The u * 8 bytes includes a 64 bit pointer (8 bytes) for each slot in a Object array, and a 64 bit pointer (8 bytes) to reference the Array Object itself.
Exact Cost = u*2 bytes + 8 bytes
The u * 2 bytes includes 16 bits for each short in the array, and a 64 bit pointer (8 bytes) to reference the Array Object itself.