ArrayLijst in afbeeldingen

Hoi! De les van vandaag ArrayListzal zowel makkelijker als moeilijker zijn dan voorgaande lessen. Het wordt moeilijker omdat we vandaag onder de motorkap gaan kijken ArrayListen bestuderen wat er gebeurt tijdens verschillende operaties. Aan de andere kant zal deze les bijna geen code hebben. Het zijn vooral foto's en uitleg. Nou, laten we gaan :) Zoals je al weet, ArrayListheeft het een gewone array binnenin, die fungeert als een gegevensopslag. In de meeste gevallen specificeren we niet de exacte grootte van de lijst. Maar de interne array moet enige grootte hebben! En dat doet het ook. De standaardgrootte is 10 .

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

Laten we eerst eens kijken hoe het toevoegen van nieuwe elementen eruit ziet. De eerste orde van zaken is om te controleren of de interne array voldoende ruimte heeft in de interne array en of er nog een element in past. Als er ruimte is, wordt het nieuwe element toegevoegd aan het einde van de lijst. Als we "tot het einde" zeggen, bedoelen we niet de laatste positie in de array (dat zou raar zijn). We bedoelen de positie die volgt op het laatste huidige element. De index wordt cars.size(). Onze lijst is momenteel leeg ( cars.size() == 0). Dienovereenkomstig wordt het nieuwe element toegevoegd op positie 0.

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

Dat is duidelijk genoeg. Wat gebeurt er als we in het midden invoegen, dus tussen andere elementen?

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
}

Ook hier wordt eerst gecontroleerd of er voldoende ruimte in de array is. Als er voldoende ruimte is, worden de elementen naar rechts verschoven , te beginnen met de positie waar we het nieuwe element invoegen. We voegen in op positie 1. Met andere woorden, het element van positie 3 wordt gekopieerd naar positie 4, element 2 naar positie 3 en element 1 naar positie 2. Dan wordt ons nieuwe element op zijn plaats ingevoegd. Het vorige element (bugatti) is van daaruit al gekopieerd naar een nieuwe positie. Laten we nu eens kijken hoe dit proces verloopt als er geen plaatsen zijn om nieuwe elementen in de array in te voegen. Uiteraard wordt er eerst gekeken of er voldoende ruimte is. Als er niet genoeg ruimte is, wordt er een nieuwe array gemaakt in deArrayListwaarvan de grootte gelijk is aan de grootte van de oude array maal 1,5 plus 1 In ons geval is de grootte van de nieuwe array 16. Alle huidige elementen worden daar onmiddellijk naartoe gekopieerd. De oude array wordt door de vuilnisman verwijderd en alleen de nieuwe, uitgebreide array blijft over. Nu is er ruimte voor een nieuw element. We steken hem in op positie 3, die bezet is. Nu begint de bekende procedure. Alle elementen, beginnend met index 3, worden een positie naar rechts verschoven en het nieuwe element wordt stilletjes toegevoegd. En klaar is het inbrengen! En we zijn klaar met inbrengen. Laten we het nu hebben over het verwijderen van items . U zult zich herinneren dat we tegen een probleem aanliepen bij het werken met arrays: het verwijderen van elementen maakt "gaten" in een array.bij elke verhuizing, en we moesten elke keer onze eigen code schrijven om deze dienst uit te voeren. ArrayList volgt hetzelfde principe, maar implementeert dit mechanisme al. Zo ziet het eruit: En uiteindelijk krijgen we wat we willen: het lamboelement is verwijderd. Hier hebben we een element uit het midden verwijderd. Het is duidelijk dat het verwijderen van een element aan het einde van de lijst sneller gaat, aangezien het element eenvoudig wordt verwijderd zonder dat alle andere moeten worden verschoven. Laten we het nog even hebben over de afmetingen van de interne array en hoe deze in het geheugen is gerangschikt. Het uitbreiden van een array kost wat middelen. Maak daarom geenArrayListmet de standaardgrootte als u zeker weet dat het ten minste 100 elementen zal hebben. De interne array zou 6 keer moeten zijn uitgebreid tegen de tijd dat u het 100ste element hebt ingevoegd, en alle elementen zouden elke keer moeten worden verschoven.

• van 10 elementen tot 16
• van 16 elementen tot 25
• van 25 tot 38
• van 38 tot 58
• van 58 tot 88
• van 88 tot 133 (dwz grootte van de oude array keer 1,5 plus 1)

Zoals u zich kunt voorstellen, is dit behoorlijk arbeidsintensief. Dus als u het vereiste aantal items al (zelfs bij benadering) weet, is het beter om een ​​lijst te maken met een array van een specifieke grootte:

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

Nu wordt het geheugen voor een array van 100 elementen in één keer toegewezen, waardoor de array efficiënter wordt (deze hoeft niet te worden uitgebreid). Deze strategie heeft ook een keerzijde. Wanneer u objecten verwijdert uit een ArrayList, neemt de grootte van de interne array niet automatisch af. Stel dat we een ArrayListvolledig volledige interne array van 88 elementen hebben: Terwijl het programma draait, verwijderen we 77 elementen, zodat er nog maar 11 over zijn: Heb je al geraden wat het probleem is? Je snapt het, inefficiënt geheugengebruik! We gebruiken hier slechts 11 posities, maar we hebben geheugen toegewezen voor 88 elementen. Dat is 8 keer meer dan we nodig hebben! In dit geval kunnen we ons geheugengebruik optimaliseren met een van de ArrayListspeciale methoden van de klasse:trimToSize(). Deze methode "verkleint" de lengte van de interne array tot het aantal elementen dat er momenteel in is opgeslagen. Nu hebben we alleen zoveel geheugen toegewezen als we nodig hebben! :)