C++ Verkettete List

Verkettete Listen in C++ erstellen, Einträge sortiert und unsortiert hinzufügen und wieder entfernen.



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;
}