Erstellen Sie ein dynamisches Array in Java

Java-Arrays haben nach ihrer Erstellung eine feste Länge. Um darüber hinaus Elemente hinzuzufügen, kapseln Sie ein reguläres Array in einer Klasse für ein dynamic array (dynamisches Array). Diese erfasst, wie viele Werte gespeichert sind, und ersetzt ihr internes Array, sobald der Platz nicht mehr ausreicht. Das folgende Beispiel speichert primitive int-Werte, hängt sie am Ende an, entfernt den letzten Wert und kann den Speicherplatz an die aktuelle size (Größe) anpassen.

Ein dynamisches Array mit eigener Logik in Java erstellen

Die Klasse verwaltet drei Zustandswerte: das interne int[], size und capacity. size gibt an, wie viele Werte aktuell gespeichert sind; capacity ist die Länge des internen Arrays. Durch diese getrennte Erfassung kann das Array Plätze reservieren, ohne sie als gespeicherte Werte zu zählen.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

import java.util.Arrays;

public class DynamicArray {
    private int[] values;
    private int size;

    public DynamicArray() {
        values = new int[2];
    }

    public void add(int value) {
        if (size == values.length) {
            int newCapacity = values.length == 0 ? 1 : values.length * 2;
            values = Arrays.copyOf(values, newCapacity);
        }
        values[size] = value;
        size++;
    }

    public void removeLast() {
        if (size == 0) {
            return;
        }
        size--;
        values[size] = 0;
    }

    public void shrinkToSize() {
        values = Arrays.copyOf(values, size);
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return values.length;
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(values, size));
    }

    public static void main(String[] args) {
        DynamicArray numbers = new DynamicArray();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());

        numbers.removeLast();
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());

        numbers.shrinkToSize();
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());
    }
}

Ausgabe:

[10, 20, 30, 40, 50] | size=5 | capacity=8
[10, 20, 30, 40] | size=4 | capacity=8
[10, 20, 30, 40] | size=4 | capacity=4

Nach fünf Hinzufügungen lauten die Werte [10, 20, 30, 40, 50], bei einer Größe von 5 und einer Kapazität von 8. Nach removeLast() lauten die Werte [10, 20, 30, 40], bei einer Größe von 4 und einer Kapazität von 8. Nach shrinkToSize() betragen Größe und Kapazität jeweils 4.

Größe, Kapazität und Vergrößerung verstehen

Der Konstruktor beginnt mit einer Kapazität von 2 und einer Größe von 0. Jeder Aufruf von add prüft, ob die Größe die Kapazität erreicht hat. Wenn das interne Array voll ist, erstellt Arrays.copyOf ein neues Array mit der doppelten Länge und kopiert die vorhandenen Werte hinein. Anschließend wird der nächste Wert am Index size geschrieben und die Größe um eins erhöht.

Bei den fünf gezeigten Hinzufügungen steigt die Kapazität zunächst von 2 auf 4 und dann auf 8. Bei diesen Vergrößerungen werden die gespeicherten Werte kopiert; die freien Plätze im neuen Array stehen für spätere Hinzufügungen bereit. Die Kapazität beschreibt den reservierten Speicherplatz, nicht die Anzahl der Werte. Die Methode toString() kopiert nur den Bereich vor size, sodass freie Plätze nicht als Elemente erscheinen.

Das Kopieren dauert proportional zur Anzahl der kopierten Werte und erfordert vorübergehend beide Arrays. Durch die Verdopplung muss nicht bei jedem Anhängen kopiert werden; ein einzelner Aufruf, der eine Vergrößerung auslöst, führt jedoch weiterhin eine Kopie aus. Diese kleine Klasse soll den Mechanismus veranschaulichen. Für Sammlungen im allgemeinen Einsatz ist Java-ArrayList<Integer> meist die bessere Wahl.

Elemente hinzufügen und entfernen

add unterstützt nur das Anhängen; Einfügen an einem beliebigen Index ist nicht möglich. removeLast verringert die Größe um eins und setzt den frei gewordenen Slot auf den Java-Standardwert für int, also 0. Da int ein primitiver Wert und keine Referenz ist, muss der Slot nicht für die Garbage Collection geleert werden. Das Leeren sorgt lediglich dafür, dass der ungenutzte Teil des internen Arrays vorhersehbare Werte enthält. Ein Aufruf von removeLast, wenn die Größe 0 beträgt, lässt das Objekt unverändert.

Beim Entfernen wird die Kapazität nicht automatisch verkleinert. Rufen Sie shrinkToSize() auf, wenn das Freigeben ungenutzter Array-Plätze wichtiger ist, als Platz für künftige Hinzufügungen vorzuhalten. Auch beim Verkleinern werden die Werte in ein Ersatzarray kopiert. Beträgt die Größe 0, wird die Kapazität auf 0 gesetzt; beim nächsten Aufruf von add wächst sie vor dem Speichern des neuen Werts auf 1. Die Implementierung speichert ausschließlich primitive int-Werte und bietet weder indizierten Zugriff noch das Einfügen oder Entfernen in der Mitte.