ArrayList în imagini

Bună! Lecția de astăzi despre ArrayListva fi atât mai ușoară, cât și mai grea decât lecțiile anterioare. Va fi mai dificil pentru că astăzi vom privi sub capota ArrayListși vom studia ce se întâmplă în timpul diferitelor operațiuni. Pe de altă parte, această lecție nu va avea aproape niciun cod. Sunt mai ales imagini și explicații. Ei bine, să mergem:) După cum știți deja, ArrayListare o matrice obișnuită în interior, care acționează ca un depozit de date. În cele mai multe cazuri, nu specificăm dimensiunea exactă a listei. Dar matricea internă trebuie să aibă o anumită dimensiune! Și așa se întâmplă. Mărimea sa implicită este 10 .

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

Mai întâi, să vedem cum arată adăugarea de elemente noi. Prima ordine de lucru este de a verifica dacă matricea internă are suficient spațiu în matricea internă și dacă se va potrivi încă un element. Dacă există spațiu, atunci noul element este adăugat la sfârșitul listei. Când spunem „până la sfârșit”, nu ne referim la ultima poziție din matrice (ar fi ciudat). Ne referim la poziția care urmează ultimului element curent. Indicele acestuia va fi cars.size(). Lista noastră este momentan goală ( cars.size() == 0). În consecință, noul element va fi adăugat la poziția 0.

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

E destul de clar. Ce se întâmplă dacă introducem la mijloc, adică între alte elemente?

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
}

Din nou, mai întâi se verifică dacă există suficient spațiu în matrice. Dacă există suficient spațiu, atunci elementele sunt deplasate la dreapta , începând cu poziția în care inserăm noul element. Inserăm în poziția 1. Cu alte cuvinte, elementul din poziția 3 este copiat în poziția 4, elementul 2 în poziția 3 și elementul 1 în poziția 2. Apoi noul nostru element este inserat în locul său. Elementul anterior (bugatti) a fost deja copiat de acolo într-o nouă poziție. Acum să vedem cum se întâmplă acest proces dacă nu există locuri pentru a introduce elemente noi în matrice. Desigur, există mai întâi o verificare pentru a vedea dacă există suficient spațiu. Dacă nu există suficient spațiu, atunci este creată o nouă matrice în interiorulArrayLista cărui dimensiune este dimensiunea vechiului tablou înmulțit de 1,5 plus 1 În cazul nostru, dimensiunea noului tablou va fi 16. Toate elementele curente vor fi copiate acolo imediat. Vechea matrice va fi ștearsă de colectorul de gunoi și va rămâne doar noua matrice extinsă. Acum este loc pentru un element nou. Îl inserăm în poziția 3, care este ocupată. Acum începe procedura familiară. Toate elementele, începând cu indicele 3, sunt deplasate cu o poziție spre dreapta, iar noul element este adăugat în liniște. Și inserarea este gata! Și am terminat cu inserarea. Acum să vorbim despre eliminarea elementelor . Vă veți aminti că ne-am confruntat cu o problemă când lucram cu matrice: eliminarea elementelor face „găuri” într-o matrice.cu fiecare eliminare și a trebuit să ne scriem propriul cod de fiecare dată pentru a efectua această schimbare. ArrayList urmează același principiu, dar implementează deja acest mecanism. Așa arată: Și în cele din urmă obținem ceea ce ne dorim: Elementul lamboa fost eliminat. Aici am scos un element din mijloc. În mod clar, eliminarea unui element de la sfârșitul listei este mai rapidă, deoarece elementul este pur și simplu eliminat, fără a fi nevoie să le mutați pe toate celelalte. Să vorbim din nou pentru un moment despre dimensiunile matricei interne și despre modul în care este aranjat în memorie. Extinderea unei matrice necesită anumite resurse. În consecință, nu creați unArrayListcu dimensiunea implicită dacă sunteți sigur că va avea cel puțin 100 de elemente. Matricea internă ar trebui să fie extinsă de 6 ori până când ați inserat al 100-lea element și toate elementele ar trebui să fie mutate de fiecare dată.

• de la 10 elemente la 16
• de la 16 elemente la 25
• de la 25 la 38
• de la 38 la 58
• de la 58 la 88
• de la 88 la 133 (adică dimensiunea matricei vechi înmulțit cu 1,5 plus 1)

După cum vă puteți imagina, acest lucru necesită destul de mult resurse. Deci, dacă știți deja (chiar și aproximativ) numărul necesar de articole, este mai bine să creați o listă cu o matrice de o anumită dimensiune:

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

Acum, memoria pentru o matrice de 100 de elemente va fi alocată dintr-o dată, făcând matricea mai eficientă (nu va fi nevoie să fie extinsă). Această strategie are și un revers. Când eliminați obiecte dintr-un ArrayList, dimensiunea matricei interne nu scade automat. Să presupunem că avem ArrayListo matrice internă complet completă de 88 de elemente: Pe măsură ce programul rulează, eliminăm 77 de elemente, deci rămân doar 11: Ai ghicit deja care este problema? Ai înțeles, folosirea ineficientă a memoriei! Aici folosim doar 11 poziții, dar am alocat memorie pentru 88 de elemente. Este de 8 ori mai mult decât avem nevoie! În acest caz, ne putem optimiza utilizarea memoriei cu una dintre ArrayListmetodele speciale ale clasei:trimToSize(). Această metodă „reduce” lungimea matricei interne până la numărul de elemente stocate în prezent în ea. Acum am alocat doar atâta memorie cât avem nevoie! :)