Linked List Node: Self-Referential Structs

What is a Linked List?

Before we dive into the code, let's establish a clear mental model. An array stores its elements one after the other in a single, continuous block of memory. A linked list, by contrast, is a chain of individual elements scattered anywhere in memory. Each element, called a node, holds two pieces of information: the actual data it's storing, and a "link"—a pointer—to the next node in the chain.

The video below provides an excellent conceptual overview of this structure, contrasting it with arrays and introducing the key terminology.

To visualize this, consider the following diagram. It shows a list containing the numbers 15, 3, 17, and 90.

As you can see, the list is defined by a single pointer, the Head, which simply points to the first node. From there, you can traverse the entire list by following the next pointer from one node to the next until you reach a NULL pointer, which signals the end.

The Self-Referential Struct: A Node's Blueprint

How do we represent a node in C? A node needs to contain its data and a pointer to another node of the same type. This circular-sounding definition is elegantly handled by a self-referential struct. This is a struct that includes a member that is a pointer to itself.

Let's look at the formal definition.

Now, let's apply this concept to build a node for our game. In a game development context, you might use a linked list to manage enemies, projectiles, or inventory items. The following reading provides a practical, game-oriented example of a node's design.

As the article demonstrates, the standard C pattern for a linked list node looks like this. We'll adapt it for our inventory system, where the data part of the node will be a struct Item.

// Forward declaration of the Item struct, assuming it's defined elsewhere.
struct Item; 

typedef struct node {
    struct Item data;        // The data payload (e.g., a sword, a potion).
    struct node *next;       // A pointer to the next node in the list.
} node_t;

Let's break this down:

1. typedef struct node { ... } node_t;: This defines a struct named node and creates a convenient alias node_t for it.
2. struct Item data;: This is the data payload. For our game, each node will hold one inventory item.
3. struct node *next;: This is the self-referential part. It's a pointer named next that can hold the memory address of another struct node. Inside the struct definition itself, we must use the full struct node name, as the typedef alias node_t is not yet fully defined at this point.

The concept is also clearly explained in the following academic resource.

A Concrete Example: Manually Building a Small List

With the node_t type defined, we can now allocate memory for some nodes and manually link them together to solidify our understanding. This involves using malloc (which you'll remember from the previous module) to create nodes on the heap and then setting their next pointers to form a chain.

The video below demonstrates this exact process.

Here is how we could apply this to create a two-item inventory list:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// A simple Item struct for our game inventory
typedef struct {
    int id;
    const char* name;
} Item;

// Our self-referential node structure
typedef struct node {
    Item data;
    struct node *next;
} node_t;

int main(void) {
    // 'head' will always point to the first node in our list.
    // An empty list is represented by a NULL head pointer.
    node_t *head = NULL;

    // --- Create the first node (a "Sword") ---
    node_t *node1 = malloc(sizeof(node_t));
    if (node1 == NULL) { return 1; } // Allocation failed
    
    node1->data.id = 101;
    node1->data.name = "Steel Sword";
    node1->next = NULL; // It's the only item, so it's also the last.

    // The list now contains one item. Update head.
    head = node1;

    // --- Create the second node (a "Shield") ---
    node_t *node2 = malloc(sizeof(node_t));
    if (node2 == NULL) { free(node1); return 1; } // Allocation failed

    node2->data.id = 205;
    node2->data.name = "Iron Shield";
    node2->next = NULL;

    // --- Link the first node to the second node ---
    head->next = node2; // The list is now: Sword -> Shield -> NULL

    // We can traverse the list starting from the head
    printf("Item 1: %s\n", head->data.name);
    printf("Item 2: %s\n", head->next->data.name);

    // Clean up memory
    free(head->next); // Free node2
    free(head);       // Free node1

    return 0;
}

This manual process demonstrates exactly how the pointers connect individual nodes into a coherent list. In practice, we will write functions to handle these operations automatically.

Conclusion

In this lesson, you've taken the first critical step into the world of linked lists. You've moved from the contiguous world of arrays to the flexible, non-contiguous world of pointer-linked nodes. This new structure offers different performance trade-offs that are vital to understand as a programmer.

Key Takeaways:

• A linked list is a data structure where elements (nodes) are connected in a sequence using pointers.
• The core component is the node, which contains both data and a link (a pointer) to the next node.
• In C, a node is implemented using a self-referential struct: a struct that contains a pointer member to its own type.
• The standard declaration pattern is typedef struct node { ... data; struct node *next; } node_t;.
• A pointer to the first node, called the head, is all that's needed to access the entire list. The end of the list is marked by a NULL pointer.

Now that we have the blueprint for a single node, our next task is to build the machinery to manage an entire list. In the next lesson, we will write functions to perform the most fundamental list operation: inserting new nodes into the list, starting with how to add a new node to the head.