Originariamente inviato da andbin
Aggiungere (o rimuovere) all'inizio o in mezzo invece ha una complessità O(N) perché è necessario spostare gli elementi successivi.
si hai ragione, sfruttando le proprietà dell'arrayList si, ma sfruttando le proprietà solo dell'array, ovvero non preoccupandomi di avere una sorta di array "frammentato", cioè non riempio l'array come un bicchiere, facendoti un esempio:

anke se ho le prime k posizioni dell'array a null, io posso inserire tranquillamente nella posizione k+1, proprio come in un array classico.

l'inserimento alla fine forse nn costerà O(1), secondo i miei calcoli dovrebbe costare O(log n) sia per l'inserimento che per la cancellazione, xkè nel caso ke ho serie di array di 10 collegati tra loro se devo inserire/cancellare in posizione 16 devo:
1-spostarmi in ultima posizione array1, quindi array1.length-1 (la quale ha il riferimento al prossimo array)
2-e andare nella posizione array2[16-(array1.length-1)]

questo dovrebbe costare O(log n) giusto?

evitando il caso limite della ricopia degli elementi che sicuramente costerà O(n).