Kuidas on ArrayListi indeksistruktuur realiseeritud?

ArrayList sisemine indeksistruktuur on rakendatud sisemise objektide massiiviga (Object[] elementData). See massiiv toimib dünaamilise massiivina, kus iga element on juurdepääsetav indeksiga konstantses ajas.

Elementide lisamisel kontrollib ArrayList, kas on massiivis piisavalt ruumi. Kui ei, luuakse uus suurem massiiv (tavaliselt 50% suurem), ja elemendid kopeeritakse sinna.

Juurdepääs elementidele indeksiga toimub otse massiivile viidates:

E element = (E) elementData[index];

Seega on indeks lihtsalt positsioon massiivis, mis tagab kiire elemendi saamise ja uuendamise. Kuid, lisamine või kustutamine keskel nõuab elementide nihutamist, mis võtab lineaarset aega.