Java LinkedList – List und Deque: Methoden, Beispiel, ArrayDeque

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

• Was sind die Eigenschaften von LinkedList?
• Welche Methoden stammen aus welchem Interface?
• 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 ist die einzige Klasse in diesem Diagramm, die neben Deque ein zweites Collection-Interface implementiert: List. Seit Java 21 erweitern Deque und List außerdem das Interface SequencedCollection. Damit hat LinkedList die Methode reversed(), die eine umgekehrte Sicht auf die Liste liefert. Was das für ein Deque bedeutet, erfährst du im Artikel Queue vs. Deque.

LinkedList Eigenschaften als Deque

Die Klasse java.util.LinkedList implementiert eine klassische doppelt verkettete Liste – und damit die beiden Interfaces List und Deque.

Sie existiert im JDK seit Version 1.2, also deutlich länger als das Deque-Interface, das sie implementiert. Einige Deque-Methoden hatte sie schon vorher, die übrigen kamen mit Einführung von Deque in Java 6 dazu. Welche Methode woher stammt, zeigt der Abschnitt LinkedList-Methoden und ihre Interfaces.

null-Elemente sind erlaubt. Deshalb kann der Rückgabewert null von pollFirst() und peekFirst() zwei Dinge bedeuten: Das Deque ist leer, oder das Element am Kopf ist null. Das Javadoc des Deque-Interfaces rät aus diesem Grund dringend davon ab, null in ein Deque einzufügen, auch wenn die Implementierung es zulässt.

Die Eigenschaften im Detail:

Unterliegende Datenstruktur	Thread-safe?	Blocking/ Non-blocking	Bounded/ Unbounded	Iterator Type
Verkettete Liste	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()- und add()-Methoden des Iterators selbst.

LinkedList-Methoden und ihre Interfaces

LinkedList ist älter als Queue und Deque. Einige ihrer Methoden gab es deshalb schon, bevor ein Interface sie deklarierte. Die folgende Tabelle zeigt, seit welcher Java-Version LinkedList eine Methode hat und welches Interface sie heute deklariert:

Methoden	In LinkedList seit	Deklariert von
addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast()	Java 1.2	Deque (seit Java 6), List und SequencedCollection (seit Java 21)
offer(), peek(), poll(), element(), remove()	Java 5	Queue
offerFirst(), offerLast(), peekFirst(), peekLast(), pollFirst(), pollLast(), push(), pop(), removeFirstOccurrence(), removeLastOccurrence(), descendingIterator()	Java 6	Deque
reversed()	Java 21	Deque, List, SequencedCollection

addFirst() ist also keine Erfindung des Deque-Interfaces: LinkedList hatte die Methode schon in Java 1.2. Java 6 hat sie in Deque übernommen, Java 21 zusätzlich in List und SequencedCollection.

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“.

Auch das Javadoc von ArrayDeque sagt, die Klasse sei als Queue „likely to be faster than LinkedList“.

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

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

Das sind natürlich nur allgemeine Empfehlungen. Wenn du Gründe hast, die für den Einsatz einer LinkedList sprechen, rate ich dir, die Performance der LinkedList für deinen speziellen Anwendungsfall mit alternativen Datenstrukturen zu vergleichen. Ein Grund kann z. B. sein, dass du hauptsächlich in der Mitte einfügst und entnimmst – das ist dann aber nicht die Rolle eines Deques.

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 Elementen 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 threadsicher 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 {
  static void main() {
    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());
  }
}

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

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 doppelt verketteten Liste spielt es für das Einfügen und Entfernen am Anfang und am Ende keine Rolle, wie lang die Liste bereits ist. Der Aufwand für beide Operationen ist 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)

Alle Operationen, die ein Element in der Mitte suchen oder entfernen – contains(), remove(Object), removeFirstOccurrence() und removeLastOccurrence() –, laufen dagegen in O(n). Das gilt auch für den Index-Zugriff get(i) aus dem List-Interface: LinkedList läuft dafür vom näheren Ende aus durch die Liste.

Zusammenfassung und Ausblick

In diesem Artikel hast du die Deque-Implementierung LinkedList kennengelernt: eine doppelt verkettete Liste, die List und Deque zugleich implementiert und null erlaubt. Als Deque ist ArrayDeque fast immer die bessere Wahl – LinkedList lohnt sich nur, wenn du dieselbe Datenstruktur auch als List brauchst.

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