Pointers and dynamic memory

Learning outcomes

Read pointer expressions, allocate a node safely, and explain ownership, lifetime and cleanup.

7.1 Addresses and indirection

A pointer stores an address used to access an object or function. With int x = 7; int *p = &x;, p points to x and *p accesses x. The expression *p = 9 changes x. Declaring a pointer does not create the object it should point to.

A null pointer indicates the absence of a target; do not dereference it. A dangling pointer refers to an object whose lifetime has ended. A pointer may also be non-null and still invalid. A null check alone does not prove validity.

7.2 Arrays and pointer arithmetic

For an array a, the expression a[i] is equivalent to *(a + i). Pointer arithmetic advances by elements of the pointed-to type, not raw bytes. A pointer one past the end may be formed for comparison or iteration, but must not be dereferenced. Arithmetic and relational comparisons must respect the C rules for the underlying array object.

int a[3] = {10, 20, 30};
int *p = a;
/* *(p + 1) is 20. */

int *rows[3] is an array of three pointers. int (*p)[3] is a pointer to an array of three integers. Parentheses change the declaration. The first form alone does not allocate any row data.

7.3 Structures and nodes

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

A node stores one value and a link. node->value is shorthand for (*node).value. A structure cannot contain an ordinary instance of itself, which would require unbounded size, but it can contain a pointer to its own type.

7.4 Dynamic allocation

malloc allocates a requested number of bytes and returns a pointer, or a null pointer on failure. calloc also sets allocated bytes to zero. Do not generalise byte-zeroing to every possible pointer or floating representation; initialise fields according to their types. free ends the lifetime of a previously allocated block. Free each owned block once, and do not access it afterwards.

#include <stdlib.h>

struct Node *node = malloc(sizeof *node);
if (node == NULL) {
    /* Report allocation failure; leave the structure unchanged. */
} else {
    node->value = 25;
    node->next = NULL;
    /* Transfer ownership to a list, or free(node) when finished. */
}

In C, no cast is needed for the result of malloc. Include <stdlib.h> so the compiler has its declaration. sizeof *node follows the pointed-to type automatically. When allocating n elements, check that n * sizeof *p will not overflow size_t before calling the allocator.

If using realloc with a nonzero new size, assign its result to a temporary pointer. On failure the original allocation remains valid; assigning directly to the only owning pointer can lose the address and leak the block.

7.5 Ownership and failure paths

A list's head owns the chain in these examples. A search result is a borrowed pointer: it may observe a node but does not own an additional allocation. Removing the node invalidates that borrowed pointer.

To delete the first node: save its address, move head to the next node, then free the saved node. Reversing the last two actions would read a freed object. For complete cleanup, repeat until head is null. Setting one pointer to null after free does not repair other aliases to the same freed object.

A sound allocation policy is transactional at the operation level: allocate first; only after success link the new object into the structure. If allocation fails, return an error without changing the existing links.

Practice

1. Explain the difference between a null pointer and a dangling pointer.
2. Why is sizeof p normally wrong when allocating storage for an object of the type pointed to by p?
3. Trace the safe deletion of the head of a two-node list.
4. Explain why calling free on the same block twice is invalid even if two pointer variables hold its address.

/* C11. singly linked list, owned by head. */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *next; } Node;
static bool prepend(Node **head, int value)
{
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false; /* Leave the existing list unchanged. */
    node->value = value; node->next = *head; *head = node;
    return true;
}
/* Remove the first matching value; pointer-to-pointer also handles the head. */
static bool remove_first(Node **head, int value)
{
    Node **link = head;
    while (*link != NULL && (*link)->value != value) link = &(*link)->next;
    if (*link == NULL) return false;
    Node *victim = *link;
    *link = victim->next;
    free(victim);
    return true;
}
static const Node *find(const Node *head, int value)
{
    while (head != NULL && head->value != value) head = head->next;
    return head;
}
static void clear(Node **head)
{
    while (*head != NULL) {
        Node *next = (*head)->next;
        free(*head); *head = next;
    }
}
int main(void)
{
    Node *head = NULL;
    assert(!remove_first(&head, 10)); assert(find(head, 10) == NULL);
    for (int i = 4; i >= 1; --i) {
        if (!prepend(&head, i * 10)) { clear(&head); return EXIT_FAILURE; }
    }
    assert(find(head, 30) != NULL);
    assert(remove_first(&head, 10)); /* head */
    assert(remove_first(&head, 30)); /* middle */
    assert(!remove_first(&head, 99));
    printf("List:");
    for (const Node *p = head; p != NULL; p = p->next) printf(" %d", p->value);
    putchar('\n');
    assert(remove_first(&head, 40)); /* tail */
    assert(remove_first(&head, 20)); /* sole node */
    assert(head == NULL);
    assert(prepend(&head, 5)); assert(prepend(&head, 5));
    assert(remove_first(&head, 5) && head != NULL && head->value == 5);
    clear(&head); clear(&head); assert(head == NULL);
    puts("linked-list tests passed");
    return EXIT_SUCCESS;
}