Arrays
Created: 2025-11-25
Edited: 2025-12-08
Id: 1.3.6.1.4.1.33097.1.1.0
Copywrite 2025 Adligo Inc
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.
Asymptotic Variables
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.
Asymptotic Time Cost (aka. Time Complexity)
| Operation | Asympotic Summary |
|---|---|
| get / set | O(1) |
Asymptotic Space Cost (aka. Space Complexity)
O(u) is the space cost of an ArrayList.
Exact Space Cost
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.
For 32 bit Java Object Arrays
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.
For 32 bit Java short Arrays
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.
For 64 bit Java Object Arrays
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.
For 64 bit Java short Arrays
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.