Java LinkedList als Deque
(mit Beispiel)

In diesem Artikel erfährst du alles über die Java-Klasse LinkedList in ihrer Rolle als Deque:

• Was sind die Eigenschaften von LinkedList?
• Wann sollte man sie als Deque einsetzen?
• Wie setzt man sie als Deque ein (Java-Beispiel)?
• Welche Zeitkomplexitäten haben die LinkedList-Operationen?

Wir befinden uns hier in der Klassenhierarchie:

LinkedList Eigenschaften als Deque

Die Klasse java.util.LinkedList implementiert eine klassische doppelt verkettete Liste.

Sie existiert im JDK seit Version 1.2, also deutlich länger als das Deque-Interface, das sie implementiert. Die Deque-spezifischen Methoden wurden mit Einführung von Deque in Java 6 hinzugefügt.

Die Eigenschaften im Detail:

¹ Fail-fast: Der Iterator wirft eine ConcurrentModificationException, wenn während der Iteration Elemente in das Deque eingefügt oder aus diesem entnommen werden.

Einsatzempfehlung als Deque

Ich rate grundsätzlich von der Verwendung der LinkedList als Deque ab. Die Gründe findest du im Artikel Unterschied zwischen Array und Linked List. Zusammengefasst:

• Ein Array benötigt deutlich weniger Speicher als eine verkettete Liste.
• Der Zugriff auf die Elemente eines Arrays ist schneller als auf die einer verketteten Liste.
• Verkettete Listen sind für den Garbage Collector "schwer verdaulich".

Wenn du eine Liste benötigst, ist ArrayList meist die bessere Wahl.

Wenn du eine nicht threadsicheres Deque (oder eine nicht threadsichere Queue) benötigst, dann verwende ein ArrayDeque.

Das sind natürlich nur allgemeine Empfehlungen. Solltest du Gründe haben, die für den Einsatz einer LinkedList sprechen (wenn du z. B. hauptsächlich Elemente in der Mitte entnimmst und einfügst – das allerdings nicht in der Rolle eines Deques), dann würde ich dir raten die Performance der LinkedList für deinen speziellen Anwendungsfall mit alternativen Datenstrukturen zu vergleichen.

LinkedList Deque Beispiel

Im folgenden Beispiel siehst du, wie man eine LinkedList in Java verwenden kann. Der Beispielcode zeigt, wie man eine LinkedList erstellt, wie man sie mit zufälligen Elemente befüllt, wie man das Kopf- und Endelement ausgibt und wie man die Elemente letztlich wieder aus der LinkedList entnimmt.

Falls du das ArrayDeque-Tutorial gelesen hast, dürfte dir das Demo bekannt vorkommen. Da sowohl ArrayDeque als auch LinkedList non-blocking und nicht thread-safe sind, kann ich für beide Implementierungen nur die Deque-Grundfunktionen demonstrieren.

Den Code findest du in der Klasse LinkedListDemo im GitHub-Repo.

public class LinkedListDemo {
  public static void main(String[] args) {
    Deque<Integer> deque = new LinkedList<>();

    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)

Hier eine beispielhafte Ausgabe:

deque.offerLast(80)  --> deque = [80]
deque.offerLast(61)  --> deque = [80, 61]
deque.offerLast(63)  --> deque = [80, 61, 63]
deque.offerFirst(30) --> deque = [30, 80, 61, 63]
deque.offerLast(11)  --> deque = [30, 80, 61, 63, 11]
deque.offerLast(33)  --> deque = [30, 80, 61, 63, 11, 33]
deque.offerLast(30)  --> deque = [30, 80, 61, 63, 11, 33, 30]
deque.offerFirst(90) --> deque = [90, 30, 80, 61, 63, 11, 33, 30]

deque.isEmpty()   = false
deque.peekFirst() = 90
deque.peekLast()  = 30

deque.pollFirst() = 90 --> deque = [30, 80, 61, 63, 11, 33, 30]
deque.pollFirst() = 30 --> deque = [80, 61, 63, 11, 33, 30]
deque.pollFirst() = 80 --> deque = [61, 63, 11, 33, 30]
deque.pollFirst() = 61 --> deque = [63, 11, 33, 30]
deque.pollLast()  = 30 --> deque = [63, 11, 33]
deque.pollLast()  = 33 --> deque = [63, 11]
deque.pollLast()  = 11 --> deque = [63]
deque.pollFirst() = 63 --> deque = []

deque.isEmpty()   = true
deque.peekFirst() = null
deque.peekLast()  = null
Code-Sprache: Klartext (plaintext)

Wenn du dir die Ausgabe Zeile für Zeile anschaust, wirst du die Funktionsweise der LinkedList gut nachvollziehen können.

LinkedList Zeitkomplexität

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

Bei einer verketteten Liste spielt es für das Einfügen und Entfernen von Elementen keine Rolle, wie lang die Liste bereits ist. Der Aufwand für beide Operationen ist somit konstant.

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

Anders sieht es in der Regel für die Bestimmung der Größe aus. Um die Elemente der verketteten Liste zu zählen, muss die Liste einmal komplett von vorne bis hinten durchlaufen werden.

Glücklicherweise ist das bei der Java LinkedList nicht der Fall. Diese speichert ihre Größe in einem zusätzlichen Feld und aktualisiert dieses Feld bei jeder Einfüge- und Löschoperation.

Die Zeitkomplexität für LinkedList.size() beträgt also auch: O(1)

Zusammenfassung und Ausblick

In diesem Artikel hast du alles über die Deque-Implementierung LinkedList erfahren.

Im nächsten Teil dieser Serie kommen wir zur ersten threadsicheren Deque-Implementierung: dem ConcurrentLinkedDeque.

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.