Linked List

What is a linked list?

An array keeps its items packed together in memory with a fixed size. A linked list takes a different approach: it stores items in separate little blocks called nodes, and connects them using pointers. Each node points to the next one, forming a chain.

The big advantage is flexibility — a linked list can grow and shrink one node at a time while the program runs, without deciding a size in advance.

The node: the building block

A node is a struct with two parts: the data, and a pointer to the next node.

struct Node {
    int data;            // the value
    struct Node *next;   // address of the next node
};

The next pointer is what links one node to another. In the last node, next is set to NULL to say "the list ends here."

Building a small list

Let's create three nodes with malloc and link them: 10 → 20 → 30.

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };

int main() {
    struct Node *head = malloc(sizeof(struct Node));
    struct Node *second = malloc(sizeof(struct Node));
    struct Node *third = malloc(sizeof(struct Node));

    head->data = 10;   head->next = second;
    second->data = 20; second->next = third;
    third->data = 30;  third->next = NULL;   // end
    return 0;
}

Now head starts a chain: 10 points to 20, 20 points to 30, and 30 points to NULL.

Traversing to print

To read a linked list you start at head and follow next until you hit NULL.

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

Inserting at the end

To add a node at the end, walk to the last node and point its next at the new node.

void append(struct Node *head, int value) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = value;
    n->next = NULL;

    struct Node *temp = head;
    while (temp->next != NULL)   // find the last node
        temp = temp->next;
    temp->next = n;             // link it on
}

This walks to the node whose next is NULL, then attaches the new node there.

Linked list vs array

Common mistakes

• Forgetting to set the last node's next to NULL, so traversal never stops.
• Walking the list with head itself and losing the start.
• Not checking malloc for NULL before using a new node.
• Forgetting to free nodes, causing memory leaks.

Summary

• A linked list is a chain of nodes, each holding data and a next pointer.
• The last node's next is NULL to mark the end.
• Nodes are created with malloc so the list grows at run time.
• Traverse by following next from head until NULL.
• Lists beat arrays for flexible size and cheap inserts, but lack instant index access.