Linked Lists: Nodes and Pointers (CS50 — Core Data Structures)

You already mastered low-level memory and pointer mechanics in the previous section. Now we’re going to take those pointers out for a walk and teach them to hold hands.

Hook: Why learn linked lists after pointers?

Arrays are great when you know the size ahead of time. Pointers taught you how memory looks and how to walk it. Linked lists are the natural next step: they let you build flexible sequences by chaining dynamically allocated nodes together — no resizing, no wasted buffer flushing, and (usually) no painful copy operations.

Think of a linked list like a conga line: each dancer (node) holds a hand (pointer) to the next dancer. If someone leaves, you just reconnect the hands; you don't have to move the whole line.

"This is the moment where the concept finally clicks."

What is a node? What is a pointer here?

• Node: a small struct that stores data and a pointer to the next node.
• Pointer: stores the memory address of another node. You used pointers before for variables and buffers — now the pointer points to nodes.

Simple node in C

// A singly linked list node for integer values
typedef struct node
{
    int value;         // payload
    struct node *next; // pointer to the next node
} node;

Micro explanation: struct node *next; is a pointer-to-struct — it stores the address of another node. That address is typically obtained with malloc, so you are directly tying dynamic memory allocation (from earlier lessons) to data structure construction.

Basic operations (with code and intuition)

We'll show common operations for singly linked lists: create, insert at head, insert at tail, search, and delete.

Create and insert at head (fast, O(1))

node *insert_front(node *head, int val)
{
    node *n = malloc(sizeof(node));
    if (n == NULL) return head; // malloc failed
    n->value = val;
    n->next = head; // point to old head
    return n;       // new head
}

Why this works: we allocate memory, set next to the current head, and return the new node as the new head. No traversal needed.

Insert at tail (O(n) unless you keep a tail pointer)

node *insert_tail(node *head, int val)
{
    node *n = malloc(sizeof(node));
    if (n == NULL) return head;
    n->value = val;
    n->next = NULL;
    if (head == NULL) return n; // list was empty

    node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
    return head;
}

Note: you can make tail insertion O(1) by keeping a separate tail pointer.

Search (O(n))

node *find(node *head, int val)
{
    node *cur = head;
    while (cur != NULL)
    {
        if (cur->value == val) return cur;
        cur = cur->next;
    }
    return NULL; // not found
}

Delete a value (careful with head)

Two main approaches:

1. Handle the head as a special case. 2. Use a pointer-to-pointer to avoid special-casing the head.

Pointer-to-pointer approach (slick):

node *delete_val(node *head, int val)
{
    node **cur = &head; // pointer to pointer to current node
    while (*cur != NULL)
    {
        if ((*cur)->value == val)
        {
            node *tmp = *cur;
            *cur = (*cur)->next; // bypass tmp
            free(tmp);
            break;
        }
        cur = &(*cur)->next;
    }
    return head;
}

Why pointer-to-pointer? cur always points to the pointer that leads to the current node (either head or some prev->next). This removes the need for special-case code when deleting the first node.

Diagrams (ASCII)

Head -> [value:5 | next:0xabc] -> [value:3 | next:0xdef] -> [value:9 | next:NULL]

Visually:

[head] -> [5] -> [3] -> [9] -> NULL

Each arrow is a pointer (an address) — remember from previous lessons that the pointer itself is stored as bytes in memory; endianness affects their byte ordering but not how you use them in C.

Common pitfalls (learned the hard way)

• Forgetting to set next = NULL for the last node. Result: garbage pointer -> crash.
• Memory leaks: every malloc must eventually be freed. If you free a node but still have pointers to it, you get dangling pointers.
• Double free: freeing the same block twice => undefined behavior.
• Using freed memory: undefined behavior (crashes, silent corruption).
• Shallow copy vs deep copy: copying a pointer copies the address, not the data it points to.
• Not checking malloc return value — handle allocation failure.

Tip: make a free_list(node *head) function that walks and frees every node.

When to use linked lists vs arrays

Real-world uses: implementing stacks, queues, adjacency lists for graphs, or when you need cheap splicing of sublists.

Small note on safety and debugging

• Use tools: Valgrind (or sanitizers) to find leaks and invalid accesses.
• Print pointer addresses when learning — it helps you visualize the chain.
• Remember earlier lessons: endianness affects how pointer bytes are laid out in memory dumps; buffers and flushing matter only if you persist structures to disk (serializing pointers directly is meaningless across runs).

Quick exercises (practice wins)

1. Implement free_list to free every node.
2. Write reverse_list iteratively and recursively.
3. Implement a function that merges two sorted linked lists into one sorted list (in-place).
4. Serialize a linked list to a file (values only), then reload it into memory — note why you can't serialize raw pointers.

Key takeaways

• A node is a payload + a pointer to the next node. Pointers are the glue.
• Insert at head is O(1); insert at tail is O(n) unless you keep a tail pointer.
• Be relentless about malloc checks and freeing memory.
• Pointer-to-pointer patterns simplify operations that change the head.

Final memory-packed thought: linked lists are less about fancy algorithms and more about mastering safe pointer choreography. If pointers were musical instruments, linked lists are the first band you form — you'll make mistakes, but by the time you can play a set without crashing, you'll be ready for the orchestra.

Tags: beginner, code, pointers