I feel like I keep harping on my time as a Computer Engineering student, but I think it is important to keep reiterating the fact that we truly only narrow in on certain languages and lines of thinking, and then we just stop. For ECE students, that means learning a few basic C++ principles, a bit of ARM/MIPS Assembly, and then a little sprinkle of C whenever we take Operating Systems.
The class that stuck with me the most was not Data Structures, intro to C++, or any of that. Instead, it was Operating Systems. Never before had I really delved deep into systems programming, kernel development, or anything of the sort. However, my professor for this class, Dr. Hartmut Kaiser, was extremely skillful in taking the tiny bit of C++ we learned as ECEs and slowly introducing us to the wild-west of C systems programming and kernel development. He still goes down as THE BEST professor I have had the pleasure of learning under to this day, and it really does go to show just how influential a single class/professor can be on a student’s development.
But that was over a year ago, and since then I have really only been messing with .NET code for my internship and a fair bit of PHP for FFLHub. Throughout all this time, I always wanted to revisit the principles and ideas that I learned in that class. Therefore, I have decided to settle on a simple challenge for myself:
Relearn C by implementing one data structure from scratch every day.
No libraries.
No header helpers.
No hiding memory behavior behind abstractions.
Just raw C, deliberate design, and intentional tradeoffs.
Today is Day 1, and we’re starting with something classic but deceptively deep:
A tailless singly linked list.
Why Start With a Tailless Linked List?
Because it forces you to think about:
- Pointer mutation
- Memory ownership
- Traversal cost
- Edge cases (empty list, single node list)
- Allocation failure handling
- Free order correctness
And importantly — it’s incomplete in ways that matter.
We are not using:
- Tail pointer
- Size tracking
- Container wrapper struct
And that’s intentional. Because in later posts, we’ll add those and see exactly just how those things aid us in complexity times and such. But first, a few ground rules and general design principles…
Memory Model — Caller Owned
This implementation uses a caller-owned memory model.
That means:
The list:
- Does NOT automatically allocate nodes
- Does NOT automatically free nodes
- Does NOT manage payload lifetime beyond copying it into the node
The caller:
- Allocates nodes
- Inserts nodes
- Removes nodes
- Destroys nodes
Why?
Because this is extremely common in systems programming. It gives maximum flexibility and makes ownership boundaries explicit.
Node Structure:
Each node stores:
- Pointer to payload
- Size of payload
- Pointer to next node
This allows the list to store heterogeneous data — not just one fixed type.
//For this linked list, I am using a caller owned approach, aka, all memeory is allocated and freed by the caller, not the list or list node itself
struct Node {
void* data;
size_t data_size;
struct Node* next;
};Allocation and Freeing Strategy:
Allocation happens in two steps:
- Allocate node struct
- Allocate payload buffer
If payload allocation fails, we roll back and free the node.
This avoids partial allocations and leaks.
I also implemented a function that allows us to allocate and populate a node with data:
//this is how we allocate the memory for nodes
struct Node* alloc_node(size_t data_size) {
//first, we allocate the memory required for the base data size of each node
struct Node* node = malloc(sizeof *node);
if (!node) return NULL; //if malloc fails, return NULL
//second, we allocate the memory for the data stored inside our node using our data size passed in
node->data = malloc(data_size);
//if that malloc fails, we free the previous base allocation and return null
if (!node->data) {
free(node);
return NULL;
}
//set the data size member
node->data_size = data_size;
//make sure the next pointer is nll
node->next = NULL;
//return the allocation pointer
return node;
}
//we simply allocate the node using our function above, then we memcpy the data into the node
struct Node* create_node_from_data(void* data, size_t data_size) {
struct Node* node = alloc_node(data_size);
if (!node) return NULL;
memcpy(node->data, data, data_size);
return node;
}And for freeing, we free in reverse allocation order:
//we free a singular node
void free_node(struct Node* node) {
if (!node) return; //if node is invalid, return
//we only want to free the data portion of our node if the data is valid, IE its been allocated properly
if (node->data) {
free(node->data);
node->data = NULL;
}
//only after this we free the memeory allocated for the base node size
//we deallocate in REVERSE order of allocation
free(node);
}Using these functions, we can create general Linked List helper functions that free and destroy the entire list:
//free the linked list using our free node function, we step through the linked list
//we save the next ptr, then free that node, then we use that next ptr to iterate to the next node
void free_list(struct Node* head) {
while (head) {
struct Node* next = head->next;
free_node(head);
head = next;
}
}
//uses the method above then also sets the base pointer to null to avoid a dangling pointer
void list_destroy(struct Node** head) {
if (!head || !*head) return;
free_list(*head);
*head = NULL;
}
Core Operations Implemented
I also wrote some functions to handle the most basic of operations that you would want to perform on a linked list:
Insertion
push_front— add a node to the front of the linked listpush_back— add a node to the back of the linked list
Removal
pop_front— remove a node from the front of the linked listpop_back— remove a node from the back of the linked list
Access
front— grab the head of the linked listback— grab the tail of the linked list
void push_front(struct Node* new_head, struct Node** head) {
//if our new head is invalid, or if our current head pointer is invalid, early exit
if (new_head == NULL || head == NULL) return;
new_head->next = *head; //the new heads next pointer must point to the old head
*head = new_head; //now we set the head equal to our new head that we want
}
void pop_front(struct Node** head) {
if (head == NULL || *head == NULL) return; //if list is empty or if the head pointer is NULL, early exit
struct Node* new_head = (*head)->next; //we store the new head ptr, which is the node that occurs after the current head
free_node(*head); //free the old head node, deallocate its memeory
*head = new_head; //set the head pointer equal to the new head we want, aka the next node in the list
}
void push_back(struct Node* new_tail, struct Node** head) {
if (head == NULL || new_tail == NULL) return; //invalid head or tail node, retunrn early
//
////if list is empty, then the head is just the node we are appending
if (*head == NULL) {
*head = new_tail;
new_tail->next = NULL;
return;
}
//otherwise, we have to iterate through the entire loop
struct Node* cur = (*head);
//we need to keep iterating until we reach the end, IE the next pointer is NULL
while (cur->next != NULL) cur = cur->next;
//once we are at the end, set the next pointer to point to our new tail node
cur->next = new_tail;
new_tail->next = NULL;
}
void pop_back(struct Node** head) {
if (head == NULL) return; //invalid header pointer, return early
if (*head == NULL) return; //list is empty, nothing to pop
//if we have a one node list, we need to handle that situation since our while loop iterator checks TWO nodes ahead, not one like the above function
if ((*head)->next == NULL) {
free_node(*head);
*head = NULL;
return;
}
//same iteration as the function above, except we check TWO nodes ahead
struct Node* prev = (*head);
while (prev->next->next != NULL) prev = prev->next;
//okay so now that we are at the end of the node, we have to free the node
free_node(prev->next);
prev->next = NULL;
}
struct Node* front(struct Node* head) {
if (head == NULL) return NULL; //invalid head pointer, return NULL, or if the list is empty, return null
return head; //so yeah even if *head is NULL itll still return NULL here, but whateever its extra safe I guess
}
struct Node* back(struct Node* head) {
if (head == NULL) return NULL; //invalid head pointer, return NULL
if (head->next == NULL) return head; //we are already at the endm return head - like before, this is redudant, but oh well maybe the compiler will make something useful out of this
//now we iterate through the entire list until we reach the end
struct Node* cur = head;
while (cur->next != NULL) cur = cur->next;
return cur;
}Now, the astute among you probably see why I mentioned we are making a TAILLESS linked list. Because we don’t store the tail of our linked list, any function that has to do with mutating the end of the our linked list has to traverse the entire list first. This yields the following complexity charge for each function we implemented:
Complexity Table (Tailless List)
| Operation | Complexity |
|---|---|
| push_front | O(1) |
| pop_front | O(1) |
| front | O(1) |
| push_back | O(n) |
| pop_back | O(n) |
| back | O(n) |
We get a O(n) complexity for every tail associated function. In the next post, we will add a tail and see what this yields (hint: it makes for a super boring chart).
And to top everything off, I wrote a little test-bed that tests our functions:
int main(void) {
const int MAX_ITERS = 10000; // change this one value to scale all tests
struct Node* head = NULL;
printf("=== Linked List Stress Test (MAX_ITERS=%d) ===\n\n", MAX_ITERS);
// -------------------------
// TEST 1: push_front
// -------------------------
printf("TEST 1: push_front %d ints (0..%d)\n", MAX_ITERS, MAX_ITERS - 1);
for (int i = 0; i < MAX_ITERS; i++) {
int v = i;
struct Node* n = create_node_from_data(&v, sizeof v);
if (!n) {
printf("alloc failed in TEST 1 at i=%d\n", i);
list_destroy(&head);
return 1;
}
push_front(n, &head);
}
struct Node* f = front(head);
struct Node* b = back(head);
if (!f || !b) {
printf("FAIL: front/back returned NULL after push_front\n");
list_destroy(&head);
return 1;
}
int front_v = *(int*) f->data;
int back_v = *(int*) b->data;
printf("Check: front=%d (expected %d), back=%d (expected %d)\n",
front_v, MAX_ITERS - 1, back_v, 0);
if (front_v != MAX_ITERS - 1 || back_v != 0) {
printf("FAIL: unexpected front/back values in TEST 1\n");
list_destroy(&head);
return 1;
}
// Pop everything and ensure order is descending MAX_ITERS-1 .. 0
printf("Pop all with pop_front and verify descending order...\n");
for (int expected = MAX_ITERS - 1; expected >= 0; expected--) {
struct Node* cur = front(head);
if (!cur) {
printf("FAIL: list became empty early at expected=%d\n", expected);
list_destroy(&head);
return 1;
}
int cur_v = *(int*) cur->data;
if (cur_v != expected) {
printf("FAIL: pop_front order mismatch: got %d expected %d\n", cur_v, expected);
list_destroy(&head);
return 1;
}
pop_front(&head);
}
if (head != NULL) {
printf("FAIL: head not NULL after popping all nodes in TEST 1\n");
list_destroy(&head);
return 1;
}
printf("PASS: TEST 1\n\n");
// -------------------------
// TEST 2: push_back
// -------------------------
printf("TEST 2: push_back %d ints (0..%d)\n", MAX_ITERS, MAX_ITERS - 1);
for (int i = 0; i < MAX_ITERS; i++) {
int v = i;
struct Node* n = create_node_from_data(&v, sizeof v);
if (!n) {
printf("alloc failed in TEST 2 at i=%d\n", i);
list_destroy(&head);
return 1;
}
push_back(n, &head);
}
f = front(head);
b = back(head);
if (!f || !b) {
printf("FAIL: front/back returned NULL after push_back\n");
list_destroy(&head);
return 1;
}
front_v = *(int*) f->data;
back_v = *(int*) b->data;
printf("Check: front=%d (expected %d), back=%d (expected %d)\n",
front_v, 0, back_v, MAX_ITERS - 1);
if (front_v != 0 || back_v != MAX_ITERS - 1) {
printf("FAIL: unexpected front/back values in TEST 2\n");
list_destroy(&head);
return 1;
}
// Pop everything and ensure order is descending from the back: MAX_ITERS-1 .. 0
printf("Pop all with pop_back and verify descending-from-back order...\n");
for (int expected = MAX_ITERS - 1; expected >= 0; expected--) {
struct Node* cur = back(head);
if (!cur) {
printf("FAIL: list became empty early at expected=%d\n", expected);
list_destroy(&head);
return 1;
}
int cur_v = *(int*) cur->data;
if (cur_v != expected) {
printf("FAIL: pop_back order mismatch: got %d expected %d\n", cur_v, expected);
list_destroy(&head);
return 1;
}
pop_back(&head);
}
if (head != NULL) {
printf("FAIL: head not NULL after popping all nodes in TEST 2\n");
list_destroy(&head);
return 1;
}
printf("PASS: TEST 2\n\n");
// -------------------------
// TEST 3: mixed operations with exact expectations
// -------------------------
printf("TEST 3: mixed ops with exact expected front/back\n");
// Step A: build 0..MAX_ITERS-1 using push_back
for (int i = 0; i < MAX_ITERS; i++) {
int v = i;
struct Node* n = create_node_from_data(&v, sizeof v);
if (!n) {
printf("alloc failed in TEST 3A at i=%d\n", i);
list_destroy(&head);
return 1;
}
push_back(n, &head);
}
// Step B: pop_front K times (removes 0..K-1)
const int K = MAX_ITERS / 10; // 10% of max iterations
for (int expected = 0; expected < K; expected++) {
struct Node* cur = front(head);
if (!cur) {
printf("FAIL: empty early during TEST 3B at expected=%d\n", expected);
list_destroy(&head);
return 1;
}
int cur_v = *(int*) cur->data;
if (cur_v != expected) {
printf("FAIL: TEST 3B pop_front mismatch: got %d expected %d\n", cur_v, expected);
list_destroy(&head);
return 1;
}
pop_front(&head);
}
// After popping K from front, expected front is K, expected back is MAX_ITERS-1
f = front(head);
b = back(head);
if (!f || !b) {
printf("FAIL: front/back NULL after TEST 3B\n");
list_destroy(&head);
return 1;
}
if (*(int*) f->data != K || *(int*) b->data != MAX_ITERS - 1) {
printf("FAIL: after TEST 3B expected front=%d back=%d, got front=%d back=%d\n",
K, MAX_ITERS - 1, *(int*) f->data, *(int*) b->data);
list_destroy(&head);
return 1;
}
// Step C: push_front K values (100000..100000+K-1)
// Because push_front reverses order, final front should be 100000+K-1
for (int i = 0; i < K; i++) {
int v = 100000 + i;
struct Node* n = create_node_from_data(&v, sizeof v);
if (!n) {
printf("alloc failed in TEST 3C at i=%d\n", i);
list_destroy(&head);
return 1;
}
push_front(n, &head);
}
f = front(head);
b = back(head);
if (!f || !b) {
printf("FAIL: front/back NULL after TEST 3C\n");
list_destroy(&head);
return 1;
}
int expected_front = 100000 + (K - 1);
int expected_back = MAX_ITERS - 1;
if (*(int*) f->data != expected_front || *(int*) b->data != expected_back) {
printf("FAIL: after TEST 3C expected front=%d back=%d, got front=%d back=%d\n",
expected_front, expected_back, *(int*) f->data, *(int*) b->data);
list_destroy(&head);
return 1;
}
// Step D: pop_back K times (removes MAX_ITERS-1 down to MAX_ITERS-K)
for (int j = 0; j < K; j++) {
int expected = (MAX_ITERS - 1) - j;
struct Node* cur = back(head);
if (!cur) {
printf("FAIL: empty early during TEST 3D at expected=%d\n", expected);
list_destroy(&head);
return 1;
}
int cur_v = *(int*) cur->data;
if (cur_v != expected) {
printf("FAIL: TEST 3D pop_back mismatch: got %d expected %d\n", cur_v, expected);
list_destroy(&head);
return 1;
}
pop_back(&head);
}
// After popping K from back, expected back is MAX_ITERS-K-1
f = front(head);
b = back(head);
if (!f || !b) {
printf("FAIL: front/back NULL after TEST 3D\n");
list_destroy(&head);
return 1;
}
expected_front = 100000 + (K - 1);
expected_back = (MAX_ITERS - K - 1);
if (*(int*) f->data != expected_front || *(int*) b->data != expected_back) {
printf("FAIL: after TEST 3D expected front=%d back=%d, got front=%d back=%d\n",
expected_front, expected_back, *(int*) f->data, *(int*) b->data);
list_destroy(&head);
return 1;
}
// Cleanup
list_destroy(&head);
if (head != NULL) {
printf("FAIL: head not NULL after list_destroy at end\n");
return 1;
}
printf("PASS: TEST 3\n\n");
printf("ALL TESTS PASSED!\n");
return 0;
}Which yields the following result:
=== Linked List Stress Test (MAX_ITERS=10000) ===
TEST 1: push_front 10000 ints (0..9999)
Check: front=9999 (expected 9999), back=0 (expected 0)
Pop all with pop_front and verify descending order...
PASS: TEST 1
TEST 2: push_back 10000 ints (0..9999)
Check: front=0 (expected 0), back=9999 (expected 9999)
Pop all with pop_back and verify descending-from-back order...
PASS: TEST 2
TEST 3: mixed ops with exact expected front/back
PASS: TEST 3
ALL TESTS PASSED!Retrospect on this challenge:
Like I said before, I mainly deal with C#, web-code, etc. We rarely have to actually think about the memory we are allocating because all of that is handled behind the scenes for us whether it be through GC or other means (Rust uses a borrow checker that I want to mess with at some point).
C makes you honest.
It makes you think about:
- Where memory comes from
- Who owns memory
- When memory dies
- What pointer actually means
- How data really moves through systems
And honestly — it’s refreshing.
Closing
If you haven’t touched C in a while, I highly recommend doing something like this.
Pick a data structure.
Write it from scratch.
Test it hard.
Then improve it iteratively.
Tomorrow:
Another data structure.
More pointer pain.
More learning.
Leave a Reply