Java ArrayList in Bildern

Hallo! Die heutige Vorlesung ArrayListwird einerseits einfacher und andererseits schwieriger sein als die vorherigen. Schwieriger ist es, denn heute schauen wir „unter die Haube“ ArrayListund untersuchen, was im Betrieb damit passiert. Andererseits wird es in dieser Vorlesung fast keinen Code geben – hauptsächlich Bilder und Erklärungen. Also, los geht's :) Wie Sie bereits wissen, ArrayListbefindet sich in 'a 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! So ist das. Die Standardgröße beträgt [10] .

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

Schauen wir uns zunächst an, wie das Hinzufügen eines neuen Elements aussieht. Zunächst wird geprüft, ob im internen Array genügend Platz vorhanden ist und 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 Zelle des Arrays (das wäre seltsam). Dies bezieht sich auf die Zelle neben dem letzten aktuellen Element. Sein Index wird gleich sein cars.size(). Unsere Liste ist derzeit leer ( cars.size() = 0). Dementsprechend wird der Zelle mit dem Index ein neues Element hinzugefügt 0.

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

Hier ist alles klar. Was passiert, wenn die Einfügung in der Mitte erfolgt, also zwischen mehreren 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);//добавляем ford в ячейку 1, которая уже занята
}

Auch hier wird zunächst geprüft, ob im Array genügend Platz vorhanden ist. Wenn genügend Platz vorhanden ist, werden die Elemente ausgehend von der Zelle, in der wir das neue Element einfügen, nach rechts verschoben . Wir fügen in die Zelle mit Index 1 ein. Das heißt, das Element aus Zelle 3 wird in Zelle 4 kopiert, Element 2 in Zelle 3, Element 1 in Zelle 2. Danach wird unser neues Element an der richtigen Stelle eingefügt. Das vorherige Element ( bugatti) wurde bereits von dort an einen neuen Speicherort kopiert. Lassen Sie uns nun herausfinden, wie dieser Vorgang ablaufen würde, wenn im Array kein Platz zum Einfügen vorhanden wäre. Zunächst wird natürlich geprüft, ob genügend Platz vorhanden ist. Wenn sich herausstellt, dass nicht genügend Platz vorhanden ist, ArrayListwird innerhalb von 'a ein neues Array mit der Größe (Größe von OldArray * 1,5) + 1 erstellt. In unserem Fall hat das neue Array eine Größe von 16 Zellen. Alle aktuellen Elemente werden sofort dorthin kopiert. Das alte Array wird vom Garbage Collector gelöscht und nur das neue, erweiterte Array bleibt übrig. Nun ist freier Platz für das neue Element vorhanden. Wir fügen es in Zelle 3 ein, die belegt ist. Nun beginnt der bekannte Ablauf. Alle Elemente, die bei Index 3 beginnen, werden um eine Zelle nach rechts verschoben und ein neues Element wird stillschweigend hinzugefügt. Und jetzt ist das Einfügen gelungen! Wir haben die Einfügung geklärt. Lassen Sie uns nun über das Entfernen von Elementen sprechen . Wie Sie sich erinnern, sind wir bei der Arbeit mit Arrays auf ein Problem gestoßen: Als wir sie gelöscht haben, sind darin „Löcher“ geblieben. Die einzige Lösung bestand darin, Elemente bei jedem Löschen nach links zu verschieben , und Sie mussten den Code für die Verschiebung selbst schreiben. ArrayListfunktioniert nach dem gleichen Prinzip, allerdings ist dieser Mechanismus darin bereits automatisch implementiert. So sieht es aus: Und am Ende erhalten wir das gewünschte Ergebnis: Das Element lambowurde erfolgreich gelöscht. Hier haben wir eine Entfernung aus der Mitte vorgenommen. Es ist klar, dass das Löschen am Ende der Liste schneller geht, da das gewünschte Element entfernt wird, ohne alle anderen zu verschieben. Werfen wir noch einmal einen Blick auf die Größe des internen Arrays und seine Speicherung im Speicher. Die Array-Erweiterung ist ein Prozess, der eine bestimmte Menge an Ressourcen beansprucht. Daher sollten Sie nicht ArrayListmit der Standardgröße erstellen, wenn Sie sicher sind, dass es mindestens 100 Elemente enthält. Wenn Sie das 100. Element einfügen, wird das interne Array um das Sechsfache erweitert , wobei jedes Mal alle Elemente übertragen 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 bis 133 (gemäß der Formel (Größe des alten Arrays * 1,5) + 1)

Das ist natürlich ressourcenintensiv. Wenn Sie also bereits eine (zumindest ungefähre) Anzahl gespeicherter Elemente kennen, ist es besser, sofort eine Liste mit einem Array einer bestimmten Größe zu erstellen:

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

Jetzt wird ein Array mit 100 Elementen sofort im Speicher zugewiesen, was effizienter ist, da keine Ressourcen für die Erweiterung verschwendet werden. Es gibt auch die andere Seite der Medaille. Wenn Objekte aus dem internen Array entfernt werden ArrayList, wird die Größe nicht automatisch reduziert. Wir haben zum Beispiel ArrayListein internes Array mit 88 Elementen, das vollständig gefüllt ist: Während des Programmlaufs entfernen wir 77 Elemente daraus, und nur 11 verbleiben darin: Haben Sie schon erraten, wo das Problem liegt? Natürlich ineffiziente Speichernutzung! Wir verwenden nur 11 Zellen, während uns Speicher für 88 Elemente zugewiesen ist – das ist achtmal mehr als wir brauchen! Um in diesem Fall eine Optimierung durchzuführen, können Sie eine spezielle Klassenmethode verwenden ArrayList– trimToSize(). Es „kürzt“ die Länge des internen Arrays auf die Anzahl der aktuell darin gespeicherten Elemente. Jetzt wird so viel Speicher zugewiesen, wie benötigt wird! :) :)