Java ArrayDeque – Ringpuffer, Beispiel, vs. LinkedList und Stack

In diesem Artikel erfährst du alles über die Klasse java.util.ArrayDeque, die es seit Java 6 gibt:

• Was sind die Eigenschaften von ArrayDeque?
• Wann sollte man es einsetzen?
• Wie setzt man es ein (Java-Beispiel)?
• Welche Zeitkomplexitäten haben die ArrayDeque-Operationen?
• Was unterscheidet ArrayDeque von LinkedList?
• Warum ist ArrayDeque der bessere Stack?

Wir befinden uns an diesem Punkt in der Klassenhierarchie:

Seit Java 21 erweitert Deque außerdem das Interface SequencedCollection. Damit hat auch ArrayDeque die Methode reversed(), die eine umgekehrte Sicht auf das Deque liefert. Was das für ein Deque bedeutet, erfährst du im Artikel Queue vs. Deque.

ArrayDeque Eigenschaften

ArrayDeque basiert – wie der Name schon sagt – auf einem Array. Auf dessen Basis wird ein Ringpuffer („circular array“) implementiert. Wie der funktioniert und wie das Array dabei wächst, erkläre ich im Artikel „Ringpuffer (Ring Buffer)“. Selbst implementieren wir ein solches Deque in einem späteren Teil der Serie, im Artikel „Deque mit einem Array implementieren“.

Das dem ArrayDeque zugrunde liegende Array wächst bei Bedarf, wird jedoch weder automatisch verkleinert, noch kann es manuell verkleinert werden. Der Standardkonstruktor legt ein Array mit 17 Feldern an. Wenn du vorher weißt, wie viele Elemente das Deque aufnehmen wird, gib die Zahl dem Konstruktor new ArrayDeque<>(n) mit – dann muss das Array nicht wachsen, bis diese Zahl erreicht ist.

null-Elemente sind nicht erlaubt (offerFirst(null) wirft eine NullPointerException) – deshalb können pollFirst() und peekFirst() mit dem Rückgabewert null eindeutig „Deque leer“ signalisieren.

Die Eigenschaften im Detail:

Unterliegende Datenstruktur	Thread-safe?	Blocking/ Non-blocking	Bounded/ Unbounded	Iterator Type
Array	Nein	Non-blocking	Unbounded	Fail-fast¹

¹ Fail-fast: Der Iterator wirft eine ConcurrentModificationException, wenn während der Iteration Elemente in das Deque eingefügt oder aus diesem entnommen werden – außer über die remove()-Methode des Iterators selbst.

Einsatzempfehlung

ArrayDeque ist für single-threaded Anwendungen (und nur dafür) eine gute Wahl. Behalte dabei im Auge, dass das zugrunde liegende Array nicht wieder schrumpft.

Für multi-threaded Einsatzzwecke solltest du eines der folgenden Deques verwenden:

• ConcurrentLinkedDeque
• LinkedBlockingDeque

Eine Entscheidungshilfe findest du im Abschnitt „Deque-Implementierungen in Java: Welche einsetzen?“.

ArrayDeque Beispiel

Der folgende Java-Code zeigt, wie man ArrayDeque in Java verwendet. Folgendes passiert:

• Mehrere Zufallselemente werden zufällig am Kopf oder am Ende des Deques eingefügt.
• Es wird ausgegeben, ob das Deque leer ist, und welche Elemente es an Kopf und Ende enthält.
• Dann werden, bis das Deque leer ist, die Elemente an einer zufälligen Seite entnommen und ausgegeben.
• Zuletzt wird noch einmal der Status des Deques angezeigt.

Du findest den Code in der Klasse ArrayDequeDemo im GitHub-Repository.

public class ArrayDequeDemo {
  static void main() {
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < 8; i++) {
      int element = ThreadLocalRandom.current().nextInt(10, 100);
      if (ThreadLocalRandom.current().nextBoolean()) {
        deque.offerFirst(element);
        System.out.println("deque.offerFirst(" + element + ") --> deque = " + deque);
      } else {
        deque.offerLast(element);
        System.out.println("deque.offerLast(" + element + ")  --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
    System.out.println();

    while (!deque.isEmpty()) {
      if (ThreadLocalRandom.current().nextBoolean()) {
        System.out.println("deque.pollFirst() = " + deque.pollFirst()
            + " --> deque = " + deque);
      } else {
        System.out.println("deque.pollLast()  = " + deque.pollLast()
            + " --> deque = " + deque);
      }
    }

    System.out.println();
    System.out.println("deque.isEmpty()   = " + deque.isEmpty());
    System.out.println("deque.peekFirst() = " + deque.peekFirst());
    System.out.println("deque.peekLast()  = " + deque.peekLast());
  }
}

Die Ausgabe des Programms sieht beispielsweise wie folgt aus:

deque.offerLast(25)  --> deque = [25]
deque.offerFirst(15) --> deque = [15, 25]
deque.offerFirst(26) --> deque = [26, 15, 25]
deque.offerFirst(39) --> deque = [39, 26, 15, 25]
deque.offerLast(25)  --> deque = [39, 26, 15, 25, 25]
deque.offerLast(50)  --> deque = [39, 26, 15, 25, 25, 50]
deque.offerFirst(95) --> deque = [95, 39, 26, 15, 25, 25, 50]
deque.offerLast(66)  --> deque = [95, 39, 26, 15, 25, 25, 50, 66]

deque.isEmpty()   = false
deque.peekFirst() = 95
deque.peekLast()  = 66

deque.pollFirst() = 95 --> deque = [39, 26, 15, 25, 25, 50, 66]
deque.pollLast()  = 66 --> deque = [39, 26, 15, 25, 25, 50]
deque.pollLast()  = 50 --> deque = [39, 26, 15, 25, 25]
deque.pollLast()  = 25 --> deque = [39, 26, 15, 25]
deque.pollFirst() = 39 --> deque = [26, 15, 25]
deque.pollLast()  = 25 --> deque = [26, 15]
deque.pollFirst() = 26 --> deque = [15]
deque.pollLast()  = 15 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null

Die Funktionsweise des ArrayDeque ist anhand der Ausgabe sehr schön nachzuvollziehen.

ArrayDeque Zeitkomplexität

(Eine Einführung in das Thema Zeitkomplexität findest du im Artikel „O-Notation und Zeitkomplexität – anschaulich erklärt“.)

Durch die Verwendung eines Ringpuffers („circular array“) müssen weder beim Einfügen in das Deque noch beim Entnehmen aus dem Deque die Elemente innerhalb des Arrays verschoben werden.

Nur wenn das Array voll ist, legt ArrayDeque ein größeres an und kopiert alle Elemente um – das kostet O(n). Weil das Array dabei proportional zu seiner Größe wächst, kommt das selten vor; über viele Einfügeoperationen gemittelt bleiben die Kosten pro Einfügen konstant. Wie das Array wächst, beschreibe ich im Abschnitt „Wachsender Puffer“ des Ringpuffer-Artikels.

Die Zeitkomplexität sowohl für die Enqueue- als auch für die Dequeue-Operationen beträgt somit: amortisiert O(1).

Alle Operationen, die ein Element in der Mitte suchen oder entfernen – contains(), remove(Object), removeFirstOccurrence() und removeLastOccurrence() –, laufen dagegen in O(n).

ArrayDeque vs. LinkedList

Eine alternative Implementierung von Deque ist die LinkedList, die ich im nächsten Teil des Tutorials vorstellen werde.

Der Unterschied zwischen ArrayDeque und LinkedList ist die zugrunde liegende Datenstruktur: Array bzw. verkettete Liste.

ArrayDeque ist in den meisten Fällen schneller als LinkedList. Das sagt auch das Javadoc der Klasse: Als Queue sei ArrayDeque „likely to be faster than LinkedList“. Die Gründe dafür findest du im Artikel Unterschiede zwischen Array und Linked List.

ArrayDeque vs. Stack

Für einen Stack bietet Deque die Methoden push(), pop() und peek(), die am Kopf des Deques arbeiten. Das Javadoc des Deque-Interfaces empfiehlt, ein Deque der alten Klasse java.util.Stack vorzuziehen, und das Javadoc von ArrayDeque ergänzt, die Klasse sei als Stack wahrscheinlich schneller als Stack.

Der Grund: Stack erbt von Vector, und dessen Methoden sind synchronisiert – auch dann, wenn nur ein Thread den Stack benutzt. ArrayDeque verzichtet auf diese Synchronisation. Weitere Unterschiede – Iterationsreihenfolge, Umgang mit leerem Stack, Interface statt Klasse – findest du im Artikel Java Deque vs. Stack.

Zusammenfassung

In diesem Teil der Tutorialserie hast du die Deque-Implementierung ArrayDeque und ihre Eigenschaften kennengelernt. ArrayDeque ist eine gute Wahl für single-threaded Anwendungen – als Queue, als Deque und als Ersatz für die Klasse Stack.