01. Verkettete Liste

Problem

Wir benötigen eine Datenstruktur mit Daten- und Adressbereich!

Datenstruktur für die verkettete Liste

// Dies ist "class" anstatt "struct", da dies C# und nicht wie letztes Schuljar C++ ist.
class CPupil
{
    // Datenbereich
    public int iNr;
    public string strName;
    public string strLocation;
    public string strPhone;

    // Addressbereich
    public CPupil Next = null; // Zeigt auf den nächsten Datensatz
}

Voraussetzungen für eine verkette Liste

• Jede verkettete Liste benötigt einen definierten Anfang! $\rightarrow$ Bereitstellung eines Listen-Ankers: CPupil Anchor = null;
• Speicher für ein neues Element allokieren

  CPupil Alloc;
  Alloc = new CPupil();
  

• Freigeben des Speichers eines Elementes

  // einer Referenzvariablen null zuweisen, GC!
  Alloc = null;
  

Grundoperationen mit verketteten Listen

• Neues Element am Ende anfügen
• Element löschen
• Gesamte Liste löschen
• Element in der Liste suchen
• Liste nach einem bestimmten Kriterium sortieren
• usw.

Operation: Element am Ende anfügen

• Unterscheidung zweier Fälle notwendig:
  • Die Liste ist leer $\rightarrow$ der Anker zeigt auf null
  • Die Liste enthält bereits Elemente $\rightarrow$ der Anker zeigt auf das erste Element

Struktogramm:

Operation: Element der Liste löschen

• Unterscheidung zweier Fälle notwendig:
  • Das erste Element der Liste soll gelöscht werden $\rightarrow$ der Anker ändert sich
  • Irgendein Element der Liste soll gelöscht werden $\rightarrow$ der Anker behält seinen Wert

Struktogramm: