Understanding Arrays: Random Access, Insertion, Deletion, and Efficiency

An array is a linear list data structure that stores elements of the same type in a contiguous block of memory, allowing direct access by index.

Linear lists arrange data in a single line with at most two neighboring directions, examples include arrays, linked lists, queues, and stacks; non‑linear lists such as binary trees, heaps, and graphs lack simple predecessor‑successor relationships.

Random access is achieved by computing the element’s address using the formula a[i]_address = base_address + i * data_type_size , where base_address is the start address of the memory block and data_type_size is the size of each element (e.g., 4 bytes for an int). This yields O(1) access time.

Insertion complexity ranges from O(1) (when inserting into an unordered array by swapping the target element with the last element) to O(n) in the worst case when shifting elements from the beginning; average insertion is O(n). Deletion follows the same pattern: O(1) when removing the first element, O(n) when removing from arbitrary positions.

To improve efficiency, batch deletions can be deferred by marking elements as removed and performing actual memory compaction only when necessary, similar to the mark‑compact garbage collection algorithm used in JVMs.

When choosing between raw arrays and containers like ArrayList<User> users = new ArrayList<>(10000); , arrays are preferable if the data size is known and operations are simple, avoiding the overhead of dynamic resizing and boxing of primitive types.

Arrays start indexing at 0 because the index directly represents the offset from the base address; using 0 eliminates an extra addition operation in loop bounds, simplifying calculations such as for(int i=0;i<3;i++) versus for(int i=0;i<=2;i++) .