Queue mit einer Linked List implementieren

Im letzten Teil dieser Tutorialserie habe ich dir gezeigt, wie man eine Queue mit Stacks implementiert. In diesem Teil werden wir eine Queue mit einer verketteten Liste implementieren. Falls du neu in die Serie einsteigst: Was eine Queue ist und wie das FIFO-Prinzip funktioniert, erklärt der erste Teil.

Der Algorithmus – Schritt für Schritt

Unsere Queue besteht aus zwei Referenzen auf Listenknoten: einer head- und einer tail-Referenz.

Die head-Referenz zeigt auf einen Listenknoten, der das vorderste Element der Queue enthält sowie einen next-Zeiger auf einen zweiten Listenknoten. Dieser wiederum enthält das zweite Element und einen Zeiger auf den dritten Listenknoten, usw.

Der letzte Knoten wird sowohl vom next-Zeiger des vorletzten Knotens als auch vom tail-Zeiger referenziert. Er enthält das letzte Queue-Element, und dessen next-Referenz zeigt auf null.

Die folgende Grafik zeigt eine Beispiel-Queue, in die die Elemente „banana“, „cherry“ und „grape“ (in dieser Reihenfolge) eingefügt wurden:

Wie gelangen wir zu diesem Zustand?

Enqueue-Algorithmus

Wir beginnen mit einer leeren Queue. Sowohl head- als auch tail-Referenz sind null.

Das erste Element fügen wir in die Queue ein, indem wir es in einen Listenknoten wrappen und sowohl head als auch tail auf diesen Knoten zeigen lassen:

Weitere Elemente fügen wir wie folgt ein:

1. Wir wrappen das einzufügende Element in einem neuen Listenknoten.
2. Wir lassen den next-Zeiger des letzten Knotens, also tail.next, auf den neuen Knoten zeigen.
3. Wir lassen ebenso tail auf den neuen Knoten zeigen.

In der folgenden Grafik siehst du, wie ein zweites Element, „cherry“, in die Beispiel-Queue eingefügt wird:

Dequeue-Algorithmus

Die Entnahme des Kopf-Elements mit dequeue() funktioniert dann wie folgt:

1. Wir merken uns das Element des Knotens, auf den head zeigt (im Beispiel wäre das „banana“).
2. Wir lassen head auf head.next zeigen (im Beispiel auf den Knoten, der „cherry“ wrappt). Falls head danach null sein sollte (die Queue also leer ist), setzen wir auch tail auf null.
3. Wir geben das in Schritt 1 gemerkte Element zurück (im Beispiel „banana“).
4. In einer Programmiersprache mit Garbage Collector (z. B. Java) löscht dieser den nicht mehr referenzierten Knoten; in anderen Sprachen (wie C++) müssten wir ihn manuell löschen.

Die folgende Grafik soll die vier Schritte verdeutlichen:

Der gestrichelte Rahmen um den „banana“-Knoten in Schritt 2 und 3 soll darstellen, dass dieser Knoten zu diesem Zeitpunkt nicht mehr referenziert wird.

Quellcode für die Queue mit einer Linked List

Der folgende Code zeigt die Implementierung einer Queue mit einer verketteten Liste (LinkedListQueue im GitHub-Repo). Die Klasse für die Knoten, Node, findest du ganz am Ende als statische innere Klasse.

public class LinkedListQueue<E> implements Queue<E> {

  private Node<E> head;
  private Node<E> tail;

  @Override
  public void enqueue(E element) {
    Node<E> newNode = new Node<>(element);
    if (isEmpty()) {
      head = tail = newNode;
    } else {
      tail.next = newNode;
      tail = newNode;
    }
  }

  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    E element = head.element;
    head = head.next;
    if (head == null) {
      tail = null;
    }
    return element;
  }

  @Override
  public E peek() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return head.element;
  }

  @Override
  public boolean isEmpty() {
    return head == null;
  }

  private static class Node<E> {
    final E element;
    Node<E> next;

    Node(E element) {
      this.element = element;
    }
  }
}

Beachte, dass LinkedListQueue nicht das java.util.Queue-Interface implementiert. Dieses erbt von java.util.Collection, sodass wir wesentlich mehr Methoden implementieren müssten.

Stattdessen habe ich für dieses Tutorial ein eigenes Queue-Interface geschrieben, das nur die Methoden enqueue(), dequeue(), peek() und isEmpty() definiert:

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}

Javas eigene LinkedList implementiert übrigens das java.util.Queue-Interface – du kannst sie also direkt als Queue einsetzen. Wie das geht und welche Implementierungen das JDK sonst noch mitbringt, zeige ich dir im Artikel über das Queue-Interface in Java.

Wie du die LinkedListQueue-Klasse einsetzt, kannst du dir im Demo-Programm QueueDemo anschauen.

Zeitkomplexität der Queue mit einer Linked List

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

Beide Operationen setzen nur Referenzen um: enqueue() hängt den neuen Knoten an tail an, dequeue() rückt head um einen Knoten weiter. Kein Durchlaufen der Liste, kein Umkopieren – egal, wie viele Elemente die Queue enthält.

Die Zeitkomplexität von Enqueue und Dequeue ist also O(1).

Vor- und Nachteile der Implementierung der Queue mit einer Linked List

Die Implementierung mit einer verketteten Liste hat gegenüber der Array-Variante zwei Vorteile: Sie verschwendet keinen Speicherplatz durch unbelegte Array-Felder, und sie braucht weder ein Umkopieren in ein größeres Array noch die Ringpuffer-Logik einer Array-Queue, deren Kopf und Ende mit jedem Enqueue und Dequeue durch das Array wandern.

Dafür belegt jedes Element ein eigenes Knoten-Objekt, das mehr Speicherplatz kostet als ein Array-Feld. Das Anlegen eines Knotens kostet mehr Zeit als das Setzen eines Array-Feldes. Und die verkettete Liste macht dem Garbage Collector mehr Arbeit, da dieser bei jedem Durchgang der kompletten Kette folgen muss.

In der Regel überwiegen die Vorteile der Array-Implementierung, sodass diese häufiger anzutreffen ist.

Ausblick

Im nächsten Teil des Tutorials zeige ich dir, wie man eine Queue mit einem Array implementiert.