Como é que a estrutura de índices é implementada no ArrayList?

No ArrayList, a estrutura de índices é implementada através de um array interno de objetos (Object[] elementData). Este array funciona como um array dinâmico, onde cada elemento é acessível por índice em tempo constante.

Ao adicionar elementos, o ArrayList verifica se há espaço suficiente no array. Se não houver, um novo array de maior tamanho (normalmente 50% maior) é criado, e os elementos são copiados para ele.

O acesso aos elementos por índice é feito diretamente através da referência ao array:

E element = (E) elementData[index];

Assim, o índice é simplesmente a posição no array, o que garante uma recuperação e atualização rápidas dos elementos. No entanto, inserir ou remover no meio da lista requer deslocar os elementos, o que leva tempo linear.