Stack mit einer Linked List implementieren

Im vorangeganenen Teil haben wir einen Stack mit einem Array implementiert. In diesem Teil zeige ich dir, wie du einen Stack mit einer einfach verketteten Liste programmierst.

Der Algorithmus – Schritt für Schritt

Dies ist im Grunde ganz einfach: Eine top-Referenz zeigt auf einen Knoten, der das oberste Element des Stacks enthält sowie einen next-Zeiger auf den zweiten Knoten. Dieser wiederum enthält das zweite Element und einen Zeiger auf den dritten Knoten, usw. Der letzte Knoten enthält das unterste Element des Stacks; die next-Referenz des letzten Knotens ist null.

Die folgende Grafik zeigt einen Beispiel-Stack, auf den die Elemente "apple", "orange" und "pear" (in dieser Reihenfolge) gepusht wurden:

Doch wie kommen wir dorthin?

Enqueue-Algorithmus

Beginnen wir mit einem leeren Stack. Die top-Referenz ist zunächst null:

Um das erste Element auf den Stack zu pushen, wrappen wir dieses in einen neuen Knoten und lassen top auf diesen Knoten zeigen:

Jedes weitere Element fügen wir zwischen top und den ersten Knoten ein. Dazu brauchen wir drei Schritte:

1. Wir legen einen neuen Knoten an und wrappen damit das einzufügende Element.
2. Wir lassen die next-Referenz des neuen Knotens auf denselben Knoten zeigen wie top.
3. Wir lassen top auf den neuen Knoten zeigen.

Die folgende Grafik zeigt die drei Einfüge-Schritte:

Dequeue-Algorithmus

Um ein Element mit pop() wieder zu entnehmen, gehen wir wie folgt vor:

1. Wir merken uns das Element des Knotens, auf das top zeigt (im Beispiel "orange").
2. Wir ändern die top-Referenz auf denjenigen Knoten auf den top.next zeigt.
3. Wir geben das in Schritt 1 gemerkte Element zurück.
4. In einer Sprache mit Garbage Collector (z. B. Java) sorgt dieser dann für das Löschen des nicht mehr referenzierten Knotens. In Sprachen ohne Garbage Collector (z. B. C++) müssen wir das selbst tun.

Die folgende Grafik zeigt die vier Schritte:

Der gestrichelte Rahmen um den "orange"-Knoten im zweiten und dritten Schritt soll andeuten, dass dieser Listenknoten nicht mehr referenziert wird.

Quellcode für den Stack mit einer Linked List

Der folgende Quellcode zeigt die Implementierung des Stacks mit einer verketteten Liste (Klasse LinkedListStack im GitHub-Repo). Die Klasse für die Knoten, Node, findest du am Ende des Quellcodes als statische innere Klasse.

public class LinkedListStack<E> implements Stack<E> {

  private Node<E> top = null;

  @Override
  public void push(E element) {
    top = new Node<>(element, top);
  }

  @Override
  public E pop() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    E element = top.element;
    top = top.next;
    return element;
  }

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


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

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

    Node(E element, Node<E> next) {
      this.element = element;
      this.next = next;
    }
  }
}Code-Sprache: Java (java)

Wie die LinkedListStack-Klasse eingesetzt wird, kannst du dir beispielhaft im Demo-Programm StackDemo ansehen.

Vor- und Nachteile der Implementierung des Stacks mit einer Linked List

Die Implementierung mit einer verketteten Liste hat gegenüber der Array-Variante den Vorteil, dass sie keinen Speicherplatz durch unbelegte Array-Felder verschwendet und dass sie keine Größenänderung des Arrays durch Kopieren des gesamten Arrays erfordert.

Die Knoten-Objekte wiederum belegen mehr Speicherplatz als ein einzelnes Feld in einem Array. Das Anlegen von Knoten-Objekten kostet mehr Zeit als das Setzen eines Array-Feldes. Eine verkettete Liste verursacht außerdem mehr Arbeit für den Garbage Collector, da dieser bei jedem Durchgang der kompletten Kette folgen muss.

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

Ausblick

Im nächsten Teil des Tutorials zeige ich dir, wie man einen Stack mit einer Queue implementieren kann.

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.