Come è implementata la struttura degli indici in ArrayList?

In ArrayList, la struttura degli indici è implementata tramite un array interno di oggetti (Object[] elementData). Questo array funge da array dinamico, dove ogni elemento è accessibile tramite indice in tempo costante.

Quando si aggiungono elementi, ArrayList verifica se c'è spazio sufficiente nell'array. Se non c'è, ne viene creato uno nuovo di dimensioni maggiori (solitamente del 50% in più), e gli elementi vengono copiati in esso.

L'accesso agli elementi tramite indice avviene direttamente tramite il riferimento all'array:

E element = (E) elementData[index];

In questo modo, l'indice è semplicemente la posizione nell'array, garantendo un rapido recupero e aggiornamento degli elementi. Tuttavia, inserire o eliminare nel mezzo della lista richiede di spostare gli elementi, operazione che richiede tempo lineare.