Einfach verkettete Liste

Aus TriagonyWiki

Eine einfach verkettete Liste, ist die einfachste Form einer Liste.

Definition

Eine einfach verkettete Liste besteht aus einem Kopf und genau einem Rest. Der Kopf besteht wiederum aus einem Kopf und einem Rest. Mittels einer Grafik und der Liste wurde das ja schon beschrieben. Welche Funktionen eine Liste bieten soll und wie sie sich intern organisiert kann man selber bestimmen. Jedoch sollten einige Funktionsweisen gegeben sein. Beispielsweise sollte man Elemente hinzufügen und löschen können. Auch sollten diese wieder ausgegeben werden können.

Beispiel

Ich habe mir die Aufgabe gesetzt eine Liste in C zu implementieren. In anderen Sprachen funktioniert dies ähnlich. In vielen Sprachen sind Listen auch schon vorhanden. Jedoch möchte ich mal unter die Haube schauen und mir selber eine Liste in C implementieren.

Knoten

Zuerst benötigen wir einen Koten einer Liste. Dieser Knoten besteht aus einem Element und einem Zeiger auf ein nachfolgendes Element. Von einem Array ist es bekannt, dass man durch einen Index auf einzelne Elemente des Arrays zugreifen kann. Dieser Zugriff ist direkt. Bei einer Liste ist dies ohne weiteres nicht möglich. Es muss immer durch die gesamte Liste gegangen werden, um einzelne Elemente auszugeben. Dies ist der Grund, warum wir den Index nicht mit Speichern müssen. Es muss immer wieder bei 0 angefangen werden und damit kann man den Abstand zum ersten Element abzählen.

/**
 * Einzelner Knoten der Liste
 */
typedef struct KListNode {
	void *element;
	struct KListNode *next;
} KListNode;

Dies steht in der Header Datei des C - Programmes. Dabei wird ein einzelner Knoten einer Liste repräsentiert. Es besitzt einen Zeiger auf ein Element und einen Zeiger auf den nächsten Knoten. Es wird ein void - Zeiger auf ein nächstes Element verwendet, damit in dem Knoten alle Datentypen gespeichert werden können. Dies ist nicht für alle Anforderungen nötig. Darum muss das Element kein Zeiger sein, sondern kann ebenfalls ein Typ sein. Der Speicherverbrauch eines leeren Knoten ist nun 8 Byte.

Kopf

Damit auch Zustandsinformationen gespeichert werden können, benötigen wir einen Kopf. In diesem wird die Größe des zu speichernden Elementes vermerkt, sowie die Anzahl der enthaltenden Elemente und und und. Ebenfalls können über Funktionszeiger Benutzer Funktionen gespeichert werden, welche nachher zum vergleichen von Elementen oder zum löschen wichtig sein können.

/**
 * Der Listenkopf
 */
typedef struct KList {
	size_t type;
	int count;
	int capacity;
	int resizeable;
	void (*destroyElementUserFunction)( void *p );
	int (*compareUserFunction)( const void *s1, const void *s2, size_t n );
	KListNode *first;
} KList;

Damit dieser als Listenkopf agieren kann, braucht dieser ein Verweis auf das erste Element der Liste. Die "destroyElementUserFunction" ist zum löschen von Elementen gedacht. Wenn in dieser Liste eine Struktur mit einem Zeiger auf eine andere Struktur gespeichert wird, dann würde es zu Speicherlags kommen. Denn die Liste weiß nicht, was für Elemente gespeichert werden. Wenn sie mit "free" den Speicher des Elementes frei räumen möchte, wird ebenfalls der Zeiger gelöcht, welcher in der gespeicherten Struktur angegeben wurde. Damit ist noch Speicher reserviert, jedoch die Referenz entfernt worden. durch den Funktionszeiger "destroyElementUserFunction" ist der Anwender selber für das frei räumen des Elementes verantwortlich.

Liste initialisieren

Um die Liste nutzen zu können, muss diese erst initialisiert werden. Dazu muss der Kopf gesetzt werden.

/**
 * listInit initialisiert eine Liste mit den Standardwerten
 * Es wird ein Zeiger auf die Liste zurück gegeben
 */
KList *klist_initList( size_t const type, int const resizeable,
		void(*destroyElementUserFunction)( void *p ),
		int(*compareUserFunction)( const void *s1, const void *s2, size_t n ) ) {
 
	//Alloziert Speicher für eine neue Liste
	KList *newList = ( KList * ) malloc( sizeof(KList) );
 
	if( NULL != newList ) {
		//Standardwerte werden gesetzt
		newList->capacity = 0;
		newList->count = 0;
		newList->type = type;
		newList->resizeable = resizeable;
		newList->first = NULL;
 
		if( NULL == destroyElementUserFunction )
			newList->destroyElementUserFunction = free;
		else
			newList->destroyElementUserFunction = destroyElementUserFunction;
 
		if( NULL == compareUserFunction )
			newList->compareUserFunction = memcmp;
		else
			newList->compareUserFunction = compareUserFunction;
	}
 
	return newList;
 
}

Wie schon gesagt. Es werden einfach nur Standardwerte gesetzt und natürlich auch die Eingaben des Anwenders beachtet. Es wird Speicher für den Listenkopf Alloziert und die Funktionszeiger werden gesetzt. Sollten diese NULL sein, wird auf die free Funktion zum freiräumen und auf die memcpy Funktion zum vergleichen zurück gegriffen. Danach wird ein Zeiger auf den Listenkopf zurück gegeben.

Knoten initialisieren

Die Initialisierung eines Knotens ist einfacher. Jedoch ist die Vorgehensweise die gleiche.

/**
 * Ein ListenKnoten wird initialisiert. Hierin werden später die Werte gespeichert.
 * Ebenfalls wird ein Zeiger zurück gegeben
 */
static KListNode *klist_initNode( void ) {
 
	//Für Knoten wird Speicher alloziiert
	KListNode *newNode = ( KListNode * ) malloc( sizeof(KListNode) );
 
	if( NULL != newNode ) {
		//Standartwerte werden gesetzt
		newNode->element = NULL;
		newNode->next = NULL;
	}
 
	return newNode;
 
}

Es wird wieder Speicher alloziert und die Elemente werden mit NULL initialisiert. Ein Zeiger auf den Speicherbereich wird zurück gegeben. Diese Funktion ist als static deklariert. Dies bedeutet, dass die Funktion von außerhalb nicht sichtbar ist. Für den Anwender sollte diese Funktion auch nicht weiter von Interesse sein, weil Knoten für ihn mit der add und insert Funktion erstellt werden.

Elemente eintragen

Um Elemente in einer Liste eintragen zu können muss erst einmal vorausgesetzt werden, dass wir wissen, wie wir an eine bestimmte Position in der Liste gelangen. Da die Liste keine lineare Speicherstruktur ist, jedoch die Adressen der Nachfolgeelemente gespeichert sind, müssen wir über einige Elemente gehen, um zu der gewünschten Position zu gelangen. Dazu gibt es zwei Strategien. Die erste ist die rekursive Lösung. Dies bedeutet, dass eine Funktion sich selber aufruft. Vorteil dabei ist, dass es übersichtlich ist und bleibt. Der Nachteil dabei ist jedoch, dass alle Variablen auf den Stack geschrieben werden müssen. Das heißt, dass je häufiger sich eine Funktion selber aufruft, der Speicherverbrauch weiter wächst. Die andere Möglichkeit ist der iterative Aufruf. Hierbei wird durch eine Schleife über die Elemente iteriert. Dadurch wird nicht so viel auf den Stack geschrieben. Nachteil ist jedoch, dass es unübersichtlicher ist.
Wichtig ist noch, wie das Element in die Liste eingefügt wird. Diese Liste besteht fast ausschließlich aus Zeigern. Es muss erst Speicher Alloziert werden und das Element muss dort hinein geschrieben werden.

/**
 * Diese Funktion alloziert Speicher und kopiert das Element auf welches der void-Zeiger zeigt
 * mit der angegebenen Größe in den Speicher
 */
static inline void *klist_cpyElement( void const * const element,
		size_t const size ) {
	//Inhalt auf den der void-Zeiger zeigt wird kopiert.
	void *ptr = malloc( size );
	if( NULL == ptr ) {
		return NULL;
	}
	return memcpy( ptr, element, size );
}

Diese Funktion ist als inline deklariert. Dies bedeutet, dass es keinen Funktionsaufruf gibt, sondern der Compiler an jeder Stelle wo diese Funktion aufgerufen wird den Code einfügt. Damit entfällt das schreiben und lesen von dem Stack.
Nun habe ich zwei Strategien zum eintragen implementiert.

add

Die erste und einfachste Möglichkeit ist add. Die Vorgehensweise ist dabei recht einfach. Wir befinden uns am Anfang im Kopf der Liste. Wir schauen, ob es einen ersten Knoten gibt. Wenn nicht dann muss einer angelegt werden. Dabei muss geprüft werden, ob ein Knoten angelegt werden konnte. Wenn nicht, wird add abgebrochen. Wenn ein Knoten angelegt werden konnte, muss die Kapazität der Liste um eins addiert werden. Nach der Überprüfung, ob es schon ein Knoten gibt, gehen wir in den ersten Knoten rein. Ob wir ihn nun angelegt haben, oder nicht. Nun wird geschaut, ob sich in dem Knoten, in welchem wir uns befinden, ein Element vorhanden ist. Wenn ja, dann schauen wir ob es einen Folgeknoten gibt. Wenn nicht legen wir diesen an. So geht es dann weiter, bis ein Knoten noch kein Element besitzt. Jedoch muss darauf geachtet werden, dass immer wieder geprüft wird, ob ein Knoten angelegt wurde oder nicht. Wir befinden uns jetzt in einem Knoten, welcher noch kein Element besitzt. Nun muss geprüft werden, ob das Element, welches wir eintragen wollen NULL ist oder nicht. Wenn es NULL ist, befinden wir uns am Ende und geben zurück, dass add erfolgreich war. Wenn es ungleich NULL ist, kopieren wir das Element in den Speicher. Bei Erfolg wird die Anzahl der Elemente in der Liste erhöht. Wenn dies nicht der Fall ist, brechen wir hier ab.
Nun können Elemente mit der add Funktion in die Liste eingetragen werden.

/**
 * Der Wert auf den der Zeiger element zeigt wird an die Liste angehangen
 */
char klist_add( KList * const list, void const * const element ) {
 
	//Wenn kein erstes Element bereit steht
	if( NULL == list->first ) {
		//Wird ein erster Knoten angelegt
		list->first = klist_initNode();
		//Wenn kein neuer Knoten angelegt werden konnte
		if( NULL == list->first ) {
			return 0;
		}
 
		//Wird die Kapazität vergrößert
		list->capacity++;
	}
 
	//Erster Knoten ist der Ausgangspunkt
	KListNode *node = list->first;
	//Solange wie Elemente in den Knoten vorhanden sind
	while( NULL != node->element ) {
		//Wenn es kein Folgeknoten gibt
		if( NULL == node->next ) {
			//wird einer angelegt
			node->next = klist_initNode();
			//Wenn ein neuer Knoten angelegt werden konnte
			if( NULL == node->next ) {
				return 0;
			}
			//Wird die Kapazität vergrößert
			list->capacity++;
		}
		//Es wird weiter durch die Liste iteriert
		node = node->next;
	}
	//Wenn ein leeres Element gefunden wurde, wird es gesetzt
	if( NULL != element ) {
		node->element = klist_cpyElement( element, list->type );
		//Wenn das Element eingetragen werden konnte, dann wird count inkremnetiert
		if( NULL == node->element ) {
			return 0;
		}
		list->count++;
	}
	else {
		node->element = NULL;
	}
	return 1;
 
}

insert

Die insert Funktion funktioniert ähnlich wie die add Funktion. Nur dass hierbei ein Index angegeben wird, an welche Stelle das Element geschrieben werden soll. Sollte die Kapazität der Liste noch nicht so groß sein, wie der Index, wird die Liste bis zu dem Index erweitert. Tritt der andere Fall ein, werden alle Folgenden Elemente um eine Position nach hinten verschoben.
Nun zu der Funktionsweise. Weil wir einen Listekopf benutzen, kann von Anfang an nicht mit einer Schleife durch die Liste iteriert werden. Darum muss der erste Knoten immer gesondert behandelt werden. Zu aller erst wird geprüft, ob der Index 0 ist. Wenn ja, dann befinden wir uns nun, am Listenkopf, schon am Ende. Wir speichern uns den Zeiger auf das erste Element zwischen. danach erstellen wir ein neues erstes Element. Hier muss wieder geprüft werden, ob das erstellen erfolgreich war. Dann fügen wir das Element in dem Knoten ein. Danach müssen wir natürlich noch das alte erste Element anfügen. Wenn dies alles geschafft wurde, sind wir schon fertig und können Erfolg berichten. Sollte der Index nicht 0 sein, dann müssen wir prüfen, ob schon ein erstes Element vorhanden ist. Wenn nicht, legen wir eins an. Danach iterieren wir wieder durch die Liste. Nun müssen wir darauf achten, dass wir bei jedem Schritt tiefer in die Liste den Index immer wieder um eins verringern. Sollte der Index dann 1 sein, müssen wir aufhören tiefer in die Liste einzudringen. Dies ist nötig, weil wir sonst das neue Element nicht an der gewünschten Position anfügen können. Denn wir arbeiten nur mit einer Kopie des Zeigers. Wenn wir den tmpNode Zeiger ändern, ändern wir nicht den next Zeiger des Elementes. Dann können wir den Zeiger auf das alte Element zwischenspeichern und nun das neue Element erstellen. Danach wieder das alte Element an das neue Element anfügen und wir können ebenfalls Erfolg verzeichnen, wenn alles geklappt hat.
Sollten viele Elemente hinzugefügt werden, sollte diese Funktion verwendet werden. Da man die Elemente an dem Index 0 schnell einfügen kann. Dazu muss dann nicht durch die ganze Liste iteriert werden, wie es bei der add Funktion der Fall ist. Denn je mehr Elemente durch add hinzugefügt werden, umso länger ist die Liste und umso länger muss add auch durch die Liste iterieren.

/**
 * Fügt ein Element am Index an. Alle folgenden Elemente
 * werden um ein Index nach hinten verschoben
 */
char klist_insert( KList * const list, int index, void const * const element ) {
 
	KListNode *tmpNode;
	//wenn der Index 0 ist
	if( 0 == index ) {
		tmpNode = list->first;
		list->first = klist_initNode();
		//Wenn kein knoten erzeugt werden konnte
		if( NULL == list->first ) {
			list->first = tmpNode;
			return 0;
		}
 
		list->capacity++;
 
		//Wenn das Element NULL ist, darf klist_cpyElement nicht ausgeführt werden
		if( NULL != element ) {
			list->first->element = klist_cpyElement( element, list->type );
			if( NULL == list->first->element ) {
				free( list->first );
				list->first = tmpNode;
				list->capacity--;
				return 0;
			}
 
			//Wenn alles geklappt hat, ist es wunderbar! ;)
			list->count++;
		}
		else {
			list->fist->element = NULL;
		}
		list->first->next = tmpNode;
		return 1;
	}
 
	//Wenn noch keine Elemente in der Liste sind
	if( NULL == list->first ) {
		list->first = klist_initNode();
		if( NULL == list->first ) {
			return 0;
		}
		list->capacity++;
	}
 
	//Es wird durch die Liste gegangen, bis vor dem einzufügenden Element
	KListNode *node = list->first;
	while( 1 < index ) {
		if( NULL == node->next ) {
			node->next = klist_initNode();
			if( NULL == node->next ) {
				return 0;
			}
			list->capacity++;
		}
		node = node->next;
		index--;
	}
 
	//Element wird eingefügt
	tmpNode = node->next;
	node->next = klist_initNode();
	if( NULL == node->next ) {
		free( node->next );
		node->next = tmpNode;
		return 0;
	}
 
	list->capacity++;
 
	//Wenn das Element NULL ist, darf klist_cpyElement nicht ausgeführt werden
	if( NULL != element ) {
		node->next->element = klist_cpyElement( element, list->type );
		//Wenn kein Speicher alloziiert werden konnte, muss alles rückgängig gemacht werden.
		if( NULL == node->next->element ) {
			free( node->next );
			node->next = tmpNode;
			list->capacity--;
			return 0;
		}
 
		list->count++;
	}
	else {
		node->next->element = NULL;
	}
	node->next->next = tmpNode;
	return 1;
 
}

Elemente ausgeben

Dies ist ebenfalls eine essentieller Teil einer Liste. Die Elemente, welche wir geschrieben haben, möchten wir ja auch wieder abrufen und benutzen können. Hierzu biete ich die get Funktion an. Ebenfalls biete ich eine search Funktion an, wobei dort direkt nach einem Element gesucht werden soll ein Zeiger zurück gegeben wird.

get

Durch die get Funktion kann mit Hilfe des Index ein Element ausgegeben werden. Dabei wird keine Kopie des Elementes zurück gegeben, sondern der Anwender arbeitet direkt auf das Element. Möchte der Anwender mit einer Kopie Arbeiten, muss er dies selbst erledigen. Jedoch bietet dies den Vorteil, dass der Anwender das Element nicht neu in die Liste speichern muss, wenn er das Element bearbeitet. Um das Element auszugeben wird zuerst geprüft, ob es den Index gibt. Wenn die Liste nicht so groß ist, wie der Index angibt, dann müssen wir uns auch nicht die Arbeit machen bis zu dem Index zu gelangen. Ansonsten müssen wir bis zu dem angegeben Index durch die Liste und können dann den Zeiger auf das Element zurück geben.

/**
 * Gibt das Element mit dem Index zurück. Es wird direkt
 * auf das Element in der Liste gearbeitet. Möchte mit einer
 * Kopie gearbeitet werden, muss das Element kopiert werden.
 */
void *klist_get( KList * const list, int index ) {
 
	if( index >= list->capacity ) {
		return NULL;
	}
 
	KListNode *node = list->first;
 
	while( 0 < index ) {
		index--;
		node = node->next;
		if( NULL == node ) {
			return NULL;
		}
	}
 
	return node->element;
 
}

search

Wieder muss durch die Liste iteriert werden. Dabei untersuchen wir nur direkt die Elemente mittels dem Funktionszeiger searchUserFunktion. Wurde diese bei dem Funktionsaufruf nicht gesetzt wird auf die memcmp Funktion aus der stdlib.h zurück gegriffen. Sollten wir das Element gefunden haben geben wir dies aus und sind fertig. Wenn nicht muss weiter durch die Liste iteriert werden. Sind wir am Ende der Liste angelangt und das Element wurde nicht gefunden wird NULL ausgegeben.

/**
 * Sucht das erste Vorkommen eines Elementes, welches mittels der
 * searchUserFunction und search macht und gibt einen Zeiger auf
 * dieses Element zurück.
 */
void *klist_search( KList *list, void *search, int(*searchUserFunction)(
		const void *s1, const void *s2, size_t n ) ) {
 
	//Wenn keine angegeben wurde, wird die std fkt verwendet
	if( NULL == searchUserFunction ) {
		searchUserFunction = memcmp;
	}
 
	//Wir untersuchen nur die Elemente.
	KListNode *listNode = list->first;
	while( NULL != listNode ) {
		if( 0 == searchUserFunction( listNode->element, search, list->type ) ) {
			//Wenn es macht, gibs aus
			return listNode->element;
		}
		listNode = listNode->next;
	}
 
	//Wenn nicht, gib es NULL zurück
	return NULL;
}

Löschen

Das Löschen von Elementen oder der Liste ist ein essentieller Teil einer Liste. Das Löschen sollte ebenfalls von der Liste selbst übernommen werden. Damit wird dem Anwender arbeit abgenommen und er muss sich nicht direkt um das freiräumen des Speichers kümmern. Nicht direkt heißt, dass er sich um das freiräumen eines Elementes kümmern muss. Dies geschieht jedoch schon beim initialisieren der Liste. Beim initialisieren der Liste gibt der Anwender die destroyUserFunction an. Diese erledigt das Löschen eines einzelnen Elementes. Dies ist sehr wichtig. Denn es kann sich alles mögliche in der Liste befinden. Wir, als Liste, wissen nicht was wir speichern. Sollte ein Element mit einem Zeiger gespeichert werden, würden wir den Zeiger einfach löschen. Jedoch hätten wir vorher nicht den Speicher des Zeigers frei geräumt. Also wäre dieser Speicher immer noch alloziert aber der Verweis weg. So entstehen Speicherlöcher. Da wir nicht wissen was für Elemente in der Liste gespeichert werden, muss der Anwender diesen Platz selber frei räumen. Jedoch braucht er dies nur ein mal zu tun. Denn wir werden die Funktion für alle Elemente der Liste einzeln aufrufen. Damit haben wir dem Anwender wiederum eine Menge Arbeit abgenommen.

Löschen eines einzelnen Knotens

Zu aller erst sollten wir erst einmal überprüfen, ob die Liste die Kapazität bis zu dem angegebenen Index hat. Wenn ja, dann lohnt es sich durch die Liste durch zu steppen. Wenn dies erledigt ist, dann müssen wir schauen, wo wir uns gerade befinden. Das heißt ob wir in die Liste "reinsteppen" müssen oder nicht. Wir müssen hier wieder vor den gewünschten Knoten. Nicht direkt auf ihn, weil wir die Folgeknoten wieder setzen müssen. Dies geht nur, wenn wir uns vor dem gewünschten knoten befinden. Sollten wir schon am Ende sein, also der Index ist 0, dann können wir mit dem freigeben beginnen. Wir müsse zuerst den Zeiger auf den Knoten sichern. Denn dort befindet sich unser Folgeknoten und das Element, welches wir löschen wollen. Nun können wir das Element mit der destroyUserFunction frei geben, wenn sich ein Element in diesem Knoten befindet. Wenn nicht, brauchen wir es natürlich nicht frei geben, da kein Speicher reserviert wurde. Nun kopieren wir den Zeiger des Folgeknotens. Dieser repräsentiert dann den ersten Knoten in der Liste. Danach können wir den zu löschenden Knoten freigeben. Die Kapazität muss un noch um Eins verringert werden und dann sind wir schon fertig. Sollte der Index nicht 0 sein, müssen wir natürlich bis vor das Element gehen. Jedoch sind dann die gleichen Schritte erforderlich.

/**
 * Diese Funktion entfernt einen Listenknoten an dem angegebenen Index.
 * Sollte die komplette Liste händisch gelöscht werden, wird empfohlen,
 * Immer das erste Element zu löschen und abzuprüfen ob count größer als
 * 1 ist.
 */
void klist_remove( KList * const list, int index ) {
 
	//Wenn kein Knoten in der Liste vorhanden ist, muss auch nix gelöscht werden
	if( index >= list->capacity ) {
		return;
	}
 
	//Der erste Knoten ist der Ausgangspunkt
	KListNode *node = list->first;
	//Wenn der Index 0 ist, ist dies ein Sonderfall
	if( 0 == index ) {
		//Wenn ein Element vorhanden ist,
		if( NULL != node->element ) {
			//Dann wird es gelöscht
			list->destroyElementUserFunction( node->element );
			list->count--;
		}
		//Der nachfolgende Knoten ist dann der erste
		list->first = node->next;
		//Knoten wird gelöscht
		free( node );
		list->capacity--;
		return;
	}
 
	//So lange wie nicht der Vorgänger erreicht ist
	while( 1 < index ) {
		//Iteriere weiter
		index--;
		//Folgeelement wird neuer Ausgangspunkt
		node = node->next;
		//Wenn dieser NULL ist, wurde das Ende der Liste erreicht
		if( NULL == node ) {
			//Ende im Gelände
			return;
		}
	}
 
	//Es wird sich der zu löschende Knoten genommen
	KListNode *oldNode = node->next;
	//Wenn ein Element vorhanden ist
	if( NULL != oldNode->element ) {
		//Wird es frei gegeben
		list->destroyElementUserFunction( oldNode->element );
		list->count--;
	}
 
	//Der neue Nächste ist der Folgende des alten
	node->next = oldNode->next;
	//Alter Knoten wird frei gegeben
	free( oldNode );
	list->capacity--;
 
}

Löschen der Liste

Das löschen der gesamten Liste gestaltet sich nach dem implementiere des entfernen von Elementen denkbar einfach. So lange wie es einen ersten Knoten gibt, löschen wir nur das erste Element der Liste. Der Anwender muss jedoch den Zeiger auf die Liste selbst manuell freigeben. Denn wir arbeiten wiederum nur mit einer Kopie des Zeigers.

/**
 * Vernichtet die Liste und räumt damit den Speicher wieder frei.
 * Es werden jedoch nur die Knoten in der Liste gelöscht.
 * Die Listen-Struktur muss per Hand gelöscht werden.
 */
void klist_removeList( KList * const list ) {
 
	while( NULL != list->first ) {
		klist_remove( list, 0 );
	}
 
}

Resize

Das die Größe einer Liste neu gemessen wird ist sehr wichtig. Denn es kann immer passieren, dass der Anwender ein Element anlegt welches NULL ist oder Elemente aus der Liste löscht, ohne dass er den Knoten an sich löscht. Dazu biete ich die Resize Funktion an. Die Vorgehensweise hier ist etwas anders als die Vorgehensweise beim Eintragen oder ähnlichem. Natürlich bildet das erste Element wieder eine Ausnahme. Da wir nicht wissen, wie viele Elemente, welche NULL sind nach dem ersten Knoten kommen, wird dies diesmal in einer while Schleife behandelt. Wir befinden uns einfach so lange in diese Schleife, wie die Elemente des ersten Knotens NULL sind. Sollte ein Element NULL sein, speichern wir uns temporär den zu löschenden Knoten, setzen den Folgeknoten als erstes Element und löschen den Knoten, welchen wir dazu auserkoren haben. Dies geschieht so lange, bis der erste Knoten ein Element besitzt. Danach geschieht prinzipiell das gleiche mit den folgenden Knoten. Wir müssen und nur abspeichern, wo wir uns gerade befinden. Dann iterieren wir so lange durch die Liste, bis wir am Ende angekommen sind. Zwischendurch prüfen wir, ob die nächsten Knoten immer ein Element besitzen. Wenn nicht, dann löschen wir den Knoten. Dies immer so lange, bis wieder ein Knoten kommt, indem sich ein Element befindet. Danach dann wieder ein Knoten weiter in der Liste. Bis zum Schluss.

/**
 * Wenn eine Liste resizeable ist, dann werden alle
 * Elemente, welche NULL sind entfernt.
 */
char klist_resize( KList * const list ) {
 
	//Wenn die Liste resized werden darf
	if( !list->resizeable ) {
		return 0;
	}
 
	if( NULL == list->first ) {
		return 1;
	}
 
	KListNode *tmpNode;
 
	//Erstes element wird geprüft
	while( NULL == list->first->element ) {
		//Element ist NULL und wird gelöscht
		tmpNode = list->first;
		list->first = tmpNode->next;
		list->capacity--;
 
		free( tmpNode );
	}
 
	//Der aktuelle Knoten, an welchem wir uns gerade befinden
	KListNode *iterateNode = list->first;
	while( NULL != iterateNode ) {
 
		//Wenn es einen nächsten Knoten gibt und das Element NULL ist
		while( NULL != iterateNode->next && NULL == iterateNode->next->element ) {
			//Dann wird dieser Knoten gelöscht
			tmpNode = iterateNode->next;
			iterateNode->next = tmpNode->next;
			list->capacity--;
 
			free( tmpNode );
		}
 
		//Wenn nicht, gehen wir weiter durch die Liste
		iterateNode = iterateNode->next;
 
	}
 
	return 1;
 
}

Eine Liste an eine Liste anhängen

Bei dieser Funktion soll die zweite Liste an die erste Liste an gehangen werden. Dazu sollte jedoch erst einmal geprüft werden, ob beide Listen rudimentär gleich sind. Dazu wird die Größe der Elemente verglichen und resizeable. Danach muss nur zum letzten Element der Liste gegangen werden und dann kann der erste Knoten aus der zweiten Liste an das Ende der ersten Liste gehangen werden. Dazu sollten dann noch die Kapazität und die Anzahl der Elemente übernommen werden. In der zweiten Liste werden diese dann 0 gesetzt und das erste Element NULL. Der Anwender muss sich nun darum kümmern, den Listenkopf der zweiten Liste frei zu geben.

/**
 * Die Liste second wird an first angehangen.
 * Second muss jedoch manuell wieder freigegeben werden,
 * wenn diese danach nicht mehr benutzt wird.
 */
char klist_append( KList * const first, KList * const second ) {
 
	if( first->type != second->type ) {
		return 0;
	}
 
	if( first->resizeable != second->resizeable ) {
		return 0;
	}
 
	if( NULL == first->first ) {
		first->first = second->first;
 
		first->capacity += second->capacity;
		first->count += second->count;
 
		second->first = NULL;
		second->capacity = 0;
		second->count = 0;
		return 1;
	}
 
	KListNode *node = first->first;
	while( NULL != node->next ) {
		node = node->next;
	}
 
	node->next = second->first;
 
	first->capacity += second->capacity;
	first->count += second->count;
 
	second->first = NULL;
	second->capacity = 0;
	second->count = 0;
 
	return 1;
 
}

Liste klonen

Die Liste, welche wir erstellt haben, können wir natürlich auch klonen. Der Umstand, dass wir Zustandsinformationen speichern ermöglicht uns dies. Wir kennen die Größe der Elemente und an welcher Speicheradresse diese beginnen. Wir kennen ebenfalls die Anzahl der Knoten und die Anzahl der Elemente. Das klonen an sich ist dann relativ einfach. Zum einen sollte gesagt werden, wenn ein Fahler auftritt, dann sollte der gesamte Klon gelöscht und wieder freigegeben werden. Als nächstes sollten wir darauf achten, dass wir uns bei dem Klon, wie auch bei dem Original immer an der gleichen Position befinden. Zu aller erst kopieren wir natürlich den Listenkopf. Danach erfolgt das kopieren der Elemente.

/**
 * Klont die Liste mit allen Elementen und Eigenschaften.
 * Es wird ein void - Zeiger auf den Listenkopf zurück gegeben
 * Wenn die Liste nicht geklont werden kann, bsp durch zu wenig
 * Speicher, wird ein NULL zurück gegeben.
 */
void *klist_clone( KList *list ) {
 
	//Neuer Listenkopf wird erstellt.
	KList *result = klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
	if( NULL == result ) {
		return NULL;
	}
 
	//capacity und count werden ebenfalls übernommen
	result->capacity = list->capacity;
	result->count = list->count;
 
	//Erstes Element wird kopiert.
	if( NULL != list->first ) {
		result->first = klist_initNode();
 
		if( NULL == result->first ) {
			free( result );
			return NULL;
		}
 
		//Element wird kopiert
		if( NULL != list->first->element ) {
			result->first->element = klist_cpyElement( list->first->element,
					result->type );
			if( NULL == result->first->element ) {
 
				free( result->first );
				free( result );
 
				return NULL;
			}
		}
	}
 
	//Tmp Elemente
	KListNode *tmpListNode = list->first;
	KListNode *tmpResultNode = result->first;
 
	//Alle anderen Elemente können nun auch kopiert werden.
	while( NULL != tmpListNode->next ) {
 
		tmpResultNode->next = klist_initNode();
		if( NULL == tmpListNode->next ) {
			klist_removeList( result );
			free( result );
 
			return NULL;
		}
 
		tmpListNode = tmpListNode->next;
		tmpResultNode = tmpResultNode->next;
 
		if( NULL != tmpListNode->element ) {
			tmpResultNode->element = klist_cpyElement( tmpListNode->element,
					result->type );
			if( NULL == tmpResultNode->element ) {
				klist_removeList( result );
				free( result );
 
				return NULL;
			}
		}
 
	}
 
	return result;
 
}

Liste in Array konvertieren

Auch dies ist uns möglich, durch das speichern von Status Informationen. Wir haben die Größe der Elemente und die Anzahl der Elemente in der Liste. Außerdem noch eine Hilfsvariable, zum speichern der Position. Dies können wir alles in einer for-Schleife realisieren. Wir schauen in dem ersten Knoten, ob sich dort ein Element befindet. Wenn nicht, dann müssen wir weiter gehen, bis sich ein Element findet. Danach kopieren wir es einfach und Addieren die Hilfsvariable um eins. Das so lange, wie die Hilfsvariable kleiner als die Anzahl der Elemente in der Liste ist. Dann sind wir fertig. Und können den Zeiger zurück geben. Nun zu der Funktion.

/**
 * Es wird die komplette Liste in einen linearen Speicherbereich
 * geladen. Es wird ein Zeiger auf das erste Element zurück
 * gegeben. Es kann dann wie in einem Array durchitteriert
 * werden. Der Speicherbereich ist list->count * list->type
 * groß. Der Speicherplatz muss manuell mit free wieder freigegeben
 * werden. Da der Speicherbereich mit malloc erstellt wurde.
 */
void *klist_toArray( KList *list ) {
 
	//Speicherplatz wird reserviert.
	void *result = malloc( list->count * list->type );
 
	//Hilfsvariable
	int pos = 0;
	KListNode *node = list->first;
 
	//da wir mit einem void Zeiger arbeiten, müssen wir immer list->type Speicherzellen weiter
	for( ; pos < ( list->count * list->type ); pos += ( int ) list->type ) {
 
		//Falls Elemente NULL sind, überspringen wir diese einfach
		while( NULL == node->element && NULL != node->next ) {
			node = node->next;
		}
 
		//Element wird kopiert
		memcpy( ( result + pos ), node->element, list->type );
 
		//Nochmals ein test, ob es noch weitere Knoten gibt
		if( NULL == node->next )
			break;
 
		//Weiter im Programm
		node = node->next;
 
	}
 
	return result;
}

Liste teilen

Beim Liste Teilen bedienen wir uns wieder eines Indexes. Diesen bekommen wir von dem Anwender. Denn diese muss angeben, ab welchem Index er die Liste teilen möchte. Hier wird wiederum eine Hilfsvariable benötigt. Denn wir müssen wissen, wie viele Elemente sich nach der Teilung in den einzelnen Listen befinden. Ebenfalls müssen wir prüfen, ob beide Listen ähnliche Eigenschaften aufweisen. Dies bedeutet, ob sie beide gleichen Typs sind, ob beide resizeable sind und natürlich ob diese beiden die selben UserFunktions nutzen. Wenn dies alles überprüft wurde, gehen wir bis zu dem Index und zählen immer die Elemente mit. Danach kopieren wir den Zeiger in die neue Liste und löschen den Zeiger aus dem aktuellen Knoten. Danach nur nch ein wenig rechnen und schon sind wir wieder fertig.

/**
 * Teilt die Liste nach dem angegebenen Index. First ist die
 * Komplette Liste, diese wird gekürzt, ausschließlich Index.
 * Der Index wird das erste Element der zweiten Liste.
 */
void klist_splitAt( KList * const first, KList *second, int index ) {
 
	//Wenn der index größer ist als die capacity
	if( index >= first->capacity ) {
		//dann muss nichts gemacht werden
		return;
	}
 
	//Dann wird die Liste initialisiert, sollte es nicht schon geschehen sein
	if( NULL == second ) {
		return;
	}
	else {
		//Wenn die Listen keine gemeinsame Basis haben.
		if( first->destroyElementUserFunction
				!= second->destroyElementUserFunction || first->resizeable
				!= second->resizeable || first->type != second->type
				|| first->compareUserFunction != second->compareUserFunction ) {
			return;
		}
	}
 
	second->capacity = first->capacity - index;
	int countElements = 0;
 
	//Wenn ab dem 0ten Element geteilt werden soll
	if( 0 == index ) {
 
		//Danach werden die relevanten Daten & Zeiger kopiert...
		second->capacity = first->capacity;
		second->count = first->count;
		second->first = first->first;
 
		//Und aus der alten gelöscht.
		first->capacity = 0;
		first->count = 0;
		first->first = NULL;
 
	}
 
	//Das erste Element hat er...
	index--;
	KListNode *node = first->first;
	while( 0 < index ) {
		//Wenn in dem aktuellen Element Inhalt ist
		if( NULL != node->element ) {
			//Dann wird eins hoch gezählt
			countElements++;
		}
		//Das nächste Element schnabbn
		node = node->next;
		index--;
	}
 
	//Hier könnte auch noch ein Element sein
	if( NULL != node->element ) {
		countElements++;
	}
 
	//Elemente kopieren...
	second->count = first->count - countElements;
	second->first = node->next;
 
	//Erste Liste wird gekürzt.
	node->next = NULL;
	first->count = countElements;
	first->capacity = first->capacity - second->capacity;
 
}

sortieren der Liste

Konzept

Es gibt verschiedene Möglichkeiten Datenstrukturen zu sortieren. Dazu kann Wikipedia[1] einen Überblick geben. Alle Verfahren haben ihre Vor- und Nachteile. Ich habe mich für Mergesort[2] entschieden. Er zeichnet sich durch seine Stabilität aus. Dies bedeutet, das es keine besondern Fälle gibt, wo er schneller oder langsamer ist. Die Komplexität ist immer gleich. Außerdem kann Mergesort bei verketteten Listen als inline Verfahren implementiert werden. Dies bedeutet das Die Elemente nicht kopiert werden brauchen und somit auch kein oder kaum extra Speicher benötigt wird. In diesem Beispiel ist dies auch fast der Fall. Das einzige wozu wir zusätzlichen Speicher benötigen ist der Listenkopf. Denn diesen müssen wir für jede Rekrusionsstufe neu erstellen.
Nun zu dem Prinzip wie Mergesort Funktioniert. Mergesort funktioniert nach dem Prinzip teile und herrsche. Die Datenstruktur, also unsere Liste wird in zwei Teile geteilt. Danach werden die Teile an sich sortiert. Das bedeutet ganz einfach, wir rufen Mergesort mit unsere Liste auf. Die Liste wird geteilt in die linke und rechte Liste. Die linke Liste wird nun wieder sortiert und ist damit unser neue Ausgangspunkt. Es wird überprüft, ob sich mehr als ein Knoten in der Liste befindet. Wenn ja, dann wird die Liste wieder geteilt und weiter sortiert. Wenn nicht, also wenn nur noch ein Knoten in der Liste ist, gilt diese als sortiert und wird zurück gegeben.
Nun folgt das interessante. Nämlich das mergen. Gemerged werden immer genau zwei Listen zu einer. Dazu wird sich eine neue Liste geschaffen. In dieser wird das Ergebnis zurück gegeben. Die beiden ersten Elemente der linken und rechten Liste werden verglichen. Das größere Element wird in die neue Liste geschrieben und aus der alten Liste raus gelöscht. Nun werden wieder beide ersten Elemente vergleichen. Dabei ist zu beachten, das vor jedem Vergleich die Anzahl der Knoten in der Liste geprüft werden. Wenn die linke Liste keine Knoten mehr hat, dann wird die gesamte rechte Liste an das Ergebnis gehangen und der Mergeprozess ist beendet. Wenn die rechte Liste keine Knoten mehr hat, wird demzufolge die linke Liste an gehangen.
In dem Merge - Schritt habe ich mir keine Ergebnisliste erstellt sondern habe alles in der linken Liste sortieren lassen. Damit meine ich, wenn in der linken Liste das größere Element war, bin ich in der linken Liste ein Knoten weiter gegangen. Wenn in der rechten Liste das größere Element war, habe ich dies eingefügt in die linke Liste und bin dann ein weiter gegangen. Dies habe ich so lange gemacht, bis ich die ganze Liste sortiert hatte.

mergesort

Dies ist nun der Mergesort - Algorithmus. Er besteht aus zwei Funktionen. Wobei die sort Funktion sich selbst nochmals aufruft. Was passiert nun hier? Zu aller erst prüfen wir, ob die Kapazität der Liste eins ist. Wenn ja, dann gilt die Liste als sortiert und wir geben diese zurück. Wenn nicht, erstellen wir uns einen neuen Listenkopf. Natürlich mit den gleichen Grundeigenschaften wie unsere originale Liste. Danach teilen wir die Liste in der Hälfte. Sollte etwas schief gehen, geben wir einen Fehler zurück. Nun lassen wir beide Teillisten für sich sortieren. Wenn es einen Fehler beim sortieren der Teillisten gibt, muss aufgeräumt werden. Dies eird dann auch getan. Wenn alles gut gelaufen ist werden die Listen zusammen gebracht mittels merge. Wenn dort wieder alles geklappt hat, müssen wir nur die rechte Liste wieder frei machen und sind fertig mit dem sortieren. Das mergen kann man sich als zusammenführen der Listen vorstellen. Dies ist der schwierigere Schritt an mergesort und wird unten weiter beschrieben.

/**
 * Sortiert eine Liste anhand des mergesort -
 * Sortieralgorythmus. Der comparor befindet
 * sich in der Liste
 */
char klist_sort( KList * const list ) {
 
	if( 1 == list->capacity ) {
		return 1;
	}
 
	KList *right = klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
 
	klist_splitAt( list, right, ( list->capacity / 2 ) );
 
	//Wenn die Liste nicht erstellt werden konnte
	if( NULL == right ) {
		return 0;
	}
 
	//Hier vlt threads starten
	if( !klist_sort( list ) || !klist_sort( right ) ) {
 
		//Tmp Listenkopf muss wieder freigegeben werden.
		//um keine Elemente zu verlieren, wird die rechte Liste an die Linke angehangen.
		klist_append( list, right );
		free( right );
 
		return 0;
	}
 
	//Listen werden gemerged
	if( !klist_merge( list, right ) ) {
 
		//Tmp Listenkopf muss wieder freigegeben werden.
		//um keine Elemente zu verlieren, wird die rechte Liste an die Linke angehangen.
		klist_append( list, right );
		free( right );
 
		return 0;
 
	}
 
	//Tmp Listenkopf muss wieder freigegeben werden.
	klist_removeList( right );
	free( right );
 
	return 1;
 
}

merge

Das mergen der beiden Listen ist das komplizierteste an Mergesort. Jedoch, wenn man einmal das Prinzip dahinter verstanden hat, ist es ganz simpel. Es werden immer die ersten beiden Elemente der Liste verglichen. Dann wird ein Element, kommt darauf an wie verglichen wird, in die Ergebnis Liste geschrieben und aus der Ursprungs Liste gelöscht. Wenn einer der beiden Listen leer ist, wird die andere komplett an die Ergebnis Liste an gehangen.
Ich habe es ähnlich implementiert. Ich habe mir die Ergebnis Liste gespart. Die komplett sortierte Liste wird am ende in der linken Liste vorhanden sein. Die rechte Liste wird Leer sein.
Zu aller erst prüfe ich jedoch die Ähnlichkeit der beiden Listen. Sind diese nicht so ähnlich, wie ich sie haben möchte, wird abgebrochen und ein Fehler zurück gegeben. Danach prüfe ich ob eine der beiden Listen leer ist. Wenn ja, bin ich fertig und speichere die vorhandene Liste in der linken Liste. Wenn bis dahin alles so verlaufen ist, wie ich es wollte, fange ich an die Listen zu mergen. Dazu benötige ich einen temporären Knoten. In diesem wird das aktuelle Element vor dem "ersten" Element der linken Liste gespeichert. Nun vergleiche ich das erste Element der rechten Liste mit dem nächsten Element, welches sich in dem temporären Knoten befindet. Ich muss es mit dem nächsten Element des temporären Knotens vergleichen, weil ich sonst das Element aus der rechten Liste nicht vor das aktuelle Element legen kann. Wenn das rechte Element nach der UserCompareFunction größer ist als das nächste Element aus dem ersten knoten, schreibe ich es vor das nächste Element. Danach gehe ich ein Knoten weiter. Dies mache ich so lange, bis ich mit meinem temporären Knoten das Ende der Liste erreicht habe, oder bis kein Knoten mehr in der rechten Liste ist. Sollten noch Elemente in der rechten Liste sein, dann hänge ich diese an die linke Liste ran. Nach alledem bin ich fertig mit dem mergen und kann erfolg zurück geben.

/**
 * Fügt zwei Listen zusammen. Die Reihenfole wird durch den
 * comparor der Liste left festgelegt.
 */
static char klist_merge( KList * const left, KList * const right ) {
 
	//Wenn die Listen nicht die gleiche Struktur haben, wird abgebrochen...
	if( left->destroyElementUserFunction != right->destroyElementUserFunction
			|| left->resizeable != right->resizeable || left->type
			!= right->type || left->compareUserFunction
			!= right->compareUserFunction ) {
		return 0;
	}
 
	//Sollte eine der Listen Leer sein
	if( NULL == right->first ) {
		return 1;
	}
 
	if( NULL == left->first ) {
		left->first = right->first;
		right->first = NULL;
		return 1;
	}
 
	KListNode *tmpNode;
 
	//Nur wenn beide Elemente nicht NULL sind kann verglichen werden
	if( NULL != left->first->element && NULL != right->first->element ) {
 
		if( left->compareUserFunction( left->first->element,
				right->first->element, left->type ) >= 0 ) {
 
			tmpNode = left->first;
			left->first = right->first;
			right->first = right->first->next;
			left->first->next = tmpNode;
 
			left->capacity++;
			left->count++;
 
			right->capacity--;
			right->count--;
 
		}
 
	}
	//Sollte das linke Element NULL sein, wird das rechte vor ihm eingefügt
	else if( NULL == left->first->element ) {
 
		tmpNode = left->first;
		left->first = right->first;
		right->first = right->first->next;
		left->first->next = tmpNode;
 
		left->capacity++;
		left->count++;
 
		right->capacity--;
		right->count--;
 
	}
 
	//Nun kann erst durch die Liste iteriert werden.
	KListNode *iterateNode = left->first;
	while( NULL != iterateNode->next && NULL != right->first ) {
 
		if( NULL != iterateNode->next->element && NULL != right->first->element ) {
 
			if( left->compareUserFunction( iterateNode->next->element,
					right->first->element, left->type ) >= 0 ) {
				tmpNode = iterateNode->next;
				iterateNode->next = right->first;
				right->first = right->first->next;
				iterateNode->next->next = tmpNode;
 
				left->capacity++;
				left->count++;
 
				right->capacity--;
				right->count--;
			}
 
		}
		//Wenn das element NULL sein sollte, wird es hinten dran gahangen
		else if( NULL == iterateNode->next->element ) {
			tmpNode = iterateNode->next;
			iterateNode->next = right->first;
			right->first = right->first->next;
			iterateNode->next->next = tmpNode;
 
			left->capacity++;
			left->count++;
 
			right->capacity--;
			right->count--;
		}
 
		//Weiter gehts
		iterateNode = iterateNode->next;
	}
 
	//Wenn die rechte liste nicht leer ist und das ende der linken erreicht ist, wird die rechte ran gehangen.
	if( NULL != right->first ) {
		iterateNode->next = right->first;
		right->first = NULL;
 
		left->capacity += right->capacity;
		left->count += right->count;
 
		right->capacity = 0;
		right->count = 0;
	}
 
	//Wenn alles glatt lief, ist er fertig...
	return 1;
}

Fazit

Eine Liste ist eine dynamische Speicherstruktur und kann nur dort alle ihre Stärken ausspielen. Bei einer gleichen Anzahl an Elementen ist eine Liste immer größer als ein Array. Ebenfalls ist diese eventuell langsamer als ein Array. Jedoch kann die Liste in dem Sinne punkten, wo die Anzahl der Elemente nicht bekannt ist. Denn dort wissen wir nicht, wie viele Elemente wir für ein Array reservieren sollen. Auch wenn der Platz nicht ausreicht, ist die realloc Funktion sehr langsam.
Ich kann mir vorstellen, dass es viele Strategien gibt, Listen zu beschleunigen. Jedoch sind mir davon keine genauen, mit Quelle, bekannt. Was ich mir vorstellen könnte ist dies mittels Cluster zu realisieren. Damit meine ich, das man in einem Knoten nicht nur ein Element speichern kann, sondern eine bestimmte Anzahl. Dies wäre dann sozusagen ein Array von Elementen in einem Knoten. Der Vorteil davon liegt klar auf der Hand. Ich habe weniger Knoten, durch welche ich durch gehen muss. In den einzelnen Knoten kann ich dann bestimmte Elemente direkt zurück geben. Nachteile sind auch klar. Der Verwaltungsaufwand wird natürlich größer.

Links

Zeiger in C
Funktionszeiger
Der void-Zeiger
Einfach verkettete Listen
Const correctness