Level 9 – Musterlösung: Der Güterzug (Verkettete Liste)

Lösung

public class Waggon
{
    private Paket ladung;
    private Waggon naechster;
 
    public Waggon(Paket p)
    {
        this.ladung = p;
    }
 
    public Waggon GetNaechster()
    {
        return naechster;
    }
 
    public void SetNaechster(Waggon w)
    {
        naechster = w;
    }
}
 
public class Gueterzug
{
    private Waggon lokomotive;
 
    public void Anhaengen(Paket p)
    {
        if (lokomotive == null)
        {
            lokomotive = new Waggon(p);
            return;
        }
 
        Waggon letzter = lokomotive;
        while (letzter.GetNaechster() != null)
        {
            letzter = letzter.GetNaechster();
        }
 
        letzter.SetNaechster(new Waggon(p));
    }
}

---

Erklärung

Was ist eine verkettete Liste?

Eine verkettete Liste ist eine Datenstruktur, bei der jedes Element auf sein nächstes Element zeigt – ähnlich wie Waggons an einem Zug. Es gibt keinen direkten Indexzugriff wie bei List<T> (pakete[2]). Stattdessen muss man immer vom Anfang aus durch die Kette laufen, bis man ans Ziel gelangt.

Der erste Waggon heißt lokomotive und ist der einzige Einstiegspunkt in den gesamten Zug. Verliert man die Referenz auf die Lokomotive, ist der gesamte Zug verloren.

Die Klasse Waggon

private Paket ladung;
private Waggon naechster;

Jeder Waggon hat zwei Attribute: seine ladung (ein Paket) und eine Referenz auf den naechster-Waggon. Wenn naechster den Wert null hat, gibt es keinen weiteren Waggon – das ist dann das Ende des Zuges.

Wichtig: naechster wird im Konstruktor nicht gesetzt. Das ist korrekt so – ein neu erstellter Waggon hat zunächst keinen Nachfolger. C# initialisiert Referenztypen automatisch mit null.

Fall 1: Der Zug ist leer

if (lokomotive == null)
{
    lokomotive = new Waggon(p);
    return;
}

Gibt es noch gar keinen Waggon, wird das neue Paket direkt zur Lokomotive. Das return ist dabei zwingend nötig: Ohne es würde der Code danach weiterlaufen und versuchen, mit lokomotive zu navigieren — was gerade erst erstellt wurde und noch keinen Nachfolger hat, was zu einem Fehler führt.

Fall 2: Den letzten Waggon finden

Waggon letzter = lokomotive;
while (letzter.GetNaechster() != null)
{
    letzter = letzter.GetNaechster();
}

Existieren bereits Waggons, muss man zum Ende des Zuges durchlaufen. letzter startet bei der Lokomotive und wandert mit jedem Schleifendurchlauf einen Waggon weiter nach hinten. Sobald GetNaechster() null zurückgibt, ist letzter der letzte Waggon im Zug.

Hier eine wichtige Unterscheidung: Die Schleife prüft letzter.GetNaechster() != null – also ob der Nachfolger null ist, nicht letzter selbst. Würde man auf letzter != null prüfen, würde man einen Schritt zu weit laufen und am Ende mit null arbeiten.

Den neuen Waggon ankuppeln

letzter.SetNaechster(new Waggon(p));

Am Ende der Kette angekommen, wird ein neuer Waggon erstellt und als Nachfolger des letzten gesetzt. Die Kette ist damit um ein Element verlängert.

Visualisierung

Ein Zug mit drei Paketen sieht intern so aus:

lokomotive
    │
[Waggon A] ──naechster──▶ [Waggon B] ──naechster──▶ [Waggon C] ──naechster──▶ null

Anhaengen läuft von A nach B nach C, stellt fest dass C keinen Nachfolger hat, und hängt D an:

[Waggon C] ──naechster──▶ [Waggon D] ──naechster──▶ null