Einfach verkettete Listen in C

Einfach verkettete Listen oder linked lists sind eine fundamentale Datenstruktur, die ich hier anhand von Code-Beispielen und Grafiken erklären will.

Einfach verkettete Listen zeichnen sich dadurch aus, dass man besonders einfach Elemente einfügen kann, wodurch sie sich besonders gut für Insertion Sort eignen. Eine Verallgemeinerung stellen die doppelt verketteten Listen da.

Knoten

Eine einfach verkettete Liste besteht aus Knoten, Englisch nodes, die einen Zeiger auf das nächste Element und auf Daten.

struct list_node {
	int data;
	struct list_node *next;
};

Um nicht jedes mal das struct mitschleppen zu müssen, kann man eine Abkürzung definieren:

typedef struct list_node* node;

Eine leere Liste besteht aus einem Kopf (Head) und nichts sonst:

Eine leere Liste beseht aus einem Kopf und einem NULL-Zeiger
Eine leere Liste

Wenn man mehrere Elemente einfügt, sieht das so aus:

Eine etwas befülltere Liste
Eine einfach verkettete Liste mit einem Kopf und zwei Knoten.

Elemente Einfügen

Wenn man einen Zeiger auf ein Element der Liste hat, ist es einfach, ein Element dahinter einzufügen.

Dazu muss man den next-Zeiger der Liste auf das neue Element setzen, und den next-Zeiger des neuen Element auf den alten Wert des next-Zeigers der Liste:

node insert_right(node list, int data){
	node new_node = (node) malloc(sizeof(struct list_node));
	new_node->data = data;
	new_node->next = list->next;
	list->next     = new_node;
	return new_node;
}
Eine liste mit zwei Elementen, in die ein neues Element eingefügt werden soll
In diese List soll links neben node1 ein Element mit dem Datum 3eingefügt werden.
Eine liste mit zwei Elementen, in die ein neues Element eingefügt ist
Durch das Setzen eines Zeigers wird das neue Element in die Liste eingegliedert.
Die gleiche Liste in etwas schönerer Darstellung

Elemente löschen

Auch das Löschen eines Elements ist einfach, wenn man einen Zeiger auf das Element links des zu löschenden Elements hat.

Dazu muss man nur den next-Zeiger des linken Elements auf das Element rechts des zu löschenden setzen:

node delete_right(node list){
	node tmp   = list->next;
	list->next = list->next->next;
	free(tmp);
	return list;
}

In diesem Fall wurde noch ein temporärer Zeiger benutzt, um den Speicher des genutzten Elements freizugeben.

Eine Liste mit einem Kopf und zwei Elementen
Aus dieser Liste soll das erste Element gelöscht werden.
Der next-Zeiger des Kopfes wird auf das zweite Element gesetzt
Und schon ist es gelöscht.

Insertion Sort mit verketteten Listen

Eine schöne Anwendung für einfach verkettete Listen ist der Sortieralgorithmus "Insertion Sort", oder auf Deutsch "Sortieren durch einfügen".

Für große Datenmengen eignet sich Insertion Sort nicht, weil die Laufzeit quadratisch mit der Anzahl der Elemente wächst, aber für kleine Datenmengen (vielleicht bis 20 Elemente) es schneller als die "schnellen" Algorithmen wie Mergesort oder Quicksort.

Es ist auch ganz einfach: man startet mit einer leeren Liste, und wenn man Elemente einfügt, achtet man darauf, sie an der richtigen Stelle einzufügen:

node insertion_sort(int *a, int count){
	node list = new_list();
	node c;
	int i;

	for (i = 0; i < count; i++){
		c = list;
		while(c->next != NULL &&; c->next->data < a[i]){
			c = c->next;
		}
		insert_right(c, a[i]);

	}
	return list;
}

In Worten: mache für jedes Element des zu sortierenden Arrays das folgende:

Gehe solange vom Kopf der Liste nach rechts, bis das Ende erreicht ist oder das nächste Element größer als das einzufügende ist, und füge dann das Element davor ein.

Suche

Um ein Element in der Liste zu suchen, hangelt man sich von einem Listenelement zum nächsten, entweder bis man die gesuchte Element gefunden hat, oder bis man NULL erreicht:

node search_for(node list, int data) {
    while (list != NULL) {
        if (list->data == data)
            return list;
        list = list->next;
    }
    return NULL;
}

Wenn man erst mal den node pointer hat, kann man z.B. rechts davon einfügen oder löschen.

Zusammenfassung

Eine einfach verkettete Liste speichert pro Element einen Zeiger auf das nächste Element und die Nutzdaten. Das Durchlaufen von Rechts nach Links, das Einfügen und das Entfernen des Elements rechts des aktuellen Elements sind einfach und erfordern nur das umsetzen von zwei Zeigern.

Gegenüber doppelt verketteten Listen brauchen sie also weniger Verwaltungsaufwand, bei etwas geringerer Flexibilität.

Weiteres Lesematerial

Bücher

"Algorithmen in C" von Robert Sedgewik ist allgemeinverständlich und praktisch. "The Art of Computer Programming" von Donald Knuth ist ein Klassiker, und beschreibt für den mathematisch interessierten Leser Algorithmen, Datenstrukturen und ihre Vor- und Nachteile im Detail (Englisch).