C Linked Lists From Scratch: Build Your First Data Structure in 2026
Table of Contents
Arrays are great — until you need to insert an element in the middle of 10,000 items and watch your program shift every single one. That’s where C linked lists change the game. They’re the first “real” data structure most C programmers build, and understanding them unlocks everything from stacks and queues to hash tables and graphs.
This lesson teaches you C linked lists from the ground up. You’ll build singly linked lists, doubly linked lists, and circular linked lists with complete, working code. If you’re comfortable with C Pointers and C Dynamic Memory Allocation, you’re ready.
Why Linked Lists Matter in C
Arrays in C have a fundamental limitation: their size is fixed at compile time (or at allocation time with malloc). Even with dynamic arrays, inserting or deleting elements requires shifting data around in memory. C linked lists solve this by storing each element in its own separately allocated node, connected by pointers.
Here’s what linked lists give you that arrays don’t:
- O(1) insertion and deletion — no shifting required once you have a pointer to the location
- Dynamic size — grows and shrinks as needed, no reallocation
- Efficient memory use — only allocates what you need
- No wasted space — unlike arrays that often over-allocate
The tradeoff? No random access. You can’t jump to element 500 — you have to walk there from the beginning. Understanding this tradeoff is what separates good C programmers from mediocre ones.
What Is a Linked List?
A linked list is a sequence of nodes. Each node contains two things: the data it stores and a pointer to the next node. The last node points to NULL, signaling the end of the list.
// The fundamental building block
struct Node {
int data; // The value stored
struct Node *next; // Pointer to next node
};
// Visually:
// [data|next] -> [data|next] -> [data|next] -> NULL
// headNotice the self-referential structure — struct Node contains a pointer to another struct Node. This is perfectly valid in C because the pointer has a fixed size regardless of what it points to. We covered how pointers work in our C Pointers lesson.
Building a Singly Linked List
Creating a Node
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
// Create a new node with given data
struct Node* createNode(int data) {
struct Node *newNode = malloc(sizeof(struct Node));
if (!newNode) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}Every node allocation uses malloc from C Dynamic Memory Allocation. Always check the return value — a NULL return means you’re out of memory.
Building the List
int main(void) {
// Create three nodes
struct Node *head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
// Traverse and print
struct Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
// Output: 10 -> 20 -> 30 -> NULL
// Free all nodes
current = head;
while (current != NULL) {
struct Node *temp = current;
current = current->next;
free(temp);
}
return 0;
}The traversal pattern — current = current->next — is the heartbeat of linked list programming. You’ll write this pattern hundreds of times.
Insertion Operations
There are three places you can insert into a linked list: the beginning, the end, or a specific position.
Insert at the Beginning (Push)
// O(1) — constant time, regardless of list size
void pushFront(struct Node **head, int data) {
struct Node *newNode = createNode(data);
newNode->next = *head; // Point new node to current head
*head = newNode; // Update head to new node
}
// Usage:
struct Node *head = NULL;
pushFront(&head, 30); // 30 -> NULL
pushFront(&head, 20); // 20 -> 30 -> NULL
pushFront(&head, 10); // 10 -> 20 -> 30 -> NULLNotice the double pointer (struct Node **head). We need to modify the caller’s head pointer, so we pass a pointer to it. This is a classic C pattern from C Pointers to Pointers.
Insert at the End (Append)
// O(n) — must traverse to find the last node
void pushBack(struct Node **head, int data) {
struct Node *newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}Insert at Position
// Insert after a given node — O(1) once you have the node
void insertAfter(struct Node *prevNode, int data) {
if (prevNode == NULL) {
fprintf(stderr, "Previous node cannot be NULL\n");
return;
}
struct Node *newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Insert at index — O(n) to find the position
void insertAt(struct Node **head, int index, int data) {
if (index == 0) {
pushFront(head, data);
return;
}
struct Node *current = *head;
for (int i = 0; i < index - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
fprintf(stderr, "Index %d out of bounds\n", index);
return;
}
insertAfter(current, data);
}Deletion Operations
Delete from Beginning
// O(1) — constant time
int popFront(struct Node **head) {
if (*head == NULL) {
fprintf(stderr, "List is empty\n");
return -1;
}
struct Node *temp = *head;
int data = temp->data;
*head = temp->next;
free(temp);
return data;
}Delete by Value
// O(n) — must search for the value
int deleteValue(struct Node **head, int target) {
if (*head == NULL) return 0;
// Special case: head node holds the target
if ((*head)->data == target) {
struct Node *temp = *head;
*head = (*head)->next;
free(temp);
return 1;
}
struct Node *current = *head;
while (current->next != NULL && current->next->data != target) {
current = current->next;
}
if (current->next == NULL) return 0; // Not found
struct Node *temp = current->next;
current->next = temp->next;
free(temp);
return 1;
}The deletion pattern always involves keeping track of the previous node so you can “bridge” over the node being removed. Forgetting to free the removed node is one of the most common C Memory Bugs in C.
Free Entire List
void freeList(struct Node **head) {
struct Node *current = *head;
while (current != NULL) {
struct Node *temp = current;
current = current->next;
free(temp);
}
*head = NULL; // Prevent dangling pointer
}Traversal and Search
// Count nodes
int length(struct Node *head) {
int count = 0;
struct Node *current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
// Search for a value — returns node or NULL
struct Node* search(struct Node *head, int target) {
struct Node *current = head;
while (current != NULL) {
if (current->data == target) return current;
current = current->next;
}
return NULL;
}
// Print the list
void printList(struct Node *head) {
struct Node *current = head;
while (current != NULL) {
printf("%d", current->data);
if (current->next) printf(" -> ");
current = current->next;
}
printf(" -> NULL\n");
}
// Reverse a linked list — classic interview question
void reverse(struct Node **head) {
struct Node *prev = NULL;
struct Node *current = *head;
struct Node *next = NULL;
while (current != NULL) {
next = current->next; // Save next
current->next = prev; // Reverse link
prev = current; // Move prev forward
current = next; // Move current forward
}
*head = prev;
}The reverse function is asked in nearly every C programming interview. The trick is using three pointers: prev, current, and next. Draw it on paper if the logic feels tangled.
Doubly Linked Lists
A doubly linked list adds a prev pointer to each node, allowing traversal in both directions.
struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
};
struct DNode* createDNode(int data) {
struct DNode *node = malloc(sizeof(struct DNode));
if (!node) { fprintf(stderr, "Allocation failed\n"); exit(1); }
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
void dPushFront(struct DNode **head, int data) {
struct DNode *newNode = createDNode(data);
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}
void dDeleteNode(struct DNode **head, struct DNode *target) {
if (*head == NULL || target == NULL) return;
if (*head == target) {
*head = target->next;
}
if (target->next != NULL) {
target->next->prev = target->prev;
}
if (target->prev != NULL) {
target->prev->next = target->next;
}
free(target);
}Doubly linked lists use more memory (extra pointer per node) but make deletion O(1) when you already have a pointer to the node — no need to find the previous node first.
Circular Linked Lists
In a circular linked list, the last node points back to the first instead of NULL. This is useful for round-robin schedulers, circular buffers, and game turn systems.
// Insert into circular list
void circularInsert(struct Node **head, int data) {
struct Node *newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode; // Points to itself
*head = newNode;
return;
}
// Find the last node (the one pointing to head)
struct Node *last = *head;
while (last->next != *head) {
last = last->next;
}
newNode->next = *head;
last->next = newNode;
*head = newNode;
}
// Print circular list — stop when we return to head
void printCircular(struct Node *head) {
if (head == NULL) return;
struct Node *current = head;
do {
printf("%d -> ", current->data);
current = current->next;
} while (current != head);
printf("(back to head)\n");
}Be careful with circular lists — a regular while (current != NULL) loop will never terminate because there’s no NULL. Always use the do...while pattern with a check against the head.
Common Mistakes and Memory Leaks
Linked lists are the number one source of pointer bugs for C beginners. Here are the mistakes that will cost you hours of debugging:
// MISTAKE 1: Not using double pointer for head modification
void brokenPush(struct Node *head, int data) {
struct Node *newNode = createNode(data);
newNode->next = head;
head = newNode; // Only modifies local copy!
}
// Fix: Use struct Node **head
// MISTAKE 2: Losing reference to freed memory
void brokenDelete(struct Node **head) {
free(*head); // Freed!
*head = (*head)->next; // USE AFTER FREE — undefined behavior
}
// Fix: Save next pointer BEFORE freeing
// MISTAKE 3: Not freeing deleted nodes
void leakyDelete(struct Node **head) {
*head = (*head)->next; // Original head node leaked!
}
// Fix: Always free removed nodes
// MISTAKE 4: Dereferencing NULL
void brokenSearch(struct Node *head, int val) {
while (head->data != val) { // Crashes if head is NULL
head = head->next;
}
}
// Fix: Check head != NULL firstUse tools like Valgrind to detect memory leaks in your linked list code. Every malloc must have a matching free. See our C Memory Bugs lesson for detailed debugging techniques.
When to Use Linked Lists vs Arrays
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) amortized | O(n) or O(1) with tail |
| Delete by value | O(n) | O(n) search + O(1) delete |
| Memory overhead | Low | Higher (pointer per node) |
| Cache performance | Excellent | Poor (scattered memory) |
Use arrays when you need fast random access and know the approximate size. Use linked lists when insertions and deletions are frequent and happen at unpredictable positions.
Practice Exercises
- Merge two sorted lists — given two sorted linked lists, merge them into one sorted list
- Detect a cycle — use Floyd’s tortoise and hare algorithm to detect if a list has a cycle
- Find the middle element — use the slow/fast pointer technique
- Remove duplicates — from a sorted linked list, remove all duplicate values
- Build a generic linked list — use
void*data pointers to store any type
Linked lists are the foundation of every data structure you’ll build next. In the next lesson, we’ll use linked lists to implement stacks and queues — two structures that power everything from function calls to print spoolers. Check the C Programming Roadmap for the full path.
