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.