Java ArrayDeque (mit Code-Beispielen)

In diesem Artikel erfährst du alles über die Klasse java.util.ArrayDeque:

• 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?

Wir befinden uns an diesem Punkt in der Klassenhierarchie:

ArrayDeque Eigenschaften

ArrayDeque basiert – wie der Name schon sagt – auf einem Array. Auf dessen Basis wird ein Ringpuffer („circular array“) implementiert. Wie der genau funktioniert, erfährst du, wenn wir in einem späteren Teil der Serie selbst ein 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.

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.

Einsatzempfehlung

ArrayDeque ist für single-threaded Anwendungen (und nur dafür) eine gute Wahl. Die Tatsache, dass das zugrunde liegende Array nicht verkleinert werden kann, sollte im Auge behalten werden.

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

• ConcurrentLinkedDeque
• LinkedBlockingDeque

Eine Entscheidungshilfe findest du im Artikel „Deque Implementierungen – 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 {
  public static void main(String[] args) {
    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 Ringbuffers („circular array“) müssen weder beim Einfügen in das Deque noch beim Entnehmen aus dem Deque die Elemente innerhalb des Arrays verschoben werden.

Der Aufwand für die Enqueue- und Dequeue-Operationen ist somit unabhängig von der Anzahl der Elemente im Deque, also konstant.

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

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. Die Gründe dafür findest du im Artikel Unterschiede zwischen Array und Linked List.

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.