ArrayList nelle immagini

CIAO! La lezione di oggi ArrayListsarà sia più facile che più difficile delle lezioni precedenti. Sarà più difficile perché oggi guarderemo sotto il cofano ArrayListe studieremo cosa succede durante le varie operazioni. D'altra parte, questa lezione non avrà quasi nessun codice. Sono principalmente immagini e spiegazioni. Bene, andiamo :) Come già sai, ArrayListha un normale array all'interno, che funge da archivio dati. Nella maggior parte dei casi, non specifichiamo la dimensione esatta dell'elenco. Ma l'array interno deve avere una certa dimensione! E così fa. La sua dimensione predefinita è 10 .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Per prima cosa, vediamo come appare l'aggiunta di nuovi elementi. Il primo ordine del giorno è verificare se l'array interno ha spazio sufficiente nell'array interno e se un altro elemento si adatterà. Se c'è spazio, il nuovo elemento viene aggiunto alla fine dell'elenco. Quando diciamo "fino alla fine", non intendiamo l'ultima posizione nell'array (sarebbe strano). Intendiamo la posizione successiva all'ultimo elemento corrente. Il suo indice sarà cars.size(). La nostra lista è attualmente vuota ( cars.size() == 0). Di conseguenza, il nuovo elemento verrà aggiunto alla posizione 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Questo è abbastanza chiaro. Cosa succede se inseriamo nel mezzo, cioè tra altri elementi?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

Ancora una volta, prima c'è un controllo se c'è abbastanza spazio nell'array. Se c'è abbastanza spazio, allora gli elementi vengono spostati a destra , a partire dalla posizione in cui stiamo inserendo il nuovo elemento. Stiamo inserendo nella posizione 1. In altre parole, l'elemento dalla posizione 3 viene copiato nella posizione 4, l'elemento 2 nella posizione 3 e l'elemento 1 nella posizione 2. Quindi il nostro nuovo elemento viene inserito al suo posto. L'elemento precedente (bugatti) è già stato copiato da lì in una nuova posizione. Ora diamo un'occhiata a come avviene questo processo se non ci sono posti per inserire nuovi elementi nell'array. Naturalmente, c'è prima un controllo per vedere se c'è abbastanza spazio. Se non c'è abbastanza spazio, viene creato un nuovo array all'interno del fileArrayListla cui dimensione è la dimensione del vecchio array per 1,5 più 1 Nel nostro caso, la dimensione del nuovo array sarà 16. Tutti gli elementi correnti verranno copiati lì immediatamente. Il vecchio array verrà eliminato dal Garbage Collector e rimarrà solo il nuovo array espanso. Ora c'è spazio per un nuovo elemento. Lo inseriamo nella posizione 3, che è occupata. Ora inizia la procedura familiare. Tutti gli elementi, a partire dall'indice 3, vengono spostati di una posizione a destra e il nuovo elemento viene aggiunto silenziosamente. E l'inserimento è fatto! E abbiamo finito con l'inserimento. Ora parliamo della rimozione degli elementi . Ricorderete che ci siamo imbattuti in un problema lavorando con gli array: la rimozione di elementi crea "buchi" in un array.con ogni rimozione e dovevamo scrivere il nostro codice ogni volta per eseguire questo turno. ArrayList segue lo stesso principio, ma implementa già questo meccanismo. Ecco come appare: E alla fine otteniamo ciò che vogliamo: L' lamboelemento è stato rimosso. Qui abbiamo rimosso un elemento dal centro. Chiaramente, rimuovere un elemento dalla fine della lista è più veloce, poiché l'elemento viene semplicemente rimosso senza la necessità di spostare tutti gli altri. Parliamo ancora per un momento delle dimensioni dell'array interno e di come è organizzato in memoria. L'espansione di un array richiede alcune risorse. Di conseguenza, non creare un fileArrayListcon la dimensione predefinita se sei sicuro che avrà almeno 100 elementi. L'array interno dovrebbe essere espanso 6 volte prima di inserire il centesimo elemento e tutti gli elementi dovrebbero essere spostati ogni volta.

• da 10 elementi a 16
• da 16 elementi a 25
• da 25 a 38
• da 38 a 58
• da 58 a 88
• da 88 a 133 (ovvero la dimensione del vecchio array moltiplicata per 1,5 più 1)

Come puoi immaginare, questo è piuttosto dispendioso in termini di risorse. Quindi, se conosci già (anche approssimativamente) il numero richiesto di elementi, è meglio creare un elenco con un array di una dimensione specifica:

ArrayList<Car> cars = new ArrayList<>(100);

Ora la memoria per un array di 100 elementi verrà allocata tutta in una volta, rendendo l'array più efficiente (non sarà necessario espanderlo). Questa strategia ha anche un rovescio della medaglia. Quando rimuovi oggetti da un ArrayList, la dimensione dell'array interno non diminuisce automaticamente. Supponiamo di avere ArrayListun array interno completamente completo di 88 elementi: mentre il programma viene eseguito, rimuoviamo 77 elementi, quindi ne rimangono solo 11: hai già indovinato qual è il problema? Hai capito, uso inefficiente della memoria! Stiamo usando solo 11 posizioni qui, ma abbiamo allocato memoria per 88 elementi. Questo è 8 volte più di quanto ci serve! In questo caso, possiamo ottimizzare il nostro utilizzo della memoria con uno dei ArrayListmetodi speciali della classe:trimToSize(). Questo metodo "taglia" la lunghezza dell'array interno fino al numero di elementi attualmente memorizzati in esso. Ora abbiamo allocato solo la quantità di memoria di cui abbiamo bisogno! :)