ArrayList i bilder

Hei! Dagens leksjon om ArrayListvil være både enklere og vanskeligere enn tidligere leksjoner. Det blir vanskeligere fordi vi i dag skal se under panseret ArrayListog studere hva som skjer under ulike operasjoner. På den annen side vil denne leksjonen nesten ikke ha noen kode. Det er mest bilder og forklaringer. Vel, la oss gå:) Som du allerede vet, ArrayListhar en vanlig array inni, som fungerer som et datalager. I de fleste tilfeller spesifiserer vi ikke den nøyaktige størrelsen på listen. Men den interne matrisen må ha en viss størrelse! Og det gjør det. Standardstørrelsen er 10 .

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

La oss først se hvordan det ser ut å legge til nye elementer. Den første oppgaven er å sjekke om den interne matrisen har nok plass i den interne matrisen og om ett element til vil passe. Hvis det er plass, legges det nye elementet til på slutten av listen. Når vi sier "til slutten", mener vi ikke den siste posisjonen i matrisen (det ville vært rart). Vi mener posisjonen etter det siste gjeldende elementet. Indeksen vil være cars.size(). Listen vår er for øyeblikket tom ( cars.size() == 0). Følgelig vil det nye elementet bli lagt til i posisjon 0.

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

Det er tydelig nok. Hva skjer hvis vi setter inn i midten, altså mellom andre elementer?

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
}

Igjen, først er det en sjekk om det er nok plass i arrayet. Hvis det er nok plass, flyttes elementene til høyre , og starter med posisjonen der vi setter inn det nye elementet. Vi setter inn ved posisjon 1. Med andre ord, elementet fra posisjon 3 kopieres til posisjon 4, element 2 til posisjon 3, og element 1 til posisjon 2. Deretter settes vårt nye element inn på plass. Det forrige elementet (bugatti) er allerede kopiert derfra til en ny posisjon. La oss nå se på hvordan denne prosessen skjer hvis det ikke er noen steder å sette inn nye elementer i matrisen. Naturligvis er det først en sjekk for å se om det er nok plass. Hvis det ikke er nok plass, opprettes en ny matrise inne iArrayListhvis størrelse er størrelsen på den gamle matrisen ganger 1,5 pluss 1 I vårt tilfelle vil den nye matrisens størrelse være 16. Alle de gjeldende elementene vil bli kopiert dit umiddelbart. Den gamle matrisen vil bli slettet av søppelsamleren, og bare den nye, utvidede matrisen vil være igjen. Nå er det plass til et nytt element. Vi setter den inn i posisjon 3, som er opptatt. Nå starter den kjente prosedyren. Alle elementene, som starter med indeks 3, flyttes en posisjon til høyre, og det nye elementet legges stille til. Og innsettingen er ferdig! Og vi er ferdige med innsetting. La oss nå snakke om å fjerne elementer . Du vil huske at vi fikk et problem når vi jobbet med matriser: fjerning av elementer lager "hull" i en matrise.med hver fjerning, og vi måtte skrive vår egen kode hver gang for å utføre dette skiftet. ArrayList følger samme prinsipp, men den implementerer allerede denne mekanismen. Slik ser det ut: Og til slutt får vi det vi vil ha: Elementet lamboer fjernet. Her fjernet vi et element fra midten. Det er klart at det går raskere å fjerne et element fra slutten av listen, siden elementet ganske enkelt fjernes uten å måtte flytte alle de andre. La oss snakke igjen et øyeblikk om dimensjonene til den interne matrisen og hvordan den er ordnet i minnet. Å utvide en matrise krever noen ressurser. Følgelig, ikke lag enArrayListmed standardstørrelsen hvis du er sikker på at den vil ha minst 100 elementer. Den interne matrisen må utvides 6 ganger når du satte inn det 100. elementet, og alle elementene måtte forskyves hver gang.

• fra 10 elementer til 16
• fra 16 elementer til 25
• fra 25 til 38
• fra 38 til 58
• fra 58 til 88
• fra 88 til 133 (dvs. størrelsen på den gamle matrisen ganger 1,5 pluss 1)

Som du kan forestille deg er dette ganske ressurskrevende. Så hvis du allerede vet (til og med omtrentlig) det nødvendige antallet elementer, er det bedre å lage en liste med en rekke av en bestemt størrelse:

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

Nå vil minnet for en matrise på 100 elementer bli allokert på en gang, noe som gjør matrisen mer effektiv (det trenger ikke å utvides). Denne strategien har også en bakside. Når du fjerner objekter fra en ArrayList, reduseres ikke størrelsen på den interne matrisen automatisk. Anta at vi har en ArrayListmed en helt full intern matrise på 88 elementer: Mens programmet kjører, fjerner vi 77 elementer, så bare 11 gjenstår: Har du allerede gjettet hva problemet er? Du skjønner, ineffektiv bruk av minne! Vi bruker bare 11 posisjoner her, men vi har allokert minne for 88 elementer. Det er 8 ganger mer enn vi trenger! I dette tilfellet kan vi optimere minnebruken vår med en av ArrayListklassens spesialmetoder:trimToSize(). Denne metoden "trimmer" lengden på den interne matrisen ned til antall elementer som for øyeblikket er lagret i den. Nå har vi bare tildelt så mye minne som vi trenger! :)