3.2. Verkettete Listen

Es gibt zwei gebräuchliche Datenstrukturen, mit denen man den ADT Liste implementieren kann:

1. Verkettete Liste

2. Array (hierbei muss berücksichtigt werden, dass die Größe des Arrays begrenzt ist und evtl. intern zwischendurch neue Arrays erstellt werden müssen, wenn die Größe überschritten wird)

Wir beschäftigen uns hier nur mit der Implemetierung als Verkettete Liste, weil wir dadurch die Grundlagen von rekursiven Datenstrukturen kennenlernen, die wir später auch bei Bäumen benötigen.

3.2.1. Wie sehen verkettete Listen aus?

Abb. 3.2 Verkettete Liste oder Polonaise?

Eine verkettete Liste besteht aus Knoten. Jeder Knoten enthält einen Inhalt (z.B. eine Zahl oder einen String) und eine Referenz auf den nächsten Knoten.

Beispiel: Liste = [“Dina”, “Coco”, “Bibi”, “Anna”]

Die Liste besteht aus 4 Knoten:

• Knoten1: Inhalt=“Dina”, naechster=Knoten2

• Knoten2: Inhalt=“Coco”, naechster=Knoten3

• Knoten3: Inhalt=“Bibi”, naechster=Knoten4

• Knoten4: Inhalt=“Anna”, naechster=None

Die Referenz naechster des letzten Knotens ist None, da es keinen weiteren Knoten gibt.

3.2.2. Übung: Einen neuen Knoten in eine Liste einfügen

Zwischen Coco und Bibi soll ein weiterer Knoten eingefügt werden, z.B. Horst. Dazu muss folgendes passieren:

Das klingt einfach… aber der 😈 steckt im Detail, wie du unten gleich sehen wirst!

1. Ein neuer Knoten, der als Inhalt den String “Horst” enthält wird angelegt.

2. Der Nachfolger von Coco wird auf Horst gesetzt.

3. Der Nachfolger von Horst wird auf Bibi gesetzt.

Aufgabe: Zeichne Abb. 3.2 ab. Ändere deine Zeichnung dann Schritt für Schritt anhand der oben genannten Schritte ab. Überlege dabei genau, welche Reihenfolge dabei sinnvoll ist.

3.2.3. Verkettete Listen in UML

Klassendiagramm

Das Klassendiagramm Abb. 3.3 zeigt, wie man die verkettete Liste in UML modelliert. Du siehst, dass zwei Klassen verwendet werden, VerketteteListe und Knoten. Die Klasse VerketteteListe speichert eine Referenz auf den ersten Knoten (den Listenkopf) und enthält all die Methoden aus dem ADT Liste, wie Hinzufügen, Entfernen und Suchen von Elementen.

Die Angabe <Typ> bezeichnet einen generischen Datentyp. Das bedeutet: Jede Liste speichert Daten eines konkreten Datentyps, z.B. GZ, Text oder Mitarbeiter. Überall wo im Diagramm <Typ> steht, wird das durch diese konkrete Klasse ersetzt. Eine VerketteteListe<Text> speichert also Text-Objekte und verwaltet diese mithilfe von Knoten<Text>-Objekten, usw.

Abb. 3.3 Klassendiagramm für die Datenstruktur Verkettete Liste (FoSa 5.1)

Die eigentliche Arbeit der Datenstruktur erfolgt in der Klasse Knoten, die ein einzelnes Listenelement darstellt. Jeder Knoten enthält sowohl einen Inhalt als auch eine Referenz auf den nächsten Knoten. Es handelt sich hier also um eine Assoziation der Klasse Knoten mit sich selbst (von Knoten zu Knoten). Man spricht hierbei von einer reflexiven Assoziation.

Beispiel: In einer betriebswirtschaftlichen Software wird die Klasse Mitarbeiter verwendet. Jedes Mitarbeiter-Objekt speichert die Daten eines Angestellten. Um z.B. alle Mitarbeiter einer Abteilung zu verwalten, benötigt man eine Liste von Mitarbeiter-Objekten. Das konkrete Klassendiagramm sieht dann so aus:

Abb. 3.4 Klassendiagramm: Verkettete Liste von Mitarbeitern

Objektdiagramm

Wichtig

Achtung: Dass die Klasse Knoten eine Assoziation mit sich selbst hat, bedeutet nicht, dass auch die einzelnen Objekte mit sich selbst assoziiert sind. Stattdessen ergibt sich im Objektdiagramm eine Kette von Objekten.

Beispiel: Frau Maier, Herr Müller und Herr Schmidt arbeiten in der (streng geheimen) Abteilung 42. Alle Mitarbeiter der Abteilung sind in einer (ebenfalls streng geheimen) Liste gespeichert. Es ergibt sich folgendes Objektdiagramm:

Abb. 3.5 Objektdiagramm: Liste von Mitarbeitern der geheimnisvollen Abteilung 42

3.3. Verkettete Listen in Python programmieren

Wir entwickeln zuerst die Klasse Knoten und eine aufs Wesentliche reduzierte Klasse VerketteteListe. In den späteren Übungen erweitern wir VerketteteListe um immer mehr Methoden.

Achtung: Der untenstehende Code führt zu einer Endlosschleife, denn er enthält einen (fiesen) Fehler in der Methode einfuegen_vorne. Findest du ihn?

from __future__ import annotations

class Knoten:
    def __init__(self, inhalt):
        """ Konstruktor für die Klasse Knoten: speichert den Inhalt und legt
        eine Referenz auf den nächsten Knoten an. """
        self.inhalt = inhalt   # keine Typ-Angabe: inhalt kann beliebig sein
        self.naechster: Knoten|None = None    # Typ-Annotation: naechster ist ein Knoten oder None

    def __str__(self) -> str:
        return str(self.inhalt)
    
    
class VerketteteListe:
    def __init__(self):
        self.erster: Knoten|None = None   # Der erste Knoten in der Liste (Listenkopf)    

    def __str__(self) -> str:
        """ Gibt die Liste als Zeichenkette, getrennt durch Pfeile, zurück. """
        inhalte = []
        knoten = self.erster
        while knoten is not None:
            inhalte.append(knoten.inhalt)
            knoten = knoten.naechster
        return " -> ".join(inhalte)

    def einfuegen_vorne(self, pInhalt) -> None:
        """Fügt einen neuen Knoten mit pInhalt am Anfang der Liste ein."""
        neu = Knoten(pInhalt)   # "Verpacke" den Inhalt in einen Knoten
        self.erster = neu  # Der neue Knoten ist ab jetzt der Listenkopf
        neu.naechster = self.erster  # Nachfolger des neuen Knotens ist der bisherige Listenkopf


print("Achtung: Dieser Code enthält einen Fehler in der Methode einfuegen_vorne. Findest du ihn?")
liste_bsp1 = VerketteteListe()
liste_bsp1.einfuegen_vorne("Anna")
liste_bsp1.einfuegen_vorne("Bibi")
liste_bsp1.einfuegen_vorne("Coco")
liste_bsp1.einfuegen_vorne("Dina")
print(liste_bsp1)

Die korrekte Lösung erhältst du, wenn du dieses Parsons-Problem löst:

Wenn du verstanden hast, warum die Lösung so - und nur so! - funktioniert, bist du bereit, die weiteren Operationen von Listen zu implementieren!