C-Programmierung

Knoten aus Liste Löschen

← Knoten in Liste Suchen | ● | Doppelt Verkettete Listen →

Einzelne Arbeitsschritte:

  • Falls der zu löschende Knoten die Wurzel ist:
    • Wurzel auf Nachfolger-Knoten des zu löschenden Knotens setzen
  • Sonst:
    • Nachfolger-Zeiger des Vorgänger-Knotens auf den Nachfolger-Zeiger des zu löschenden Knotens setzen
  • Speicher von zu löschendem Knoten freigeben 
         -----     -----     -----     -----
root --> |d|n| --> |d|n| --> |d|n| --> |d|n| --> null
         -----     -----     -----     -----

Fall 1: 

      free
         |
         -----     -----     -----     -----
root     |d|n|     |d|n| --> |d|n| --> |d|n| --> null
   |     -----     -----     -----     -----
   |               ^
   \_______________/

Fall 2: 

                free
                   |
         -----     -----     -----     -----
root --> |d|n|     |d|n|     |d|n| --> |d|n| --> null
         -----     -----     -----     -----
            |                ^
            \________________/

Problem: Wie ermittelt man den Vorgängerknoten? Es gibt keinen direkten Weg zurück, nur den verketteten Weg von der Wurzel.

Nachteil: Suche nach Vorgänger-Element kostet Zeit.
Lösung: Doppelt verkettete Listen.

← Knoten in Liste Suchen | ● | Doppelt Verkettete Listen →

Options: