Listen sind zunächst abstrakte Konstrukte. Die Implementation in C sieht meistens irgendwie so aus:
Listen sind zunächst abstrakte Konstrukte. Die Implementation in C sieht meistens irgendwie so aus:
Also: Ein Listenelement (node) sieht so aus:
typedef struct Node_s {
struct Node_s *next;
char *cont;
} Node;
Die Verwendung von struct Node_s * in der Definition von Node ist wegen der rekursiven Definition notwendig: Das typedef hat der Compiler noch nicht verdaut, wenn wir den Zeiger auf das nächste Listenelement deklarieren wollen.
Für die ganze Liste brauchen wir:
typedef struct List_s {
Node *first; /* Erstes Element */
Node *last; /* Letztes Element */
} List;
Die Definition von List kommt in den Header (Clients sollen den Inhalt aber nicht kennen – List ist opak). Dass wir die Liste mit Nodes implementieren (und nicht z.B. ein Array dazu nehmen), soll der Benutzer nicht wissen. Leider muss die Definition des Typen Node trotzdem in den Header, weil sie zur Definition von List nötig ist.
Weiterführend: Tatsächlich könnten wir darauf bestehen, im Headerfile nichts über den Inhalt von Node zu verraten. C würde die Deklaration
struct Node;
typedef struct List_s {
struct Node *first; /* Erstes Element */
struct Node *last; /* Letztes Element */
} List;
friedlich über sich ergehen lassen und euch erlauben, dass ihr struct Node erst dort erklärt, wo ihr wirklich auf seine Elemente zugreifen wollt (hier also nicht im Header, sondern im C-Quellcode des Listenmoduls). Sowas ist ein Beispiel für forward declarations, Deklarationen, in denen man nur verspricht, später mehr zu verraten.
Wir wollen hier der Einfachheit halber darauf verzeichten.
Neue Liste erzeugen:
List *list_new(void)
{
List *l = malloc(sizeof(List));
if (l) {
l->first = NULL;
l->last = NULL;
}
return l;
}
Wenn kein Platz ist, wird NULL zurückgegeben.
Die Logik hier ist, dass malloc bereits NULL zurückgibt, wenn der Speicher nicht alloziert werden kann. Bedingt auf den Erfolg von malloc wird dann die Liste initialisiert.
Weil die Funktion kurz ist, ist das hier guter Stil. Ist der Funktionskörper länger, ist es empfehlenswert, bereits beim Auftreten des Fehlers aufzugeben (aber Vorsicht mit memory leaks!):
if (!(l = malloc(sizeof(Liste))) {
return NULL;
}
Diese Funktion ist gewissermaßen der Konstruktor unserer List-“Klasse”.