C-Programmierung

Verkettete Listen

Zusatzaufgabe #3 | | Einfach Verkettete Liste

Um eine veränderliche Menge an Daten zu speichern, bedient man sich typischerweise eines dynamischen Arrays (Stichwort malloc()).

Das Anfügen von weiteren Daten geschieht mittels der Vergrößerung des Speicherbereichs (Stichwort realloc()), z.B. Verdoppelung des vorgehaltenen Speichers.

  • Der Vorteil ist ist der wahlfreie Zugriff auf einzelne Elemente (random access).
  • Der Nachteil ist die Unflexibilität eines Arrays bei der Entfernung von einzelnen Elementen.

Hier hat man drei Wahlmöglichkeiten:

  • Element als gelöscht markieren
    • Nachteil: Speicherverbrauch
  • AuffĂĽllen des gelöschten Element mit dem letzten Element
    • Nachteil: Ordnung der Elemente geht verloren
  • Verschieben der nachfolgenden Elemente um eine Stelle nach links
    • Nachteil: Kopieren des ganzen rechtsseitigen Speicherbereichs

Lösung: verkettete Datenstrukturen, d.h. Strukturen deren Elemente einen Zeiger auf weitere dynamisch erzeugte Elemente enthalten.

Ein Beispiel dafĂĽr ist die einfach verkettete Liste.

Zusatzaufgabe #3 | | Einfach Verkettete Liste

Options: