Algorithmen und Datenstrukturen in C/ Listen

Wikipedia hat einen Artikel zum Thema:

Verkettete Listen

Eine verkettete Liste ist eine dynamische Datenstruktur, die eine unbestimmte Anzahl von zusammengesetzten Datentypen enthält. Dieser Datentyp dient der Speicherung von Daten. Die aus diesen Datentypen erzeugten Datenstrukturen werden Knoten oder node genannt. Die einzelnen Knoten der Liste sind dabei durch Zeiger verbunden. Das bedeutet, dass jedes Element der Liste außer dem ersten Element einen Vorgänger und (außer dem letzten Element) einen Nachfolger hat. Das ermöglicht einen sehr flexiblen Umgang mit den Daten in den Knoten.

Verkettete Listen kommen dann zum Einsatz, wenn man eine unbestimmte Anzahl an Elementen speichern und verarbeiten muss.

In einigen Programmiersprachen (z.B. in Java) gibt es Standard-Bibliotheken in denen Verkettete Listen bereits implementiert sind. In C gibt es keine Sprachmittel oder Bibliotheken. Die Ursache dafür ist, dass verkettete Listen sich zu der Zeit, als C entwickelt wurde, noch nicht allgemein in der Informatik durchgesetzt hatten. Trotzdem lassen sie sich in C mit ein wenig Aufwand äußerst effizient realisieren.

Vorteile

Verkettete Listen sind dynamische Datenstrukturen und lassen sich zur Laufzeit verändern.
Generische Programmierung ist ohne großen Mehraufwand möglich.

Nachteile

Beim falschen Setzen von Zeigern kann es schnell zu Endlosschleifen kommen.
Es müssen Sonderfälle für den ersten und letzten Knoten beachtet werden.

Einfach verkettete Liste

Die einfachste Form einer Liste ist die einfach verkettete Liste. Sie besitzt neben ihrem Wert einen Zeiger auf den nachfolgenden Knoten. Der Zeiger vom letzten Element zeigt auf NULL. Der NULL-Zeiger definiert das Ende der verketteten Liste.

typedef struct ListNode {
   int value;
   struct ListNode* next;
} ListNode;

Doppelt verkettete Liste

Die doppelt verkettete Liste besitzt einen weiteren Zeiger. Dieser zeigt auf den vorhergehenden Knoten. Eine doppelt verkettete Liste ermöglicht ein effektiveres Löschen und Sortieren. Außerdem kann auch von hinten nach vorne iteriert werden. Der zusätzliche Zeiger muss aber in allen Algorithmen berücksichtigt werden, und bedeutet daher mehr Aufwand für den Programmierer.

typedef struct ListNode {
   int value;
   struct ListNode* prev;
   struct ListNode* next;
} ListNode;

zyklische Liste

Eine zyklische Liste (oder Ringliste) entsteht, wenn man den Zeiger des letzten Knotens auf einen anderen Knoten zeigen lässt. Dieser muss nicht unbedingt der erste sein. Dies ist in einer einfach verketteten und einer doppelt verketteten Liste möglich. Um einen Zyklus in einer verketteten Liste effizient zu ermitteln, gibt es den Hase-Igel-Algorithmus.

void HaseIgel(ListNode* list) {
    ListNode* igel = list;
    ListNode* hase = list->next;

    while (hase && hase != igel) {
        hase = hase->next;
        igel = igel->next;
        if (hase)
            hase = hase->next;
    }
    if (hase)
        printf("Liste ist zyklisch\n");
    else
        printf("Liste ist nicht zyklisch\n");
}

Für die Funktion HaseIgel(...) wird eine verkettete Liste erstellt und der erste Knoten übergeben. Der Algorithmus durchläuft die verkette Liste mit unterschiedlicher Schrittweite. Während jeder Iteration der Schleife wird der Zeiger igel um einen Knoten verschoben und der Zeiger hase um zwei. Wenn beide Zeiger auf den selben Knoten referenzieren, hat die Liste einen Zyklus. Wenn hase das Ende der Liste erreicht gibt es keinen Zyklus.

Eine andere Möglichkeit um einen Zyklus zu finden, ist bei einem Durchlauf alle angeschauten Knoten zu markieren. Trifft man nun auf einen bereits markierten Knoten, hat die Liste einen Zyklus.

Algorithmen

Bei den Algorithmen für verkettete Listen wird von einer doppelt verketteten Liste ausgegangen, da diese die am häufigsten anzutreffende Variante ist.

Erstellen

Der folgende Algorithmus dient zum Erstellen und Anhängen eines Knoten mit dem Wert value an die verkettete Liste list. Wenn list ein Nullzeiger ist, wird eine neue verkette Liste erstellt. Die Funktion liefert einen Zeiger auf den erstellten Knoten zurück.

struct ListNode* appendNode(struct ListNode* list, int value) {
    // Speicher bestellen
    struct ListNode* node = malloc(sizeof(struct ListNode));

    // Zum Ende der Liste gehen
    for (; list && list->next; list = list->next);
    
    // Wert eintragen und Zeiger setzen
    node->value = value;
    node->prev = list ? list : NULL;
    node->next = NULL;
    
    if (list)
        list->next = node;
         
    return node;
}

Einfügen

ListNode* insertNode(ListNode* list, ListNode* dest, ListNode* obj) {
    if (!list || !obj)
       return NULL;
       
    if (!dest)
        dest = list;
    
    obj->next = dest;
    obj->prev = dest == list ? NULL : dest->prev;
    if (dest == list)
        list = obj;
    dest->prev->next = obj;
    dest->prev = obj;
 
return list;  
}

Ausgeben

Mit dieser Funktion lassen sich die Werte der verketteten Knoten ausgeben. Die Schleife schaut jeden Knoten einzeln an und gibt seinen Wert an die Standardausgabe zurück. Der Parameter list ist der erste Knoten in der verketteten Liste.

void printList(struct ListNode* list) {
    // Schleife zum durchlaufen
    for (; list; list = list->next)
        printf("%d ", list->value);
}

Verschieben

Die Funktion dient zu Verschieben eines Knotens in einer verketteten Liste. Sie basiert auf den Funktionen Entfernen und Einfügen. Der erste Parameter list ist der erste Knoten in der verketteten Liste. Er ist auch der Rückgabewert. Der zweite Parameter dest ist der Knoten vor den eingefügt werden soll. Ist dieser gleich NULL, wird der dritte Parameter obj, der zu verschiebende Knoten, an das Ende gesetzt.

ListNode* moveNode(ListNode* list, ListNode* dest, ListNode* obj) {
    if (!list || !obj)
       return NULL;
    
    if (dest == NULL) {
        list = removeNode(list, obj);        
        list = appendNode(list, obj);
    }
    else {
        list = removeNode(list, obj);
        list = insertNode(list, dest, obj);
    }
          
    return list;
}

Entfernen

Diese Funktion dient zum Entfernen eines beliebigen Knoten aus einer verketteten Liste. Die Sonderfälle für den ersten und letzten Knoten werden ebenfalls berücksichtigt. Die Funktion besitzt als ersten Parameter list den ersten Knoten der verketteten Liste, sowie als zweiten Parameter obj den zu entfernenden Knoten. Zurückgegeben wird immer der (neue) erste Knoten in der verketteten Liste. Zu beachten ist, das der Knoten nur aus der Liste herausgenommen wird. Er wird nicht gelöscht! Diese Funktion ist notwendig um ein Bewegen oder Sortieren der Liste möglich zu machen.

ListNode* removeNode(ListNode* list, ListNode* obj) {
    if (!list || !obj)
       return NULL;
    
    if (obj->next)
        obj->next->prev = obj->prev;
    else
        obj->prev->next = NULL;
    if (obj->prev)
        obj->prev->next = obj->next;
    else {
        obj->next->prev = NULL;
        list = obj->next;
    }

    return list;
}

Suchen und Sortieren

Das Suchen und Sortieren in einer verketteten Liste ist natürlich von den gespeicherten Daten in den Knoten abhängig. Für verkettete Liste mit int-Zahlen finden sich fertige Algorithmen in den entsprechenden Kapiteln zu Such- und Sortieralgorithmen. Bei einer anderen Datenstruktur im Knoten müssen diese Algorithmen angepasst werden.