

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
vonLinkedList
?
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:
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());
}
}
Code-Sprache: Java (java)
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
Code-Sprache: Klartext (plaintext)
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.
Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.