Dynamische Arrays in Java

Bei der Erstellung von Programmen unterschiedlicher Komplexität verwendet jeder Entwickler viele Datentypen, darunter auch Arrays. Diese Struktur eignet sich gut für die Aufbewahrung eines Satzes eines Typs, bietet eine hervorragende Leistung und ist im Allgemeinen praktisch. Ein wesentlicher Nachteil von Arrays besteht darin, dass sie statisch sind: Ihre Größe muss im Voraus festgelegt werden. Programmierer wissen jedoch noch nicht, wie sie die Zukunft vorhersagen können (es sei denn, es erscheint natürlich eine KI, die Informationen unglaublich schnell verarbeitet und alle Ereignisse vorhersagen kann). Aus diesem Grund haben wir eine Struktur erstellt, die ihre Größe ändern kann, während das Programm läuft. Es heißt dynamisches Array .

Dynamische Arrays im JavaRush-Kurs

Dieses Thema wird auf Stufe 7 und teilweise auf Stufe 8 des JavaRush-Kurses in der Java-Syntax-Quest sehr verständlich und klar behandelt . Im Laufe mehrerer Vorlesungen und bis zu 18 Aufgaben werden Schlüsselthemen, Arten dynamischer Arrays und deren Unterschiede, einschließlich der Leistung, behandelt. Dieses Thema ist äußerst wichtig, da dynamische Arrays den Entwickler von Depressionen und Kopfschmerzen befreien und unglaublich viel Zeit sparen.

Was ist ein dynamisches Array?

Ein dynamisches Array ist ein Array, dessen Größe sich während der Programmausführung ändern kann. In Java spielen diese Rolle hauptsächlich die Klassen ArrayList und LinkedList. Im Gegensatz zu Arrays enthalten ArrayList und LinkedList nur Referenzdatentypen, das heißt, sie können nur Objekte speichern. Glücklicherweise verfügt Java über Autoboxing- und Autounboxing-Mechanismen, mit denen Sie primitive Typen in dynamischen Arrays speichern können. Wie ein statisches Array ist ein dynamisches Array homogen, das heißt, es kann einen einzelnen Datentyp speichern. Dank des Vererbungsmechanismus und der richtigen Verwendung von Schnittstellen ist es jedoch möglich, in einem dynamischen Array eine ganze Reihe verschiedener Klassen zu speichern, die von einer gemeinsamen Klasse geerbt werden. Mehr dazu weiter unten. Das heißt, ein statisches Array funktioniert so: Und ein dynamisches Array in Java funktioniert wie folgt (Fortsetzung des Diagramms aus dem dritten Schritt): Java verwendet eine spezielle native Funktion, um ein Array zu kopieren, daher ist eine solche „Verschiebung“ nicht sehr teuer.

Warum brauchen wir ein dynamisches Array?

Ein dynamisches Array in Java wird verwendet, um Mengen homogener Daten zu verarbeiten, deren Größe zum Zeitpunkt des Schreibens des Programms unbekannt ist. Beispielsweise möchten Sie möglicherweise die Daten jedes Clients zwischenspeichern, der die Anwendung derzeit verwendet. Es ist unmöglich, die Anzahl dieser Kunden im Voraus vorherzusagen. Ohne dynamische Arrays kann dieses Problem mit den folgenden Optionen gelöst werden:

1. Erstellen Sie ein großes Array, das mit 100-prozentiger Wahrscheinlichkeit den Bedarf abdeckt.
2. Erstellen Sie ein statisches Array, das als Puffer fungiert.
3. Wenden Sie andere dynamische Strukturen an, z. B. Mengen.

Die erste Option eignet sich nur bei einem streng begrenzten Sortiment. In anderen Fällen nimmt ein solches Array viel Speicherplatz ein, was äußerst ineffizient ist. Der zweite Schritt erfordert die Implementierung zusätzlicher Mechanismen zum Löschen, Lesen usw. des Puffers. Der dritte hat aufgrund der unterschiedlichen Funktionalität auch Nachteile.

Was macht ein dynamisches Array in Java?

In der Java-Sprache fungieren die Klassen ArrayList und LinkedList als dynamisches Array. Am häufigsten wird ArrayList verwendet, da es im Gegensatz zu LinkedList, das das Konzept einer doppelt verknüpften Liste implementiert, als klassisches Array fungiert. Wir werden etwas später darüber sprechen.

ArrayList, LinkedList – Konzepte und Betriebsregeln

ArrayList ist ein klassisches Array, das während der Programmausführung erweitert werden kann. Es basiert auf einem regulären Array: Seine Größe beträgt bei der Erstellung 10 Elemente. Mit zunehmender Größe erhöht sich die Kapazität. Die Regeln, nach denen ArrayList funktioniert:

• Genau wie ein statisches Array wird es von 0 an indiziert;
• Das Einfügen am Ende und der Zugriff per Index erfolgen sehr schnell - O(1);
• Um ein Element am Anfang oder in der Mitte einzufügen, müssen Sie alle Elemente eine Zelle nach rechts kopieren und dann ein neues Element an der gewünschten Position einfügen;
• Der Zugriff nach Wert hängt von der Anzahl der Elemente ab – O(n);
• Im Gegensatz zu einem klassischen Array kann es Nullen speichern;

Bei LinkedList ist alles etwas komplizierter: Es basiert auf einer doppelt verketteten Liste. Das heißt, strukturell besteht dieses dynamische Java-Array aus einer Reihe verstreuter Objekte, die aufeinander verweisen. Mit Bildern ist es einfacher zu erklären. Innerhalb von LinkedList haben wir ein Hauptobjekt Head, das Informationen über die Anzahl der Elemente sowie einen Link zum ersten und letzten Element speichert: Jetzt ist das Feld size = 0, firstund last = null. Jedes dieser Liste hinzugefügte Element ist der Inhalt eines separaten internen Objekts. Fügen wir ein Element hinzu Johnny: Jetzt haben wir einen Knoten mit dem Wert „Johnny“. Beim Hauptelement verweisen die Links zum ersten und letzten Element auf den neuen Knoten. Dieses Objekt verfügt auch über Links zu den vorherigen und nächsten Elementen. Der Link zum vorherigen Element ist immer null, da dies das erste Element ist, und der Link zum nächsten Element ist immer null, da es noch nicht existiert. Beheben wir das: Ein neues Element mit dem Wert „Watson“ wurde hinzugefügt, das zum zweiten Element wurde. Bitte beachten Sie, dass das erste Element ein Feld hat next, das auf das nächste Element zeigt, und das neue Element ein Feld hat previous, das auf das vorherige zeigt. Beim Hauptelement zeigt der Link zum letzten Element nun auf den neuen Knoten. Das folgende Diagramm zeigt, wie Elemente zur Mitte der Liste hinzugefügt werden: Ein neues Element „Hamish“ wurde hinzugefügt. Um es in die Mitte der Liste einzufügen, ordnen Sie einfach die Links den Elementen neu zu, wie in der Abbildung gezeigt. Diese Abbildungen erläutern den Prozess einer doppelt verketteten Liste auf der obersten Ebene, ohne ins Detail zu gehen. Um die Geschichte von LinkedList zusammenzufassen, können wir mehrere Regeln für seine Funktionsweise ableiten:

• Genau wie ein Array wird es von 0 an indiziert;
• Der Zugriff auf das erste und letzte Element hängt nicht von der Anzahl der Elemente ab – O(1);
• Das Abrufen eines Elements über den Index, das Einfügen oder Löschen aus der Mitte einer Liste hängt von der Anzahl der Elemente ab – O(n);
• Sie können den Iteratormechanismus verwenden: Das Einfügen und Löschen erfolgt dann in konstanter Zeit.
• Im Gegensatz zu einem klassischen Array kann es Nullen speichern.

Codebeispiele

Gehen wir einige Beispiele durch. Die Codeausschnitte enthalten Beispiele für ArrayList und LinkedList.

Schaffung

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Ein Element hinzufügen

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

Auf den ersten Blick führen die add()AND- Methoden addLast()die gleiche Funktionalität aus, aber die Methode add()kam von der Schnittstelle zu LinkedList Listund die Methode addLastkam von der Schnittstelle Deque. LinkedList implementiert beide Schnittstellen. In diesem Fall empfiehlt es sich, die Methode zu verwenden, die für den Kontext am besten geeignet ist. Wenn LinkedList als Warteschlange verwendet wird, verwenden Sie am besten die addLast. Wenn LinkedList als Liste verwendet wird, wäre die Verwendung sinnvoll add().

Ein Element entfernen

// Удаление Element по индексу
arrayList.remove(0);
// Удаление Element по значению
arrayList.remove("Johnny");

// Удаление первого Element в списке
linkedList.removeFirst();
// Удаление первого Element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего Element в списке
linkedList.removeLast();
// Удаление первого вхождения Element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения Element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Wenn ein Objekt per Index gelöscht wird, gibt die Methode das gelöschte Objekt zurück. Wenn ein Objekt nach Wert gelöscht wird (oder das erste oder letzte Element einer LinkedList gelöscht wird), gibt die Methode „ true“ zurück , wenn das Objekt gefunden und gelöscht wird, andernfalls „false“ .

Auf ein Element zugreifen und die Liste durchsuchen

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск Element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения Element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого Element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего Element
String lastLinkedElement = linkedList.getLast();

// Поиск Element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения Element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

In einer Schleife laufen

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Hier lohnt es sich, ein paar Worte zur Suche zu sagen. Viele unerfahrene Entwickler beginnen bei der Suche nach einem Element in einer Liste die Suche in einer Schleife und vergleichen alle Elemente mit dem gesuchten, obwohl Methoden indexOf()und vorhanden sind lastIndexOf(). Sie können die Methode auch verwenden, contains()um festzustellen, ob ein Element in der Liste enthalten ist:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Links zur weiteren Lektüre

1. Hier gibt es einen hervorragenden Artikel zum Entfernen von Elementen aus einer ArrayList. Aufgrund der Tatsache, dass es sich um ein dynamisches Java-Array handelt , gibt es beim Entfernen von Elementen viele Feinheiten.
2. Die Funktionsweise von ArrayList wird hier ausführlich erläutert .
3. Ein bisschen mehr über LinkedList.
4. Ein paar Artikel von Habr über ArrayList und LinkedList .