Loading...

C essentialsData Structures

Data structures: linked lists

18 min lesson

Next
  • A linked list is a chain of nodes, where each node holds a value and a pointer to the next node, so the elements do not need to sit next to each other in memory.
  • Linked lists matter because they can grow and shrink easily and let you insert or remove items without shifting a whole array.
  • Think of a linked list as a treasure hunt: each clue has a piece of treasure and the address of the next clue. You follow the chain from the first clue to the last.
  • A node is a small struct with a value and a next pointer, like struct Node { int value; struct Node *next; }.
  • The head is a pointer to the first node; if the head is NULL, the list is empty.
  • Traversal means walking the list from the head to the end, following each next pointer until you reach NULL.
  • The computer stores each node separately on the heap, and the next pointers tie them into a chain, so inserting a node only changes a couple of pointers.
  • The syntax for a node struct is: struct Node { int value; struct Node *next; }; and to create one: struct Node *n = malloc(sizeof *n);.
  • A realistic use: an undo history, a playlist that grows and shrinks, or a queue of tasks that arrive one at a time.
  • A surprising detail: finding the nth item takes time proportional to n, because you must walk from the head; arrays can jump straight to an index.
  • The example program builds a small list by adding nodes at the front, prints it, sums its values, and frees every node to avoid leaks.
Keep in mind
  • Always keep a pointer to the head; without it you lose the whole list.
  • Free every node when you are done, or you leak memory.
  • Remember that inserting at the front is fast, but searching is slow.
  • Draw the pointers on paper when learning; it makes the logic clear.
  • Linked lists are the gateway to real data structures. Great work!
main.c
#include <stdio.h>
#include <stdlib.h>

// A node holds an int value and a pointer to the next node
struct Node {
    int value;
    struct Node *next;
};

// Add a new node at the front of the list
struct Node *pushFront(struct Node *head, int value) {
    // Allocate a new node on the heap
    struct Node *node = malloc(sizeof *node);
    // Stop if allocation failed
    if (node == NULL) {
        return head;
    }
    // Set the value and link the node to the current head
    node->value = value;
    node->next = head;
    // The new node becomes the new head
    return node;
}

int main(void) {
    // Start with an empty list
    struct Node *head = NULL;
    // Push three values; each becomes the new front
    head = pushFront(head, 10);
    head = pushFront(head, 20);
    head = pushFront(head, 30);

    // Walk the list and sum the values
    int total = 0;
    for (struct Node *cur = head; cur != NULL; cur = cur->next) {
        printf("Node: %d\n", cur->value);
        total += cur->value;
    }
    printf("Total: %d\n", total);

    // Free every node to avoid leaks
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }

    return 0;
}

What happens: Node: 30 Node: 20 Node: 10 Total: 60

Breaking it down

Node struct

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

Defines the shape of one link: a value and a pointer to the next node. The pointer is the chain.

Empty list

struct Node *head = NULL;

An empty list is just a NULL head. Every traversal checks for NULL to know when to stop.

pushFront

node->next = head; return node;

Creates a node, points it at the current head, and returns it as the new head. This makes insertion at the front very fast.

Traversal

for (cur = head; cur != NULL; cur = cur->next)

Visits each node by following next pointers until NULL. This is the standard way to walk a list.

Freeing

free(cur); cur = next;

Saves the next pointer before freeing the current node, so the chain is not lost. This prevents leaks.

Array vs linked list

OperationArrayLinked list
Access by indexFast, O(1)Slow, O(n)
Insert at frontSlow, shift allFast, O(1)
Insert in middleSlow, shiftFast if you have the node
Memory layoutContiguousScattered nodes
ResizeFixed or copyGrows node by node

A helpful analogy

A linked list is like a treasure hunt. Each clue has a piece of treasure (the value) and the address of the next clue (the next pointer). You start at the first clue (the head) and follow the chain until the last clue, which points to nowhere (NULL).

Nesting rules

  • 1.Every node must have its next pointer set before it becomes part of the list.
  • 2.Always stop traversal at NULL; dereferencing NULL crashes the program.
  • 3.When freeing, save the next pointer before calling free on the current node.
  • 4.Keep a single head pointer; without it the whole list is unreachable.

Common mistakes

Losing the next pointer before free

Avoid

free(cur); cur = cur->next; // use after free

Use instead

struct Node *next = cur->next; free(cur); cur = next;

After free, cur->next is invalid. Save the next pointer first, then free.

Forgetting to link the new node

Avoid

node->value = 5; // next uninitialized

Use instead

node->value = 5; node->next = head;

An unlinked node is not part of the list, and its next pointer is garbage. Always set next.

Not checking malloc for NULL

Avoid

struct Node *n = malloc(sizeof *n); n->value = 1; // crash if NULL

Use instead

if (n == NULL) { /* handle */ }

malloc returns NULL on failure. Dereferencing NULL crashes. Check before using the node.

Quick tips

  • •Draw the list on paper before writing insert or delete code.
  • •Write a helper to print the list and use it after each change.
  • •Free the whole list at the end of every test to keep Valgrind clean.
  • •Try adding a value in the middle and see how the pointers change.
  • •Use a tail pointer if you need fast appends; it is a common next step.
Previous
Next