C course menu
Linked Lists in C: Insert, Delete, Search, Reverse and Free
Build a singly linked list in C step by step: self-referential structs, creating nodes with malloc, inserting at the head and tail, searching, deleting a node with a pointer to pointer, reversing the list, and freeing every node.
On this page
A linked list stores items in separate nodes scattered through the heap. Each node holds a value and a pointer to the next node. Unlike an array, a linked list can grow and shrink one node at a time, and inserting at the front is instant, but reaching the nth item means walking from the start.
The node#
A node struct contains a pointer to its own type, a self-referential structure:
typedef struct Node {
int value;
struct Node *next; /* NULL marks the end of the list */
} Node;The tag struct Node is needed inside the definition because the typedef name Node does not exist yet at that point.
A complete list#
The program below builds a list and uses each core operation. Functions that may change the head receive Node **head, a pointer to the caller's head pointer (Advanced Pointers):
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *new_node(int value) {
Node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = NULL;
return n;
}
void push_front(Node **head, int value) {
Node *n = new_node(value);
n->next = *head;
*head = n;
}
void push_back(Node **head, int value) {
Node **link = head;
while (*link != NULL) link = &(*link)->next; /* find the final NULL link */
*link = new_node(value);
}
void print_list(const Node *head) {
for (const Node *p = head; p != NULL; p = p->next) printf("%d -> ", p->value);
printf("NULL\n");
}
Node *find(Node *head, int value) {
for (Node *p = head; p != NULL; p = p->next)
if (p->value == value) return p;
return NULL;
}
int remove_value(Node **head, int value) {
for (Node **link = head; *link != NULL; link = &(*link)->next) {
if ((*link)->value == value) {
Node *doomed = *link;
*link = doomed->next; /* unlink it */
free(doomed);
return 1;
}
}
return 0;
}
void reverse(Node **head) {
Node *prev = NULL, *cur = *head;
while (cur != NULL) {
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head = prev;
}
void free_list(Node **head) {
Node *p = *head;
while (p != NULL) {
Node *next = p->next; /* save before freeing */
free(p);
p = next;
}
*head = NULL;
}
int main(void) {
Node *list = NULL; /* empty list */
push_back(&list, 20);
push_back(&list, 30);
push_front(&list, 10);
push_back(&list, 40);
print_list(list);
printf("find 30: %s\n", find(list, 30) ? "yes" : "no");
remove_value(&list, 10); /* the head */
remove_value(&list, 30); /* the middle */
printf("remove 99: %d\n", remove_value(&list, 99));
print_list(list);
push_back(&list, 50);
reverse(&list);
print_list(list);
free_list(&list);
print_list(list);
return 0;
}10 -> 20 -> 30 -> 40 -> NULL
find 30: yes
remove 99: 0
20 -> 40 -> NULL
50 -> 40 -> 20 -> NULL
NULLHow the operations work#
- push_front creates a node, points it at the old head, and makes it the new head. It takes constant time, O(1).
- push_back walks to the last link. It takes O(n); keeping a separate
tailpointer makes it O(1). - remove_value walks with
Node **link, a pointer to "the pointer that points at the current node". Removing then means one assignment,*link = doomed->next, whether the node is the head or in the middle, so the head needs no special case. - reverse turns each
nextpointer around, using three pointers: previous, current and next. - free_list must save
p->nextbefore freeingp, because reading a freed node is use after free.
Arrays or linked lists?#
In practice, arrays (including growable ones) are usually faster on modern hardware because of caching. Linked lists suit frequent insertions and removals in the middle, and they are a favourite interview topic.
Practice#
Practice exercise
Using the node type above, write int length(const Node *head) and int middle_value(const Node *head) that finds the middle node in one pass with a slow pointer and a fast pointer (the fast one moves two nodes at a time). Build the list 1 → 2 → 3 → 4 → 5 with push_front and test both.
Show solution
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
void push_front(Node **head, int value) {
Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->value = value;
n->next = *head;
*head = n;
}
int length(const Node *head) {
int n = 0;
for (; head != NULL; head = head->next) n++;
return n;
}
int middle_value(const Node *head) {
const Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow->value;
}
int main(void) {
Node *list = NULL;
for (int v = 5; v >= 1; v--) push_front(&list, v);
printf("length %d, middle %d\n", length(list), middle_value(list));
while (list != NULL) {
Node *next = list->next;
free(list);
list = next;
}
return 0;
}length 5, middle 3Key takeaway#
Finished this lesson?