ArrayList in Bildern

Hallo! Die heutige Lektion ArrayListwird sowohl einfacher als auch schwieriger sein als die vorherigen Lektionen. Es wird schwieriger, denn heute werden wir einen Blick unter die Haube werfen ArrayListund untersuchen, was bei verschiedenen Operationen passiert. Andererseits wird diese Lektion fast keinen Code enthalten. Es sind hauptsächlich Bilder und Erklärungen. Nun, los geht's :) Wie Sie bereits wissen, ArrayListenthält es ein gewöhnliches Array, das als Datenspeicher fungiert. In den meisten Fällen geben wir die genaue Größe der Liste nicht an. Aber das interne Array muss eine gewisse Größe haben! Und so ist es auch. Die Standardgröße beträgt 10 .

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

Sehen wir uns zunächst an, wie das Hinzufügen neuer Elemente aussieht. Zunächst muss geprüft werden, ob im internen Array genügend Platz vorhanden ist und ob ein weiteres Element hineinpasst. Wenn Platz vorhanden ist, wird das neue Element am Ende der Liste hinzugefügt. Wenn wir „bis zum Ende“ sagen, meinen wir nicht die letzte Position im Array (das wäre seltsam). Wir meinen die Position nach dem letzten aktuellen Element. Sein Index wird sein cars.size(). Unsere Liste ist derzeit leer ( cars.size() == 0). Dementsprechend wird das neue Element an Position 0 hinzugefügt.

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

Das ist klar genug. Was passiert, wenn wir in der Mitte, also zwischen anderen Elementen, einfügen?

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
}

Auch hier wird zunächst geprüft, ob im Array genügend Platz vorhanden ist. Wenn genügend Platz vorhanden ist, werden die Elemente nach rechts verschoben , beginnend mit der Position, an der wir das neue Element einfügen. Wir fügen an Position 1 ein. Mit anderen Worten: Das Element von Position 3 wird an Position 4, Element 2 an Position 3 und Element 1 an Position 2 kopiert. Dann wird an seiner Stelle unser neues Element eingefügt. Das vorherige Element (bugatti) wurde von dort bereits an eine neue Position kopiert. Schauen wir uns nun an, wie dieser Prozess abläuft, wenn es keine Orte gibt, an denen neue Elemente in das Array eingefügt werden können. Selbstverständlich wird zunächst geprüft, ob genügend Platz vorhanden ist. Wenn nicht genügend Platz vorhanden ist, wird im Inneren ein neues Array erstelltArrayListdessen Größe der Größe des alten Arrays mal 1,5 plus 1 entspricht. In unserem Fall beträgt die Größe des neuen Arrays 16. Alle aktuellen Elemente werden sofort dorthin kopiert. Das alte Array wird vom Garbage Collector gelöscht und nur das neue, erweiterte Array bleibt übrig. Jetzt ist Platz für ein neues Element. Wir fügen es an Position 3 ein, die besetzt ist. Nun beginnt der bekannte Ablauf. Alle Elemente, beginnend mit Index 3, werden um eine Position nach rechts verschoben und das neue Element wird stillschweigend hinzugefügt. Und fertig ist das Einfügen! Und wir sind mit dem Einfügen fertig. Lassen Sie uns nun über das Entfernen von Elementen sprechen . Sie werden sich erinnern, dass wir bei der Arbeit mit Arrays auf ein Problem gestoßen sind: Durch das Entfernen von Elementen entstehen „Löcher“ in einem Array.mit jeder Entfernung, und wir mussten jedes Mal unseren eigenen Code schreiben, um diese Verschiebung durchzuführen. ArrayList folgt dem gleichen Prinzip, implementiert diesen Mechanismus jedoch bereits. So sieht es aus: Und am Ende bekommen wir, was wir wollen: Das lamboElement wurde entfernt. Hier haben wir ein Element aus der Mitte entfernt. Das Entfernen eines Elements vom Ende der Liste geht eindeutig schneller, da das Element einfach entfernt wird, ohne dass alle anderen verschoben werden müssen. Lassen Sie uns noch einmal kurz über die Abmessungen des internen Arrays und seine Anordnung im Speicher sprechen. Das Erweitern eines Arrays erfordert einige Ressourcen. Erstellen Sie daher keineArrayListmit der Standardgröße, wenn Sie sicher sind, dass es mindestens 100 Elemente enthält. Das interne Array müsste bis zum Einfügen des 100. Elements um das Sechsfache erweitert werden , und jedes Mal müssten alle Elemente verschoben werden.

• von 10 bis 16 Elementen
• von 16 Elementen auf 25
• von 25 bis 38
• von 38 bis 58
• von 58 bis 88
• von 88 auf 133 (d. h. Größe des alten Arrays mal 1,5 plus 1)

Wie Sie sich vorstellen können, ist dies ziemlich ressourcenintensiv. Wenn Sie also bereits (auch nur annähernd) die erforderliche Anzahl an Elementen kennen, ist es besser, eine Liste mit einem Array einer bestimmten Größe zu erstellen:

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

Jetzt wird der Speicher für ein Array mit 100 Elementen auf einmal zugewiesen, wodurch das Array effizienter wird (es muss nicht erweitert werden). Diese Strategie hat auch eine Kehrseite. Wenn Sie Objekte aus einem entfernen ArrayList, verringert sich die Größe des internen Arrays nicht automatisch. Angenommen, wir haben ein System ArrayListmit einem komplett vollständigen internen Array von 88 Elementen: Während das Programm läuft, entfernen wir 77 Elemente, sodass nur noch 11 übrig bleiben: Haben Sie schon erraten, wo das Problem liegt? Sie haben es verstanden, ineffiziente Speichernutzung! Wir verwenden hier nur 11 Positionen, haben aber Speicher für 88 Elemente reserviert. Das ist achtmal mehr als wir brauchen! In diesem Fall können wir unsere Speichernutzung mit einer der ArrayListspeziellen Methoden der Klasse optimieren:trimToSize(). Diese Methode „kürzt“ die Länge des internen Arrays auf die Anzahl der aktuell darin gespeicherten Elemente. Jetzt haben wir nur so viel Speicher zugewiesen, wie wir brauchen! :) :)