Verwandte Themen

Einfach verkettete Listen in C

Nach den doppelt verketteten Listen werden hier einfach verkettete Listen vorgestellt.

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 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;
};

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.
top

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
top

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.
top

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.

top

Verwandte Themen