CodeUtility
Mach dir das Coderleben leicht!
Datenstrukturen in C/C++

Einfach verkettete Liste in C und C++

In dieser Lektion baust du eine einfach verkettete Liste in C und C++ auf, durchläufst sie und gibst sie wieder frei.

Einführung

Eine einfach verkettete Liste (singly linked list) besteht aus Knoten (nodes), und jeder Knoten speichert einen Wert und einen Zeiger auf den nächsten Knoten. Anders als bei einem Array müssen die Knoten nicht hintereinander im Speicher liegen, deshalb kannst du neue Elemente einfügen, ohne andere zu verschieben.

Wichtige Punkte

  • Lege fest, welche Bedingungen in der Datenstruktur immer gelten müssen (Invarianten), bevor du die Operationen schreibst.
  • Behandle die Fälle leer, voll und fehlgeschlagene Speicherreservierung vollständig.
  • Bewerte bei jeder Operation Komplexität und Speicherverwaltung gemeinsam.

So funktioniert es

Füge vorne oder hinten Knoten hinzu und klicke auf einen Knoten, um ihn zu löschen. Mit Start folgst du den next-Zeigern von head bis NULL.

Codebeispiele in C und C++

C
Code ausführen →
main.c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
Ergebnis der Ausführung
1 2 3
C++
Code ausführen →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
Ergebnis der Ausführung
1 2 3

C und C++ im Vergleich

In der C-Version wird jeder Knoten mit malloc reserviert, und am Ende muss das Programm die ganze Liste durchlaufen und für jeden Knoten free aufrufen. In der C++-Version sind die Knoten mit std::unique_ptr verbunden, deshalb wird beim Zerstören des ersten Knotens automatisch die ganze nachfolgende Kette freigegeben.

C

Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.

C++

Klassen und Container schützen die Korrektheit der Daten und verwalten ihre Ressourcen selbst.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

  • Ergänze Tests für den leeren Zustand und für das Erreichen der Kapazitätsgrenze.
  • Schreibe die Speicherfreigabe und prüfe auf Speicherlecks.
  • Vergleiche die Komplexität mit dem entsprechenden Container der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges