Summary  
This chapter covers dynamically creating nodes and inserting them into a singly linked list—handling both empty and non-empty lists by allocating memory, traversing via pointers, and updating head and next pointers (using a pointer‐to‐pointer for the head).

General domain of usage  
Data structure implementation

To make your singly linked list useful, you need to add nodes to it. You will implement the logic to insert nodes into the list. You will create new nodes, connect them, and integrate them so that the list grows dynamically as you add elements. 

This hands-on approach helps you understand exactly what happens behind the scenes.

## Implementing Node Insertion

Let's write a simple function to create a node. This function should:

- As an argument, take a number of type **int**, which will be stored in the node in the data field;
- Create a pointer to a dynamically allocated memory area (taking into account the size of the node);
- Check the success of memory allocation for the node;
- Put the required value (function argument) into the data field;
- The next pointer must be **NULL**, since the function creates only one node;
- The function must return a pointer to the memory area where value is stored.

The **AddNewNode()** function takes a pointer to a pointer, because it can change the value of the pointer to the first (**head**) node of the list, as well as the value that will be stored in the new node:

```
void AddNewNode(struct Node** head, int value) 
{
	...
}
```
If the list is empty (**\*head == NULL**), we simply update the pointer to the head of the list (**\*head**) to point to the new node (**newNode**), in which case newNode will become the first node (head node).
In the case of a non-empty list, we use a loop to look for the last node.

The current node plays the role of a buffer node, with its help we can iterate through the list and find a node that points to nowhere (**\*next == NULL**).



```
struct Node* current = *head;

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

After all, you need to make the new node `newNode` the last node, which means `current->next` must be equal to `newNode`. Now newNode is the last node in the list.

As a task, you need to figure out and add a function for adding new nodes to existing nodes.


#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

Gain a solid understanding of how structs work in C, from basic definitions to advanced memory concepts. Explore how pointers interact with structured data, discover efficient ways to organize information, and build confidence by implementing real data structures such as linked lists.

Build confidence by implementing a linked list from scratch, explore its structure, and create essential functions for adding, traversing, and managing list elements.

Adding Elements

Implementing Node Insertion

解答