Linked Structures

The previous lesson measured who releases a block of memory. This course starts with a different axis: who sees a change when you modify a node. When two different pointers hold the same block of memory, a change made through one is visible through the other — the source does not say so, because both variables have the identical declaration (struct Node *). The linked list is the clearest example of this sharing: the field that leads to the next node carries a pointer, and whoever holds that pointer sees the same node.

This lesson builds the linked list and the binary search tree from scratch and compares two of the four classes, shared and copy, on the same structure: accessing and changing a node through an alias produces shared visibility (shared); duplicating the entire list with new nodes cuts that sharing (copy). The previous course’s (Memory and Pointers in C) question of “who releases this node” still applies here — releasing the tree still honors that contract — but the axis this lesson measures is different: not ownership, visibility.

Linked List: Insertion, Traversal, Release

The list is singly linked, and every insertion happens at the head. list_total walks every node and sums their values; list_free saves the next node before releasing each one. list_shallow_copy does not allocate a new node — it returns the incoming head as is, so the list it returns shares the same nodes as the original. list_deep_copy instead allocates a new node for each one and copies its value; the list it returns owns an independent chain of memory blocks.

// node.h — singly linked list and basic operations
#ifndef NODE_H
#define NODE_H

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

struct Node *list_insert(struct Node *head, int value);
int list_total(const struct Node *head);
void list_free(struct Node *head);
struct Node *list_shallow_copy(struct Node *head);
struct Node *list_deep_copy(const struct Node *head);

#endif

// node.c — implementation of the list operations
#include <stdlib.h>
#include "node.h"

struct Node *list_insert(struct Node *head, int value) {
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return head;
    }
    node->value = value;
    node->next = head;
    return node;
}

int list_total(const struct Node *head) {
    int total = 0;
    for (const struct Node *n = head; n != NULL; n = n->next) {
        total += n->value;
    }
    return total;
}

void list_free(struct Node *head) {
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

struct Node *list_shallow_copy(struct Node *head) {
    return head;
}

struct Node *list_deep_copy(const struct Node *head) {
    struct Node *new_head = NULL;
    struct Node *tail = NULL;
    for (const struct Node *n = head; n != NULL; n = n->next) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) {
            list_free(new_head);
            return NULL;
        }
        node->value = n->value;
        node->next = NULL;
        if (tail == NULL) {
            new_head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return new_head;
}

A Node Changed Through an Alias

The list is built with the values 1, 2, 3. The pointer second points at the second node — not a new node, but one of the list’s own nodes. A change made through second is reflected in the list’s total, because both point at the same block of memory.

// alias.c — accessing the list's own node through a second pointer
#include <stdio.h>
#include "node.h"

int main(void) {
    struct Node *head = NULL;
    head = list_insert(head, 3);
    head = list_insert(head, 2);
    head = list_insert(head, 1);

    printf("%s %d\n", "total before changing through the alias", list_total(head));

    struct Node *second = head->next;
    second->value = 20;

    printf("%s %d\n", "total after changing through the alias", list_total(head));
    printf("%s %d\n", "is second the same node as head->next", (int)(second == head->next));

    list_free(head);
    return 0;
}

total before changing through the alias 6
total after changing through the alias 24
is second the same node as head->next 1

DS1. The second variable is of type struct Node *, and so is head — nothing in the source says anywhere whether second points at the list’s own node or an independent copy. What decides this is not the declaration but the assignment itself: second = head->next is not a copy of a value but a copy of a pointer, meaning second and head->next carry the same address. The line second->value = 20 therefore also changes the total read through head: from 6 to 24. The last line confirms this without printing an address — the comparison second == head->next gives 1, showing that the two pointers point at the same node. The class is shared: a second reader (here, the call to list_total through head) sees the change, because there is a single shared object between them, not two copied objects.

Shallow Copy, Deep Copy

list_shallow_copy does not allocate even a single node — it returns the head it receives as is. Because of this, the pointer it returns and the original list point at the same nodes, and a change made through one is visible through the other. list_deep_copy allocates a new node for each one; the list it returns carries the values as they were at the moment of copying, but afterward shares no node with the original.

// copy_comparison.c — shallow copy shares, deep copy cuts the sharing
#include <stdio.h>
#include "node.h"

int main(void) {
    struct Node *head = NULL;
    head = list_insert(head, 3);
    head = list_insert(head, 2);
    head = list_insert(head, 1);

    struct Node *shallow = list_shallow_copy(head);
    head->next->value = 200;
    printf("%s %d\n", "second value seen by the shallow copy", shallow->next->value);

    struct Node *deep = list_deep_copy(head);
    head->next->value = 2000;
    printf("%s %d\n", "second value seen by the deep copy", deep->next->value);

    list_free(deep);
    list_free(head);
    return 0;
}

second value seen by the shallow copy 200
second value seen by the deep copy 200

DS2. Both lines print the same number (200), but for different reasons, and that difference is what this lesson measures. On the first line, shallow points at the same nodes as head; the assignment head->next->value = 200 also changes shallow->next->value, because both look at a single object — the class is shared. On the second line, deep was built by allocating new nodes at the moment of copying (while the second node still carried the value 200); the assignment head->next->value = 2000, made after the copy, does not affect deep, because deep’s nodes are independent memory blocks from head’s. deep->next->value still carries the 200 from the moment of copying, not 2000 — the class is copy: the change never reaches a second reader, because there is no shared object between them. Because the pointer returned by list_shallow_copy is exactly identical to head, this lesson releases only deep and head separately; releasing shallow as well would release the same block twice.

Binary Search Tree: Insertion, Traversal, Release

The linked list’s single-next-pointer sharing extends to two pointers (left, right) in the binary tree, but the principle is the same: when a node is reached through more than one path, the source does not show which path was used. tree_insert is recursive, tree_total walks in order (inorder) and sums the values, tree_free releases the subtrees before releasing the root — the list’s “who releases it” contract still applies here; this lesson focuses not on that contract but on the tree’s visibility.

// tree.h — basic binary search tree operations
#ifndef TREE_H
#define TREE_H

struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *tree_insert(struct TreeNode *root, int value);
int tree_total(const struct TreeNode *root);
void tree_free(struct TreeNode *root);

#endif

// tree.c — insertion, inorder traversal, and release
#include <stdlib.h>
#include "tree.h"

struct TreeNode *tree_insert(struct TreeNode *root, int value) {
    if (root == NULL) {
        struct TreeNode *node = malloc(sizeof *node);
        if (node == NULL) {
            return NULL;
        }
        node->value = value;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (value < root->value) {
        root->left = tree_insert(root->left, value);
    } else {
        root->right = tree_insert(root->right, value);
    }
    return root;
}

int tree_total(const struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return tree_total(root->left) + root->value + tree_total(root->right);
}

void tree_free(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    tree_free(root->left);
    tree_free(root->right);
    free(root);
}

// tree_alias.c — accessing the tree's own node through a second pointer
#include <stdio.h>
#include "tree.h"

int main(void) {
    struct TreeNode *root = NULL;
    int values[] = {5, 3, 8, 1, 4};
    for (size_t i = 0; i < sizeof values / sizeof values[0]; i++) {
        root = tree_insert(root, values[i]);
    }
    printf("%s %d\n", "total of the tree's values before", tree_total(root));

    struct TreeNode *left_child = root->left;
    left_child->value = 30;
    printf("%s %d\n", "total after changing through left_child", tree_total(root));

    tree_free(root);
    return 0;
}

total of the tree's values before 21
total after changing through left_child 48

DS3. left_child points at the same node as root->left — it did not add a new branch to the tree; we reached an existing node through a second path (through its own variable instead of the root’s left field). The assignment left_child->value = 30 raises this node’s value from 3 to 30, and tree_total(root) sees it: from 21 to 48. The same principle as the second example in the linked list — the class is again shared. The contract we honor when releasing the tree (tree_free) is a separate question: who releases each node, the axis of the previous course (Memory and Pointers in C). This lesson does not reopen that question; it only measures whether a change is visible through a second pointer.

Partial Shallow Copy Through Struct Assignment

list_shallow_copy and list_deep_copy were two extreme examples: one copied nothing at all, the other copied every node. But C has a third, more insidious way of copying a struct: struct assignment (=). When you write struct Node copy = *head;, the compiler copies every field of the struct that head points at into a new variable — but if one of “every field” is itself a pointer, that pointer is also copied as a value, not the place it points at.

// struct_assignment.c — a partial shallow copy through variable-type assignment
#include <stdio.h>
#include "node.h"

int main(void) {
    struct Node *head = NULL;
    head = list_insert(head, 3);
    head = list_insert(head, 2);
    head = list_insert(head, 1);

    struct Node copy = *head;
    printf("%s %d\n", "copy's value field right after the assignment", copy.value);

    head->value = 100;
    printf("%s %d\n", "copy.value after head->value changes", copy.value);

    head->next->value = 200;
    printf("%s %d\n", "copy.next->value after changing through the second node", copy.next->value);

    list_free(head);
    return 0;
}

copy's value field right after the assignment 1
copy.value after head->value changes 1
copy.next->value after changing through the second node 200

DS14. The line struct Node copy = *head; does two different things, both inside the same assignment: the value field is an int, and the assignment copies it by value — this is why, after head->value = 100 runs, copy.value still holds its first value, 1. But the next field is a struct Node *, and the assignment copies it by value too — the value copied is an address, meaning copy.next and head->next carry the same address after the assignment. When head->next->value = 200 runs, this change is also visible through copy.next->value: 200. Within a single assignment line, the value field produces the copy class while the node that next points at produces the shared class at the same time — the difference between a “shallow copy” and a “deep copy” is sometimes not a matter of which function you chose, but of which fields of a struct carry pointers. list_shallow_copy’s returned pointer was shared in its entirety; here only the node that next points at is shared, the value field itself is not — two separate classes within the same struct assignment.

The Bounding Measurement

A pointer’s sharing is invisible in the source. When two list heads or two tree branches point at the same node, the type of the structure does not say so — the declaration struct Node * can point at either the list’s own node or an independent copy, and there is no distinction between them at the source level. In this lesson we compared pointers in both cases without printing an address: the equality second == head->next told us whether the two variables looked at the same block of memory or at different blocks. The difference between list_shallow_copy and list_deep_copy also shows up not in a signature in the source but in what their bodies do: one performs no allocation at all, the other allocates a new node for every node. It is not possible to tell whether a function shares by looking at its return type; this can only be understood by reading the body or by measuring.

Summary

• The linked list and the binary search tree were built on the same principle: more than one pointer can reach a node at the same time, and the source does not say so.
• Accessing and changing a node through an alias produced the shared class in both the list and the tree: a second reader (list_total, tree_total) saw the change.
• list_shallow_copy stayed shared because it returns the head without allocating a node; list_deep_copy produced the copy class because it allocates a new node for every node.
• A partial copy made through struct assignment (=) can produce the copy class in a struct’s scalar fields and the shared class in what its pointer fields point at, at the same time.
• Whether two pointers point at the same node can be measured only through equality (==), without printing an address.
• Who releases a struct (K02’s question) and who sees a change (this course’s question) are separate axes; this lesson measures the second one.

Next Step

In this lesson we always held a pointer to reach a node, and that pointer was permanent. The next lesson, Ring Buffers and Queues, looks at a structure where what is shared is not the pointer itself but a position (an index): a producer and a consumer use the same array, but one writes while the other reads, and a written value can be overwritten before it is read. The class there is not shared but handoff: the value reaches the reader exactly once, and can then disappear.