Linked Lists

Linked Lists

A linked list is a dynamic data structure where each element (node) points to the next. Unlike arrays, linked lists can grow and shrink without reallocation.

Node Structure

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

Each node holds a value and a pointer to the next node. The last node points to NULL.

The chain of command: each officer points to the next in line, from Captain down to Ensign. The last one points to NULL -- no one left to delegate to.

Creating Nodes

struct Node *new_node(int data) {
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    n->data = data;
    n->next = NULL;
    return n;
}

Building a List

struct Node *head = new_node(10);
head->next = new_node(20);
head->next->next = new_node(30);
// List: 10 -> 20 -> 30 -> NULL

Traversing a List

struct Node *curr = head;
while (curr != NULL) {
    printf("%d\n", curr->data);
    curr = curr->next;
}

Prepending (Adding to Front)

struct Node *prepend(struct Node *head, int data) {
    struct Node *n = new_node(data);
    n->next = head;
    return n;  // new head
}

Your Task

Implement struct Node *prepend(struct Node *head, int data) that adds a new node to the front of the list, and void print_list(struct Node *head) that prints each value on its own line. Build a list by prepending 3, 2, 1 (in that order) and print it.