The node
struct node {
int data;
struct node *next;
};The struct refers to itself through a pointer. That is legal because a pointer has a known size (8 bytes) even before the struct is fully defined. A member of type struct node next; would not compile - it would be infinitely large.
Creating one node
struct node *make_node(int value) {
struct node *n = malloc(sizeof(struct node));
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->data = value;
n->next = NULL;
return n;
}sizeof(struct node), not sizeof(struct node *). The second gives you 8 bytes for a 16-byte struct, and you get memory corruption that shows up somewhere completely unrelated.
malloc does not clear the memory it gives you. If you forget n->next = NULL, next holds whatever bytes were there before, your traversal follows a garbage address and the program segfaults. Always set every field immediately after malloc.
The complete program
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
static struct node *make_node(int value) {
struct node *n = malloc(sizeof(struct node));
if (n == NULL) { fprintf(stderr, "out of memory\n"); exit(1); }
n->data = value;
n->next = NULL;
return n;
}
/* O(1) */
static struct node *push_front(struct node *head, int value) {
struct node *n = make_node(value);
n->next = head;
return n;
}
/* O(n) */
static struct node *push_back(struct node *head, int value) {
struct node *n = make_node(value);
if (head == NULL) return n;
struct node *cur = head;
while (cur->next != NULL) cur = cur->next;
cur->next = n;
return head;
}
/* delete the first node holding value; returns the new head */
static struct node *delete_value(struct node *head, int value) {
struct node *cur = head, *prev = NULL;
while (cur != NULL && cur->data != value) {
prev = cur;
cur = cur->next;
}
if (cur == NULL) return head; /* not found */
if (prev == NULL) head = cur->next; /* deleting the head */
else prev->next = cur->next;
free(cur);
return head;
}
static struct node *reverse(struct node *head) {
struct node *prev = NULL, *cur = head;
while (cur != NULL) {
struct node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
static void print_list(struct node *head) {
for (struct node *cur = head; cur != NULL; cur = cur->next) {
printf("%d -> ", cur->data);
}
printf("NULL\n");
}
static void free_list(struct node *head) {
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}
}
int main(void) {
struct node *head = NULL;
head = push_back(head, 10);
head = push_back(head, 20);
head = push_back(head, 30);
head = push_front(head, 5);
print_list(head); /* 5 -> 10 -> 20 -> 30 -> NULL */
head = delete_value(head, 20);
print_list(head); /* 5 -> 10 -> 30 -> NULL */
head = reverse(head);
print_list(head); /* 30 -> 10 -> 5 -> NULL */
free_list(head);
return 0;
}Compile and run it:
/* gcc -Wall -Wextra -g list.c -o list && ./list */Why every function returns the head
push_front creates a new first node, so the caller's head must change. C passes arguments by value, so a function cannot change the caller's variable directly. Returning the new head and writing head = push_front(...) is the simplest fix, and it is what most textbooks do.
The alternative is passing struct node **head and writing *head = n;. Both are correct. Pick one and use it everywhere - mixing them is how students lose a whole afternoon.
The three lines in reverse()
The reversal loop is the most common viva question on this topic. Trace it on paper with a 3-node list.
struct node *next = cur->next; /* remember where we were going */
cur->next = prev; /* flip this link backwards */
prev = cur; /* prev moves forward */
cur = next; /* cur moves forward */The first line is the one people forget. Without it, cur->next = prev destroys the only reference to the rest of the list, and everything after the current node is leaked and unreachable.
Three mistakes cost marks in the practical exam. One: forgetting the cur == NULL check in delete_value, which segfaults on a missing value. Two: forgetting the prev == NULL case, so deleting the head corrupts the list. Three: calling free(cur) and then using cur->next - read the next pointer BEFORE freeing.
Freeing properly
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}free(head); head = head->next; reads memory you have just given back. It often appears to work, which makes it worse - the bug shows up in a different program on a different day. Save the pointer first.
Run valgrind ./list if your lab machines have it. "All heap blocks were freed -- no leaks are possible" in your report is a strong finish. If valgrind is missing, add a global counter incremented in make_node and decremented before each free, and print it at the end. It should be zero.