Summary  
Describes how to dynamically create and insert nodes into a singly linked list by allocating memory and updating head and next pointers, handling both empty and non-empty list cases.  

General domain of usage  
Data structures and algorithms

Um eine einfach verkettete Liste nützlich zu machen, müssen Knoten hinzugefügt werden. Hierbei wird die Logik implementiert, um Knoten in die Liste einzufügen. Neue Knoten werden erstellt, miteinander verbunden und so integriert, dass die Liste beim Hinzufügen von Elementen dynamisch wächst.

Dieser praxisorientierte Ansatz vermittelt ein genaues Verständnis der Abläufe im Hintergrund.

## Implementierung der Knoteneinfügung

Eine einfache Funktion zur Erstellung eines Knotens:

- Übergabe einer Zahl vom Typ **int** als Argument, die im Datenfeld des Knotens gespeichert wird;
- Erstellung eines Zeigers auf einen dynamisch allozierten Speicherbereich (unter Berücksichtigung der Knotengröße);
- Überprüfung des Erfolgs der Speicherzuweisung für den Knoten;
- Einfügen des gewünschten Wertes (Funktionsargument) in das Datenfeld;
- Der Next-Zeiger muss **NULL** sein, da die Funktion nur einen Knoten erstellt;
- Die Funktion gibt einen Zeiger auf den Speicherbereich zurück, in dem der Wert gespeichert ist.

Die Funktion **AddNewNode()** erhält einen Zeiger auf einen Zeiger, da sie den Wert des Zeigers auf den ersten (**head**) Knoten der Liste sowie den Wert, der im neuen Knoten gespeichert wird, ändern kann:

```
void AddNewNode(struct Node** head, int value) 
{
	...
}
```
Ist die Liste leer (**\*head == NULL**), wird der Zeiger auf den Kopf der Liste (**\*head**) einfach auf den neuen Knoten (**newNode**) gesetzt; in diesem Fall wird newNode zum ersten Knoten (Kopfknoten).
Bei einer nicht-leeren Liste wird mit einer Schleife nach dem letzten Knoten gesucht.

Der aktuelle Knoten dient als Pufferknoten, mit dessen Hilfe die Liste durchlaufen und ein Knoten gefunden werden kann, der auf nichts mehr zeigt (**\*next == NULL**).



```
struct Node* current = *head;

while (current->next != NULL) 
{
    ...
}
```

Am Ende muss der neue Knoten `newNode` zum letzten Knoten werden, was bedeutet, dass `current->next` gleich `newNode` sein muss. Nun ist newNode der letzte Knoten in der Liste.

Als Aufgabe soll eine Funktion entwickelt und hinzugefügt werden, die neue Knoten zu bestehenden Knoten hinzufügt.


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

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

void addNewNode(struct Node** head, int value);

struct Node* createNode(int value);

// Helper function to free the linked list
void freeList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        struct Node* tmp = current;
        current = current->next;
        free(tmp);
    }
}

TEST_CASE("Create a single node") {
    struct Node* node = createNode(42);
    REQUIRE(node != nullptr);
    REQUIRE(node->data == 42);
    REQUIRE(node->next == nullptr);
    free(node);
}

TEST_CASE("Add a node to an empty list") {
    struct Node* head = nullptr;
    addNewNode(&head, 10);

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

    freeList(head);
}

TEST_CASE("Add multiple nodes and check order") {
    struct Node* head = nullptr;
    addNewNode(&head, 10);
    addNewNode(&head, 20);
    addNewNode(&head, 30);

    struct Node* current = head;
    REQUIRE(current->data == 10);
    current = current->next;
    REQUIRE(current->data == 20);
    current = current->next;
    REQUIRE(current->data == 30);
    REQUIRE(current->next == nullptr);

    freeList(head);
}

TEST_CASE("Add negative and zero values") {
    struct Node* head = nullptr;
    addNewNode(&head, 0);
    addNewNode(&head, -5);
    addNewNode(&head, 15);

    struct Node* current = head;
    REQUIRE(current->data == 0);
    current = current->next;
    REQUIRE(current->data == -5);
    current = current->next;
    REQUIRE(current->data == 15);
    REQUIRE(current->next == nullptr);

    freeList(head);
}

TEST_CASE("Add large number of nodes") {
    struct Node* head = nullptr;
    int n = 1000;
    for (int i = 0; i < n; i++) {
        addNewNode(&head, i);
    }

    struct Node* current = head;
    for (int i = 0; i < n; i++) {
        REQUIRE(current != nullptr);
        REQUIRE(current->data == i);
        current = current->next;
    }
    REQUIRE(current == nullptr);

    freeList(head);
}

TEST_CASE("Add to non-empty list preserves previous nodes") {
    struct Node* head = nullptr;
    addNewNode(&head, 1);
    addNewNode(&head, 2);

    addNewNode(&head, 3);
    addNewNode(&head, 4);

    struct Node* current = head;
    REQUIRE(current->data == 1);
    current = current->next;
    REQUIRE(current->data == 2);
    current = current->next;
    REQUIRE(current->data == 3);
    current = current->next;
    REQUIRE(current->data == 4);
    REQUIRE(current->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.

Elemente Hinzufügen

Implementierung der Knoteneinfügung

Lösung