C-Programmierung: Verkettete Listen

Beim Programmieren in C kommt man immer wieder zu Punkten, an denen man feststellt, dass man mit einem Array nicht auskommt. Diese treten zum Beispiel dann ein, wenn man eine unbekannte Anzahl von Elementen verwalten muss. Mit den Mitteln, die wir jetzt kennen, könnte man beispielsweise für eine Anzahl an Elementen Speicher dynamisch anfordern und wenn dieser aufgebraucht ist, einen neuen größeren Speicher anfordern, den alten Inhalt in den neuen Speicher schreiben und dann den alten wieder löschen. Klingt beim ersten Hinsehen ziemlich ineffizient, Speicher allokieren, füllen, neu allokieren, kopieren und freigeben. Also lassen Sie uns überlegen, wie wir das Verfahren optimieren können.

1. Überlegung:

Wir fordern vom System immer nur Platz für ein Element an. Vorteil: Jedes Element hat einen eigenen Speicher und wir können jetzt für neue Elemente einfach einen malloc ausführen. Weiterhin sparen wir uns das Kopieren, da jedes Element von unserem Programm eigenständig behandelt wird. Nachteil: Wir haben viele Zeiger, die jeweils auf ein Element zeigen und wir können immer noch nicht beliebig viele Elemente verwalten.

2. Überlegung:

Jedes Element ist ein komplexer Datentyp, welcher einen Zeiger enthält, der auf ein Element gleichen Typs zeigen kann. Vorteil: wir können jedes Element einzeln allokieren und so die Vorteile der ersten Überlegung nutzen, weiterhin können wir nun in jedem Element den Zeiger auf das nächste Element zeigen lassen, und brauchen in unserem Programm nur einen Zeiger auf das erste Element. Somit ist es möglich, beliebig viele Elemente zur Laufzeit zu verwalten. Nachteil: Wir können nicht einfach ein Element aus der Kette löschen, da sonst kein Zeiger mehr auf die nachfolgenden existiert.

Die einfach verkettete Liste

Die Liste ist das Resultat der beiden Überlegungen, die wir angestellt haben.
Eine einfache Art, eine verkettete Liste zu erzeugen, sieht man im folgenden Beispielquelltext:

Online-Compiler ideone:

#include <stdio.h>
#include <stdlib.h>

struct element
{
    int value;            /* der Wert des Elements          */
    struct element *next; /* Zeiger auf das nächste Element */
};


void printliste(const struct element *e)
{
    for( ; e != NULL ; e = e->next )
    {
        printf("%d\n", e->value);
    }
}


void append(struct element **lst, int value)
{
    struct element *neuesElement;
    
    /* Zeiger auf die Einfügeposition ermitteln, d.h. bis zum Ende laufen */
    while( *lst != NULL ) 
    {
        lst = &(*lst)->next;
    }

    neuesElement = malloc(sizeof(*neuesElement)); /* erzeuge ein neues Element */
    neuesElement->value = value;
    neuesElement->next = NULL; /* Wichtig für das Erkennen des Listenendes     */

    *lst = neuesElement;
}

int main()
{
    struct element *Liste;

    Liste = NULL;      /* init. die Liste mit NULL = leere Liste */
    append(&Liste, 1); /* füge neues Element in die Liste ein    */
    append(&Liste, 3); /* füge neues Element in die Liste ein    */
    append(&Liste, 2); /* füge neues Element in die Liste ein    */

    printliste(Liste); /* zeige alle Elemente der Liste an */

    return 0;
}