Datenstrukturen in C/C++

Einfach verkettete Liste

Jeder Knoten enthält einen Wert und einen Link zum Nachfolger.

Was ist Einfach verkettete Liste?

Jeder Knoten enthält einen Wert und einen Link zum Nachfolger.

Erzeuge, durchlaufe und lösche eine verkettete Liste.

Wichtige Punkte

Definiere Invarianten vor den Operationen.
Behandle leere, volle und fehlgeschlagene Allokationen.
Bewerte Laufzeit und Speicherbesitz gemeinsam.

Codebeispiele in C und 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;
}

Erwartete Ausgabe

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

Erwartete Ausgabe

1 2 3

Vergleich zwischen C und C++

C allokiert Knoten mit malloc und muss jeden freigeben. C++ unique_ptr gibt beim Zerstören des Kopfes die gesamte Kette frei.

Strukturen und Operationen sind getrennt; Allokation ist explizit.

C++

Klassen und Container schützen Invarianten und verwalten Ressourcen.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Teste leere und volle Zustände.
Implementiere Cleanup und prüfe auf Leaks.
Vergleiche mit einem Standardcontainer.