Summary  
This chapter describes the structure of a singly linked list in C, explaining how each node holds data and a pointer to the next node and why using pointers avoids self-referential memory allocation errors.

General domain of usage  
Data structure implementation

A **linked list** in C is a simple dynamic data structure consisting of elements called nodes.
Each node contains data (such as a variable or object) as well as a pointer to the next node in the list.


Here's what a typical node in a singly linked list looks like in C:

If instead of a pointer to the next node you try to simply create an instance of a new node, you will get an error.

The compiler will not be able to allocate memory for such a structure, since it contains itself. It's like trying to look at yourself from the outside with your own eyes

Using a pointer solves this problem because the compiler knows how much memory to allocate for a pointer variable.

The last node pointer will always be `NULL`.

Note

#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

The course covers the principles of creating and using structures, their memory and methods of data manipulation.

In this section you will learn what a structure is, why they exist and how to create them.

In this section we will review what pointers are, learn why pointers are used in structures and, most importantly, how this connection is implemented.

In this section, you'll learn how structures are stored in memory, see what alignment and padding are, and get acquainted with unions.

In this section you will learn about the features of nested structures, their application within other structures, get acquainted with anonymous structures and their application, and also superficially familiarize yourself with the most common data structures.

In this section you will implement a simple but very common data structure Linked List, and also create the necessary functions for working with the list.

Basic Concept and Structure

Lösung

Awesome!

Basic Concept and Structure

Lösung