Linked lists

Nodes joined by pointers

• A linked list is a chain of small structs called nodes, scattered around the heap.
• Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
• Unlike an array, a list can grow one node at a time without moving the others.

A self-referential struct

• A node is a struct that contains a pointer to its own type:
• struct Node { int data; struct Node *next; }; — data is the value, next points to the following node.
• This is given for you as Node in each starter. The last node's next is NULL.

head and the NULL end

• A single pointer, the head, points to the first node. From there you reach the rest.
• The very last node points to NULL, which marks the end of the list.
• An empty list is just head == NULL — there are no nodes at all.

#include <stdio.h>

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

int main(void) {
    // A tiny list on the stack: 10 -> 20 -> 30 -> NULL
    Node n3 = {30, NULL};
    Node n2 = {20, &n3};
    Node n1 = {10, &n2};
    const Node *head = &n1;

    // Walk it: follow ->next until NULL, counting nodes
    int count = 0;
    const Node *cur = head;    // start at the head
    while (cur != NULL) {      // stop at the NULL end
        count++;
        cur = cur->next;       // step to the next node
    }
    printf("length = %d\n", count);   // length = 3
    return 0;
}

Adding a node at the front

• To add to the front, make a new node, point its next at the old head, and return the new node as the new head.
• This is fast — it does not touch any other node.
• Because the head changes, the function returns the new head, and the caller saves it.

Now you try

• Walk a list with a cur pointer and cur = cur->next, stopping at NULL.
• New nodes come from malloc(sizeof(Node)); the checker frees the list. Do not write a main.