Step 1 of 6

A node that points to a node

This module puts structs, pointers and malloc together to build the first real data structure. Arrays store elements side by side, which makes them fast to index but hard to grow or insert into. A linked list takes the opposite approach: each element (a node) is separate, and each node holds a pointer to the next one.

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

• value is the data.
• next points at the following node, or is NULL for the last node.
• The whole list is reached through one pointer to the first node, called the head. An empty list is just head == NULL.

A struct can't contain itself (that would be infinitely big), but it can contain a pointer to its own type, because a pointer is a fixed size.

Walking a list

You can't jump to "element 5" of a list. You start at the head and follow next pointers until you reach NULL:

#include <stdio.h>
#include <stddef.h>

struct Node {
    const char *name;
    struct Node *next;
};

int main(void) {
    struct Node third = {"cherry", NULL};
    struct Node second = {"banana", &third};
    struct Node first = {"apple", &second};
    int count = 0;
    for (struct Node *p = &first; p != NULL; p = p->next) {
        printf("%s\n", p->name);
        count++;
    }
    printf("%d nodes\n", count);
    return 0;
}

apple
banana
cherry
3 nodes

The for loop is the standard list traversal: start at the head, stop at NULL, and step with p = p->next. You'll write it many times.

In real programs nodes are allocated with malloc (next step); here they're plain local variables to keep the first example simple.

Your turn: link three stack-allocated nodes together and walk the list.

Next: Push to the front