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