| Titel: | C++ Verkettete List | |
| Beschreibung: | Verkettete Listen in C++ erstellen, Einträge sortiert und unsortiert hinzufügen und wieder entfernen. | |
| Kategorie: | Programmierung | |
| Unterkategorie | C/C++ | |
| Benötigtes Fachwissen: | Fortgeschrittene | |
| Artikel überarbeiten: | C++ Verkettete List | |
Eine verkettete Liste ist eine dynamische Datenstruktur, mit dessen Hilfe danamisch - ohne vorher zu wissen wie viele Einträge diese später haben wird - aufbauen kann.
Beim Aufbau einer verketteten Liste gibt es für jeden Listeneintrag einen Datenteil und einen Zeiger. Im Datenteil werden die Nutzdaten gespeichert und im Zeiger wird jeweils auf das nächst folgende Element gezeigt.
Übliche Listenarten sind einfach verkettete Listen und doppelt verkettete Liste. Einfach verkettete Listen zeigen immer nur auf das jeweils nächste Element, doppelt verkettete Listen zeigen sowohl auf das nächste - als auch auf das vorherige Element.
Dieser Artikel behandelt nur einfach verkettete Listen
// Knotenstruktur einer verketteten Liste struct Node { int data; Node* next; }; Node* head = 0;
// Wert x absteigend sortiert einfügen Node* q = new Node; Node* p = head; while(p->next != 0 && p->next->data > x) p = p->next; q->next = p->next; p->next = q;
// Wert x löschen Node* p = head; while(p->next != 0 && p->next->data != x) p = p->next; Node* q = p->next; //Zeiger ein Element nach p setzen p->next = q->next; //Knoten aushängen delete q; //ausgehängten Knoten löschen
// Alle x ausgeben Node* p = head; while(p->next != 0) { p = p->next; //auf nächstes Element verweisen if( p->data == x ) //Wert suchen cout << p->data << endl; }
// Konstruktor // Hilfskopfknoten erstellen Node* q = new Node; head->next = q; //Node an Listenanfang einfügen knotenanzahl = 0;//Anzahl der Knoten definieren q->data = 0; //Datenschritt entfernen
// Destruktor // Alle Elemente löschen while (head != 0) { Node* p = head; head = head->nextPtr; delete p; }
C++ Zeiger und Referenzen