ArrayList i bilder

Hej! Dagens lektion om ArrayListblir både lättare och svårare än tidigare lektioner. Det blir svårare eftersom vi idag ska titta under huven på ArrayListoch studera vad som händer under olika operationer. Å andra sidan kommer den här lektionen att ha nästan ingen kod. Det är mest bilder och förklaringar. Nåväl, låt oss gå :) Som du redan vet, ArrayListhar en vanlig array inuti, som fungerar som ett datalager. I de flesta fall anger vi inte den exakta storleken på listan. Men den interna arrayen måste ha en viss storlek! Och så gör det. Dess standardstorlek är 10 .

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

Låt oss först se hur det ser ut att lägga till nya element. Den första uppgiften är att kontrollera om den interna arrayen har tillräckligt med utrymme i den interna arrayen och om ytterligare ett element kommer att passa. Om det finns utrymme läggs det nya elementet till i slutet av listan. När vi säger "till slutet" menar vi inte den sista positionen i arrayen (det vore konstigt). Vi menar positionen efter det sista aktuella elementet. Dess index kommer att vara cars.size(). Vår lista är för närvarande tom ( cars.size() == 0). Följaktligen kommer det nya elementet att läggas till vid position 0.

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

Det är tydligt nog. Vad händer om vi sätter in i mitten, dvs mellan andra element?

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
}

Återigen, först kontrolleras om det finns tillräckligt med utrymme i arrayen. Om det finns tillräckligt med utrymme, flyttas elementen åt höger , med början på positionen där vi infogar det nya elementet. Vi infogar vid position 1. Med andra ord, elementet från position 3 kopieras till position 4, element 2 till position 3 och element 1 till position 2. Sedan infogas vårt nya element på sin plats. Det tidigare elementet (bugatti) har redan kopierats därifrån till en ny position. Låt oss nu titta på hur denna process går till om det inte finns några ställen att infoga nya element i arrayen. Naturligtvis är det först en kontroll för att se om det finns tillräckligt med utrymme. Om det inte finns tillräckligt med utrymme skapas en ny array inutiArrayListvars storlek är storleken på den gamla arrayen gånger 1,5 plus 1 I vårt fall kommer den nya arrayens storlek att vara 16. Alla aktuella element kommer att kopieras dit omedelbart. Den gamla arrayen kommer att raderas av sopsamlaren, och bara den nya, utökade arrayen kommer att finnas kvar. Nu finns det plats för ett nytt element. Vi sätter in den vid position 3, som är upptagen. Nu börjar den välbekanta proceduren. Alla element, som börjar med index 3, flyttas en position åt höger, och det nya elementet läggs till tyst. Och insättningen är klar! Och vi är klara med insättningen. Låt oss nu prata om att ta bort föremål . Du kommer ihåg att vi stötte på ett problem när vi arbetade med arrayer: att ta bort element gör "hål" i en array.med varje borttagning, och vi var tvungna att skriva vår egen kod varje gång för att utföra detta skifte. ArrayList följer samma princip, men den implementerar redan denna mekanism. Så här ser det ut: Och till slut får vi som vi vill: Elementet lambohar tagits bort. Här tog vi bort ett element från mitten. Det är klart att det går snabbare att ta bort ett element från slutet av listan, eftersom elementet helt enkelt tas bort utan att alla andra behöver flyttas. Låt oss prata igen ett ögonblick om dimensionerna för den interna arrayen och hur den är ordnad i minnet. Att utöka en array kräver vissa resurser. Skapa därför inte enArrayListmed standardstorleken om du är säker på att den kommer att ha minst 100 element. Den interna arrayen skulle behöva utökas 6 gånger när du infogade det 100:e elementet, och alla element skulle behöva flyttas varje gång.

• från 10 element till 16
• från 16 element till 25
• från 25 till 38
• från 38 till 58
• från 58 till 88
• från 88 till 133 (dvs. storleken på den gamla matrisen gånger 1,5 plus 1)

Som du kan föreställa dig är detta ganska resurskrävande. Så om du redan vet (till och med ungefär) det erforderliga antalet objekt, är det bättre att skapa en lista med en uppsättning av en specifik storlek:

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

Nu kommer minnet för en array med 100 element att allokeras på en gång, vilket gör arrayen mer effektiv (den behöver inte utökas). Denna strategi har också en baksida. När du tar bort objekt från en ArrayList, minskar inte den interna arrayens storlek automatiskt. Anta att vi har en ArrayListmed en helt full intern array av 88 element: När programmet körs tar vi bort 77 element, så bara 11 återstår: Har du redan gissat vad problemet är? Du förstår, ineffektiv användning av minnet! Vi använder bara 11 positioner här, men vi har allokerat minne för 88 element. Det är 8 gånger mer än vi behöver! I det här fallet kan vi optimera vår minnesanvändning med en av ArrayListklassens speciella metoder:trimToSize(). Denna metod "trimmar" längden på den interna arrayen ner till antalet element som för närvarande är lagrade i den. Nu har vi bara tilldelat så mycket minne som vi behöver! :)