Linked Lists

A linked list is a chain of dynamically-allocated nodes, each holding a value and a pointer to the next node — unlike an array, it can grow one node at a time without needing one large contiguous block of memory up front.

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

Node *createNode(int value) {
    Node *node = malloc(sizeof(Node));
    node->value = value;
    node->next = NULL;
    return node;
}

void printList(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d -> ", cur->value);
    }
    printf("NULL\n");
}

int main(void) {
    Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    printList(head); // 1 -> 2 -> 3 -> NULL

    // free every node before exiting
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
    return 0;
}

A struct referencing its own type by pointer (struct Node *next) is exactly what makes this self-referential shape possible — it couldn't hold a whole struct Node by value, since that would need infinite space, but a pointer to one is just a fixed-size address.

Common mistakes

• Freeing a node and then still using cur->next on it afterward — save next before freeing the current node, exactly as shown above.