Summary  
This chapter explains how to define a singly linked list node in C, showing how to use pointers to link nodes dynamically and prevent self-referential memory allocation errors.

General domain of usage  
Data structures

Eine **verkettete Liste** in C ist eine einfache dynamische Datenstruktur, die aus Elementen besteht, die als Knoten bezeichnet werden.
Jeder Knoten enthält Daten (wie eine Variable oder ein Objekt) sowie einen Zeiger auf den nächsten Knoten in der Liste.


So sieht ein typischer Knoten in einer einfach verketteten Liste in C aus:

c3RydWN0IE5vZGUgewogICAgaW50IGRhdGE7ICAgICAgICAgICAvLyBkYXRhIGluIG5vZGUKICAgIHN0cnVjdCBOb2RlKiBuZXh0OyAgLy8gcG9pbnRlciB0byBuZXh0IG5vZGUKfTs=

Wenn Sie anstelle eines Zeigers auf den nächsten Knoten einfach eine Instanz eines neuen Knotens erstellen, erhalten Sie einen Fehler.

Der Compiler kann für eine solche Struktur keinen Speicher reservieren, da sie sich selbst enthält. Das ist, als würde man versuchen, sich selbst mit den eigenen Augen von außen zu betrachten.

Die Verwendung eines Zeigers löst dieses Problem, da der Compiler weiß, wie viel Speicher für eine Zeigervariable reserviert werden muss.

Der Zeiger des letzten Knotens ist immer `NULL`.

Hinweis

#define CATCH_CONFIG_MAIN
#include <catch2/catch.hpp>
#include <cstdlib>

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int value);

// Helper: free a list
void freeList(struct Node* head) {
    struct Node* current = head;
    while (current != nullptr) {
        struct Node* tmp = current;
        current = current->next;
        free(tmp);
    }
}

TEST_CASE("createNode returns non-null and correct data") {
    struct Node* node = createNode(42);
    REQUIRE(node != nullptr);
    REQUIRE(node->data == 42);
    REQUIRE(node->next == nullptr);
    free(node);
}

TEST_CASE("createNode multiple nodes and link manually") {
    struct Node* head = createNode(10);
    struct Node* second = createNode(20);
    struct Node* third = createNode(30);

    REQUIRE(head != nullptr);
    REQUIRE(second != nullptr);
    REQUIRE(third != nullptr);

    head->next = second;
    second->next = third;

    REQUIRE(head->data == 10);
    REQUIRE(head->next == second);
    REQUIRE(second->data == 20);
    REQUIRE(second->next == third);
    REQUIRE(third->data == 30);
    REQUIRE(third->next == nullptr);

    freeList(head);
}

TEST_CASE("Single node list") {
    struct Node* node = createNode(100);
    REQUIRE(node != nullptr);
    REQUIRE(node->data == 100);
    REQUIRE(node->next == nullptr);
    free(node);
}

TEST_CASE("Link nodes incrementally") {
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    head->next = second;

    struct Node* current = head;
    REQUIRE(current->data == 1);
    current = current->next;
    REQUIRE(current->data == 2);
    REQUIRE(current->next == nullptr);

    freeList(head);
}

TEST_CASE("Create nodes with negative and zero values") {
    struct Node* head = createNode(0);
    struct Node* second = createNode(-10);
    head->next = second;

    REQUIRE(head->data == 0);
    REQUIRE(head->next == second);
    REQUIRE(second->data == -10);
    REQUIRE(second->next == nullptr);

    freeList(head);
}

test.cpp

Erwerben Sie ein fundiertes Verständnis darüber, wie Strukturen in C funktionieren, von grundlegenden Definitionen bis hin zu fortgeschrittenen Speicher-Konzepten. Erforschen Sie, wie Zeiger mit strukturierten Daten interagieren, entdecken Sie effiziente Möglichkeiten zur Organisation von Informationen und gewinnen Sie Sicherheit durch die Implementierung realer Datenstrukturen wie verketteter Listen.

Erkunden Sie die Grundlagen von Structs, verstehen Sie deren Anwendungszwecke und gewinnen Sie Sicherheit beim Definieren, Erstellen und Zugreifen auf strukturierte Daten.

Entdecken Sie, wie Zeiger mit Strukturen interagieren, erfahren Sie, warum diese Verbindung wichtig ist, und beherrschen Sie wichtige Techniken wie dynamische Speicherzuweisung und das Übergeben von Strukturen an Funktionen.

Erwerben Sie ein fundiertes Verständnis dafür, wie Structs im Speicher abgelegt werden, untersuchen Sie Alignment und Padding und erfahren Sie, wie Unions die effiziente Verwaltung gemeinsam genutzter Daten ermöglichen.

Vertiefung in fortgeschrittene Struct-Muster, einschließlich verschachtelter und anonymer Structs, praktische Methoden zur Kombination mit Arrays sowie Einführung in gängige Datenstrukturen.

Stärkung des Selbstvertrauens durch die Implementierung einer verketteten Liste von Grund auf, Untersuchung ihrer Struktur und Erstellung grundlegender Funktionen zum Hinzufügen, Durchlaufen und Verwalten von Listenelementen.

Grundkonzept und Struktur

Lösung