Advanced   Java   Services Einfach verkettete Listen Back Next Up Home


Einfach verkettete Listen

Eine einfach verkettete Liste ist Reihe von Elementen (auch Knoten genannt), die durch Zeiger miteinander verbunden sind. Das erste Element wird gerne Rootelement genannt. Mit Hilfe des Zeigers kann man von einem Element zum nächsten navigieren. Da es nur einen Zeiger gibt, kann man die Liste nur in einer Richtung durchlaufen. Typische Operationen für eine Liste sind das Erstellen des Wurzelelements, das Anhängen eines Elements, das Löschen eines Elements, das Löschen der ganzen Liste.

Die Elemente einer Liste sind vom Typ struct. Wir geben uns folgendes vor:

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

typedef struct node  node;

Das folgende kleine Programm erzeugt einen Wurzelknoten und zwei Nachfolger und gibt die Daten aus.

/*
 * Eine Wurzel mit zwei Nachfolgern zu Fuß
 */
void beispiel()
{
   puts("beispiel");

   // Erstellen von root
   node *root = malloc(sizeof(node));
   if (root == NULL) return;

   root->data = 17;
   root->next = NULL;

   // Anhängen eines Knotens
   node *secondNode = malloc(sizeof(node));
   if (secondNode == NULL) return;

   root->next = secondNode;
   secondNode->next = NULL;
   secondNode->data = 19;

   // Anhängen eines weiteren Knotens
   node* last = malloc(sizeof(node));
   if (last == NULL) return;

   secondNode->next = last;
   last->next = NULL;
   last->data = 21;

   //Ausgeben der Daten
   for( ; root != NULL; root = root->next)
      printf("%d ", root->data);
   printf("\n");
}

Im Hauptspeicher kann man sich das wie folgt vorstellen.

c-linked-list-01.jpg

Der Zeiger des letzten Knotens muß explizit auf NULL gesetzt werden. Alle Algorithmen erkennen das Ende an diesem NULL-Zeiger.


createRoot, appendNode, printList, listLength, seekList

Die folgenden Funktionen sind einfache Verallgemeinerungen des ersten Beispiels.


createRoot
/*
 * Die Funktion createroot erzeugt einen ersten Knoten mit Daten
 * Falls kein Speicher angefordert werden kann, gibt die Funktion
 * NULL zurück, ansonsten den Rootknoten.
 */
node* createRoot(int data)
{
   node *root = malloc(sizeof(node));
   if (root == NULL) return NULL;

   root->next = NULL;
   root->data = data;
   return root;
}

appendNode
/*
 * Hängt am Ende an. Falls nicht der letzte Knoten übergeben wurde, wird das Ende gesucht.
 * Auf diese Weise kann man einen beliebigen Knoten übergeben. Es wird nicht geprüft,
 * ob die Daten bereits in der Liste sind. Wenn der erste Parameter NULL ist oder kein
 * Speicher angefordert werden kann gibt die Funktion NULL zurück. Im Erfolgsfall wird
 * der neue Knoten zurückgegeben.
 */
node* appendNode(node* oldtail, int data)
{
   if (oldtail == NULL ) return NULL;

   node *newtail = malloc(sizeof(node));
   if (newtail==NULL) return NULL;

   while (oldtail->next != NULL)  // ans Ende
      oldtail = oldtail->next;

   // nun ist oldtail->next NULL
   oldtail->next = newtail;
   newtail->next = NULL;
   newtail->data = data;
   return newtail;
}

printList
/*
 * Gibt die Liste ab der Stelle root aus
 */
void printList(node* root)
{
   if (root == NULL) return;
   for ( ; root != NULL ; root = root->next)
      printf("%d ", root->data);
   printf("\n");
}

listLength
/*
 * Ermittelt die Länge der Liste ab dem übergebenen Knoten
 */
int listLength(node* root)
{
   if (root == NULL) return 0;
   int len = 1;
   for( ; root->next != NULL; len++)
      root = root->next;

   return len;
}

seekList
/*
 * Durchsucht die List nach einem übergebenen Datenelement. Wird es gefunden,
 * so wird ein Zeiger auf den Knoten zurückgegeben, andernfalls NULL. Es wird
 * nur das erste Auftreten des Elements gesucht
 */
node* seekList(node* root, int data)
{
   if (root == NULL) return NULL;
   for(; root !=NULL; root = root->next)
      if (root->data == data) return root;

   return NULL;
}

Freigeben der Liste

Beim Freigeben der ganzen Liste muß man den Zeiger auf den nächsten Knoten zwischenspeichern bevor man den aktuellen Knoten freigibt, damit man noch auf den nächsten Knoten zugreifen kann.

/*
 * Gibt den Speicher ab der Stelle curr frei. Ist der übergebene
 * Knoten der Wurzelknoten, so wird die ganze Liste gelöscht.
 */
void freelist(node* curr)
{
   if (curr == null) return;
   while (curr->next != null)
   {
      node *nextnode = curr->next;
      free(curr);
      curr = nextnode;
   }
   // jetzt muß noch das letzte gelöscht werden:
   free(curr);
}

Löschen eines Elements der Liste

Beim Löschen eines Knotens sind drei Fälle zu unterscheiden, Löschen von root, Löschen innerhalb der Liste und Löschen des Endes der Liste. Im ersten Fall muß root neu gesetzt werden, aus diesem Grund wird ein Zeiger auf den Zeiger auf root übergeben. In den letzten beiden Fällen muß der Vorgänger bekannt sein und dessen Zeiger neu gesetzt werden, daher ist die Funktion aufwendiger.

/*
 * Löschen eines Elements der Liste
 * Returnwert:
 * 0 falls nichts gelöscht wurde.
 * 1 falls root gelöscht wurde (und es somit eine neue wurzel gibt)
 * 2 falls innen gelöscht wurde
 * 3 falls am ende gelöscht wurde
*/
int delete(node** pRoot, int data)
{
   if (pRoot == null || *pRoot == NULL) return 0;  // Nichts gelöscht

   // pRoot löschen
   if ( data == (*pRoot)->data )
   {
      node* newRoot = (*pRoot)->next;
      free(*pRoot);
      *pRoot = newRoot;
      return 1;   // neue root
   }

   /* Beginnend mit pRoot->next wird geprüft, ob ein Knoten die übergebenen daten enthält
    * Der Vorgänger wird gespeichert, damit man im Falles des Findens den Knoten aushängen kann
    * Falls nichts gefunden wird, ist curr->next = NULL und man ist am Ende angekommen
    * Nun wird noch curr untersucht und evtl abgehängt. Kommen Daten mehrmals vor, so wird
    * nur das erste Vorkommen gelöscht. Da ein Löschen am Anfang eine neue Wurzel ergibt,
    * wird immer die Wurzel zurückgegeben.
    */
   node* prev = *pRoot;
   node* curr = (*pRoot)->next;
   for (; curr->next != null; prev = prev->next, curr = curr->next)
   {
      if ( curr->data == data )
      {
         // curr aushängen, curr löschen
         prev->next = curr->next;
         free(curr);
         return 2;  // innen gelöscht
      }
      // else weitersuchen
   }
   // da nichts gefunden ist hier curr->next = NULL
   if ( curr->data == data )
   {
      prev->next = curr->next; // NULL
      free(curr);
      return 3;  // am ende gelöscht
   }
   // else nichts gefunden
   return 0;
}

Aufbau einer geordneten Liste

Der Aufbau einer geordneten Liste funktioniert ähnlich wie das Löschen eines Knotens, man unterscheidet die gleichen drei Fälle: Einhängen vor root, Insert nach root und vor dem Ende, und Anhängen am Ende.

/*
 * Geordnetes einfügen
 * Erhält einen Zeiger auf root, damit root über die parameterliste
 * aktualisiert werden kann.
 * Returnwert:
 * 0 falls nichts eingefügt wurde.
 * 1 falls vor root eingefügt wurde (und es somit eine neue wurzel gibt)
 * 2 falls ein echtes insert stattfindet
 * 3 falls am ende angehängt wird
 */
int insert(node** pRoot, int data)
{
   if (pRoot == null || *pRoot == NULL) return 0;

   // "einhängen" vor pRoot
   if ( data < (*pRoot)->data )
   {
      node *newroot = malloc(sizeof(node));
      if (newroot != NULL)
      {
         newroot->next = *pRoot;
         newroot->data = data;
         *pRoot = newroot;
         return 1; // neue root
      }
      return 0;
   }

   /* Beginnend mit pRoot wird geprüft, ob man zwischen
    * pRoot und und pRoot->next einhängen kann. falls
    * diese prüfung positiv ausfällt wird eingehängt
    * und mit return beendet. falls nicht, kommt man ans Ende der liste
    * (curr->next == null) und die Schleife wird normal beendet.
    * In diesem Fall wird am Ende angehängt.
    */
   node* curr = *pRoot;
   for (; curr->next != null; curr = curr->next)
   {
      if ( curr->data < data && data <= curr->next->data)
      {
         node *newnode = malloc(sizeof(node));
         if (newnode != null)
         {
            newnode->next = curr->next;
            curr->next = newnode;
            newnode->data = data;
         }
         return 2;  // echtes insert
      }
      //else  weitersuchen
   }
   // falls kein einfügestelle gefunden, ist hier curr->next = NULL, also append
   node *newnode = malloc(sizeof(node));
   if (newnode != null)
   {
      newnode->data = data;
      newnode->next = curr->next;
      curr->next = newnode;
      return 3; // append
   }
   return 0;
}
Valid XHTML 1.0 Strict top Back Next Up Home