---
title: 'Linked Structures'
source: 'https://academia.sh/en/courses/c-systems-programming/linked-structures'
course: 'Systems Programming with C'
language: en
updated: '2026-09-26T03:02:44+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - 'Implements a linked list and a binary search tree in C with insertion, traversal, and release operations'
    - 'Measures, without printing addresses, the node a pointer shares through an alias, using equality and value'
    - 'Shows the visibility difference between a shallow copy and a deep copy (shared/copy) on the same list'
---

# Linked Structures

A C implementation of a linked list and a binary search tree; measuring how changing a node through an alias and a shallow copy produce shared visibility, while a deep copy cuts it.

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.

```c
// 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
```

```c
// 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.

```c
// 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.

```c
// 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.

```c
// 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
```

```c
// 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);
}
```

```c
// 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.

```c
// 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.