Site hosted by Angelfire.com: Build your free website today!

Verkettete Listen


Eine verkettete Liste ist eine Menge von Knoten, wobei jedes Element mit einem *next Zeiger auf das ihm folgende zeigt.
Die Vorteile von verketteten Listen sind:
 * dass die Größe nicht im Voraus bekannt sein muss
 * leicht neue Elemente der Liste hinzugefügt werden können
 * leicht Elemente entfernt werden können
 * es einfach ist, die Elemente umzuordnen
 * mehrere Listen einfach zusammengehängt werden können

Die Nachteile von verketteten Listen sind:
 * dass man nicht direkt mit einem Index auf ein Element zugreifen kann
 * dass es zumindest bei einer einfach verketteten Liste einem Element nicht möglich ist, auf seinen Vorgänger zu zeigen

Der folgende Code zeigt neben einem Beispielknoten Funktionen, die eine leere Liste erzeugen, einen neuen Knoten einfügen und einen Knoten aus der Liste entfernen. Es ist anzumerken, dass der erste Knoten head und der letzte Knoten z (z zeigt auf sich selbst) standardmäßig als Pseudoknoten in einer Liste vorhanden sind und den Zweck haben, die verschiedensten Operationen zu vereinfachen. 
Sonst gibt es dazu eigentlich nicht mehr so viel zu sagen. Enjoy the code ;-)!

struct node {
     itemType key;
     node *next;
};

void cm_LeereListeErzeugen() {
     node *head = new node;
     node *z = new node;
     head->next = z;
     z->next = z;
}

void cm_NodeEinfuegen(node *k, itemType wert) {
     node *x = = new node;
     x->key = wert;
     x->next = k->next;
     k->next = x;
}

void cm_NodeEntfernen(node *k) {
     node *x = k->next;
     k->next = x->next;
     if(x != z) delete x;
}


   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher    

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze    

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage