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:

c3RydWN0IE5vZGUgewogICAgaW50IGRhdGE7ICAgICAgICAgICAvLyBkYXRhIGluIG5vZGUKICAgIHN0cnVjdCBOb2RlKiBuZXh0OyAgLy8gcG9pbnRlciB0byBuZXh0IG5vZGUKfTs=

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

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.

Explore the fundamentals of structs, understand why they are used, and build confidence in defining, creating, and accessing structured data.

Discover how pointers interact with structs, learn why this connection matters, and master key techniques such as dynamic allocation and passing structs to functions

Gain a solid understanding of how structs are stored in memory, explore alignment and padding, and learn how unions help manage shared data efficiently.

Dive into advanced struct patterns, including nested and anonymous structs, explore practical ways to combine them with arrays, and get familiar with common data structures.

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

Basic Concept and Structure

Solution

Basic Concept and Structure

Solution