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.

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 Elements 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 diesen Zustand?

Enqueue-Algorithmus

Wir beginnen mit einer leeren Queue. Sowohl head- aus 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;
    }
  }
}

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

Ausblick

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