verkettete Liste

Eine verkettete Liste ist eine lineare Datenstruktur, bei der man auf jedes Element zugreifen kann. Man implementiert das in C am besten als eine Struct mit Zeigern auf Structs des gleichen Typs.

Es ist auch eine gute Idee einen zweite Struktur zu definieren, die etwas Verwaltungsblabla enthält, damit wird auch das Übergeben an die Funktionen einfacher.

Am besten legt man dann eine solche Struktur des Haupttyps als lokale Variable oben im Programm an, und reicht immer Zeiger darauf runter. Dabei muß man sich keine Gedanken um Memory-Leaks machen.

Man kann solche Listen mit einfacher oder doppelter Verkettung anlegen, je nach Verwendugnszweck. Bei doppelten Listen ist es einfacher mittendrin was zu löschen, wenn man nur einen Zeiger auf ein Element hat, während man bei einfachen Verkettungen dann von Anfang an loslaufen muß, da man den Vorgänger kennen muß um seinen neuen Nachfolger zu verlinken.

Sinnvolle Operationen sind insert, delete, retrieve, count und zur Verwaltung noch init und free. Hier eine kurze Skizzierung der Befehle einer ad-hoc-Implementierung (man kann es noch nahezu beliebig viel komfortabler gestalten).

struct list_item {
    const void *payload;
    struct list_item *last, *next;
};

struct list {
    unsigned count;
    struct list_item *data;
};

void init_list(struct list *l)
{
    l->data = NULL;
    l->count = 0;
}

void free_list(struct list *l)
{
    /* Liste durchlaufen, einzelne Einträge löschen.
     * An Memory-Leaks denken. Aufpassen daß keine Einträge
     * gekillt werden, auf die man noch zugreifen muß (weil sie
     * den Zeiger auf den Nachfolger haben, etc.)
     */
}

/* diese Funktion dient nur dem Blackboxing und der Kapselung,
 * natürlich könnte man l->count direkt abfragen, aber
 * so ist es aus der Sicht des Designs robuster, weil keiner an den
 * Innereien der Liste rumpfuscht, wenn er die Implementierungsdetails
 * nicht kennt.
 */
unsigned count_list(struct list *l)
{
    return l->count;
}

int insert_list(struct list *l, struct list_item *i, unsigned pos)
{
    /* i an der Stelle pos einhängen */    
}

/* Es ist möglicherweise sinnvoll sowas wie append und prepend zu
 * schreiben, das dann insert_list mit pos = 0 bzw. pos = count aufruft,
 * da dies häufige Operationen sind und Schreibarbeit sparen. Vielleicht
 * sogar nicht als Wrapper auf insert_list, sondern direkt implementieren,
 * falls Performance wichtig ist. Tipp: ans Ende kommt man schnell mit
 * Kopf -> last :-)
 */

int delete_list(struct list *l, unsigned pos)
{
    /* Ding an der Stelle pos rauswerfen */
}

struct list_item *retrieve_list(struct list *l, unsigned pos)
{
    /* Zeiger auf das Ding an der Stelle pos zurückgeben */
}
    

Statt dem void-Zeiger kann man natürlich, wenn der Zweck der Liste bekannt ist und es etwas unflexibel sein darf, durch konkrete Datenfelder ersetzt werden. Die Einfüge- und Entfernungsoperation sollte signalisieren, ob's geklappt hat. Die Init-Funktion kann nicht großartig fehlschlagen, die Free-Funktion sollte auch nicht fehlschlagen können, und wenn, dann kann der Benutzer vermutlich eh nicht sinnvoll drauf reagieren.