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.

Common mistakes

Never lose the head pointer, or the whole list is unreachable.
Free every node; the last node points to NULL.

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.

Explore

Nodes and pointers

Each node points to the next; insert/delete by re-linking.

Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not write a main.

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

/* Count the nodes from head (0 for NULL). Do not write main(). */
int length(const Node *head) {
    return 0;   /* walk with ->next until NULL */
}

Click Run to see the output here.

Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not write a main.

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

/* Total every node's data (0 for NULL). Do not write main(). */
int sum_list(const Node *head) {
    return 0;   /* walk and add cur->data */
}

Click Run to see the output here.

Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not write a main.

#include <stdlib.h>

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

/* Make a new node holding value, link it before head, return it. Do not write main(). */
Node *push_front(Node *head, int value) {
    /* malloc a Node, set its data and next, return it */
    return head;
}

Click Run to see the output here.