C/C++ Programmierung: Verkettete Listen

Verkettete Listen gehören zu den so genannten dynamischen Datenstrukturen. Die einzelnen Elemente dieser Strukturen – in der Regel Instanzen einer Klasse – werden als Knoten bezeichnet. Ganz nach Bedarf können nun neue Knoten erzeugt oder nicht mehr benötigte Knoten gelöscht werden.

Damit man auf die einzelnen Knoten zugreifen kann, benötigt man deren Speicheradressen. Bei einfach verketteten Listen wird die Speicheradresse eines neu erzeugten Knoten einfach im zuletzt erzeugten Knoten gespeichert. Hierzu dient die Zeigervariable NextNode. Hier eine kleine Beispielklasse:

class CNode
{
public:

    long id;
    long age;
    char name[100];

    CNode* NextNode;

    CNode()
    {
        NextNode = NULL;
    }

    ~CNode()
    {
        printf("\nAufruf Destruktor: %d\n", id);
    }
};

Den Anfangs- und Endknoten (bzw. Kopf- und Schwanzknoten) kommt bei der Arbeit mit einer verketteten Liste eine besondere Bedeutung zu:

// Anfangsknoten (Kopf) der Liste
CNode* g_Head = NULL;

// Endknoten (Schwanz) der Liste
CNode* g_Tail = NULL;

Die Funktion Traverse_List() dient zum Durchlaufen der Liste. Diese Funktion hat die folgenden Aufgaben zu erfüllen:

  • Starte beim Anfangsnoten und gebe die Daten aus, die in diesem Knoten gespeichert sind.
  • Gehe zum nächsten Knoten und gebe die Daten aus, die in diesem Knoten gespeichert sind.
  • Wiederhole den vorherigen Schritt so lange, bis der Endknoten erreicht ist.


void Traverse_List(CNode* pHead)
{
    // Überprüfen, ob die Liste existiert:
    if(pHead == NULL)
    {
        printf("\nListe ist leer!\n");
        return;
    }

    CNode* node = pHead;

    while(node != NULL)
    {
        // Auslesen der Daten:
        printf("\nID: %d", node->id);
        printf("\nAge: %d", node->age);
        printf("\nName: %s \n", node->name);

       // Auf zum nächsten Knoten:
       node = node->NextNode;
    }
}

Mithilfe der Funktion Insert_Node() wird ein neuer Knoten initialisiert und als neuer Endknoten an die Liste angehängt. Hierbei müssen drei Fälle berücksichtigt werden:

  • Im einfachsten Fall existiert noch keine Liste. Der neue Knoten wird zugleich zum Anfangs- und Endknoten der neu erzeugten Liste.
  • Im zweiten Fall besteht die Liste schon aus einem einzelnen Knoten (dem Anfangsknoten). Der neue Knoten wird direkt an den Anfangsknoten angehängt und wird so selbst zum neuen Endknoten.
  • Im dritten Fall besteht die Liste schon aus zwei oder mehr Elementen. Der neue Knoten wird direkt an den Endknoten angehängt und wird selbst zum neuen Endknoten.


Hinweis:
Damit die Anfangs- und Endknotenzeiger manipuliert werden können, müssen der Insert_Node()-Funktion die Speicheradressen dieser Zeiger übergeben werden. In diesem Zusammenhang spricht man auch von einem Zeiger auf einen Zeiger.

void Insert_Node(CNode** ppHead, CNode** ppTail,
                 long id, long age, char *pName)
{
    // neuen Knoten erzeugen
    CNode* newNode = new CNode;

    // Dem neuen Knoten die neuen Werte zuweisen:
    newNode->id  = id;
    newNode->age = age;
    strcpy(newNode->name, pName);
    newNode->NextNode = NULL;

    // Den Status der Liste überprüfen:
    if(*ppHead == NULL)
    {
        // leere Liste
        // Anfangs- und Endknoten sind
        // identisch
        *ppHead = *ppTail = newNode;
    }
    else if(*ppHead != NULL &&
            (*ppHead == *ppTail))
    {
        // Liste besteht aus exakt einem Element
        (*ppHead)->NextNode = newNode;

        // newNode wird neuer Endknoten:
        *ppTail = newNode;
    }
    else
    {
        // Liste besteht aus zwei oder mehr Elementen
        (*ppTail)->NextNode = newNode;

        // newNode wird neuer Endknoten:
        *ppTail             = newNode;
    }
}

Die Funktion Delete_List() dient zum Löschen der kompletten Liste. Vom Anfangsknoten an werden bis zum Endknoten nacheinander alle Knoten gelöscht.

void Delete_List(CNode** ppHead, CNode** ppTail)
{
    // Überprüfen, ob die Liste existiert:
    if(*ppHead == NULL)
        return;

    CNode* pointer = NULL;

    while(*ppHead != *ppTail)
    {
        pointer = *ppHead;
        *ppHead = (*ppHead)->NextNode;
        delete pointer;
    }

    // letzten Knoten löschen:
    delete *ppHead;
    *ppHead = *ppTail = pointer = NULL;
}

Einzelne Knoten können mithilfe der Delete_Node()-Funktion gelöscht werden. Identifiziert wird der betreffende Knoten anhand seiner id. Ist besagter Knoten gefunden, müssen beim Löschvorgang vier Fälle berücksichtigt werden:

  • Der zu löschende Knoten ist zugleich Anfangs- und Endknoten.
  • Der zu löschende Knoten ist der Anfangsknoten.
  • Der zu löschende Knoten ist der Endknoten.
  • Der zu löschende Knoten befindet sich zwischen Anfangs- und Endknoten. In diesem Fall wird die Speicheradresse des nachfolgenden Knoten im NextNode-Zeiger des Vorgängerknotens gespeichert. Der zu löschende Knoten wird also praktisch überbrückt.

void Delete_Node(CNode** ppHead, CNode** ppTail, int id)
{
    // Überprüfen, ob die Liste existiert:
    if(*ppHead == NULL)
        return;

    // benötigte Hilfszeiger
    CNode* current_ptr  = *ppHead;
    CNode* previous_ptr = *ppHead;

    // Die Liste durchgehen und den Knoten suchen,
    // der gelöscht werden soll:
    // Wird dieser gefunden, dann wird die Schleife
    // verlassen.
    while(current_ptr->id != id &&
          current_ptr != NULL)
    {
        previous_ptr = current_ptr;

        // Endknoten erreicht, zu löschender
        // Knoten aber nicht gefunden:

        if(current_ptr == *ppTail)
            return;

        current_ptr = current_ptr->NextNode;
    }

    // Der gesuchte Knoten wurde gefunden:
    // Jetzt müssen wir wieder verschiedene
    // Fälle überprüfen:

    // Liste besteht nur aus einem Element
    if(*ppHead == *ppTail)
    {
        // Knoten löschen:
        delete *ppHead;
        *ppHead = *ppTail = NULL;
    }

    // Der Anfangsknoten soll gelöscht werden
    else if(current_ptr == *ppHead)
    {
        //der nachfolgende Knoten wird der
        // neue Anfangsknoten:
        *ppHead = (*ppHead)->NextNode;

        //Knoten löschen:
        delete current_ptr;
        current_ptr = NULL;
    }

    // Der Endknoten soll gelöscht werden:
    else if(current_ptr == *ppTail)
    {
        // Es muß dafür Sorge getragen werden,
        // daß der vorletzte Knoten nicht mehr
        // auf den alten Endknoten zeigt.
        // previous_ptr zeigt auf den vorletzen Knoten:
        previous_ptr->NextNode = NULL;

        // Knoten löschen
        delete current_ptr;
        current_ptr = NULL;

        // Der vorletzte Knoten wird zum neuen Endknoten:
        *ppTail = previous_ptr;
    }

    // Der zu löschende Knoten befindet sich irgendwo
    // zwischen Anfangs- und Endknoten:
    else
    {
        // Verbinden des Vorgängerknotens mit dem
        // nachfolgenden Knoten.
        // Der zu löschende Knoten wird somit überbrückt:
        previous_ptr->NextNode = current_ptr->NextNode;

        // Knoten löschen
        delete current_ptr;
        current_ptr = NULL;
    }
}