A linked list in C is a data structure where each element (called a node) stores a value and a pointer to the next node. Unlike an array, nodes are scattered in memory — the pointers chain them together into a sequence. This makes insertion and deletion at any position O(1) once you have a pointer to that position, without shifting elements the way an array requires.
This page covers a complete singly linked list implementation in C — node creation, insert at front, insert at end, delete by value, search, count, traverse, and free — with a step-by-step trace and complexity analysis.
Linked List vs Array
| Property | Array | Linked List |
|---|---|---|
| Size | Fixed at compile time (or VLA/malloc) | Grows and shrinks at runtime |
| Insert/Delete at front | O(n) — must shift elements | O(1) — update head pointer |
| Insert/Delete at end | O(1) amortized (dynamic array) | O(n) without tail pointer |
| Random access | O(1) — arr[i] directly | O(n) — must traverse from head |
| Memory | Contiguous — cache-friendly | Scattered — pointer overhead per node |
Node Structure
Each node in a singly linked list holds two things: the data and a pointer to the next node. In C:
typedef struct Node {
int data;
struct Node *next;
} Node;
The last node’s next pointer is always NULL — this marks the end of the list.
head │ ▼ [10|→]──→[20|→]──→[30|→]──→[40|NULL]
Singly Linked List Program in C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
/* ── Node creation ───────────────────────────────────────────── */
Node *createNode(int val)
{
Node *n = (Node *)malloc(sizeof(Node));
if (!n) { fprintf(stderr, "malloc failed\n"); exit(1); }
n->data = val;
n->next = NULL;
return n;
}
/* ── Insert at front — O(1) ──────────────────────────────────── */
Node *insertFront(Node *head, int val)
{
Node *n = createNode(val);
n->next = head;
return n; /* new head */
}
/* ── Insert at end — O(n) ────────────────────────────────────── */
Node *insertEnd(Node *head, int val)
{
Node *n = createNode(val);
Node *curr;
if (head == NULL)
return n;
curr = head;
while (curr->next != NULL)
curr = curr->next;
curr->next = n;
return head;
}
/* ── Insert after a given value ──────────────────────────────── */
void insertAfter(Node *head, int after, int val)
{
Node *curr;
for (curr = head; curr != NULL; curr = curr->next) {
if (curr->data == after) {
Node *n = createNode(val);
n->next = curr->next;
curr->next = n;
return;
}
}
printf("%d not found — cannot insert after it.\n", after);
}
/* ── Delete first node with matching value — O(n) ───────────── */
Node *deleteNode(Node *head, int val)
{
Node *curr, *prev;
if (head == NULL) { printf("List is empty.\n"); return NULL; }
if (head->data == val) { /* deleting the head */
curr = head;
head = head->next;
free(curr);
return head;
}
prev = head;
curr = head->next;
while (curr != NULL) {
if (curr->data == val) {
prev->next = curr->next;
free(curr);
return head;
}
prev = curr;
curr = curr->next;
}
printf("%d not found in list.\n", val);
return head;
}
/* ── Search — returns 1-based position, or -1 ───────────────── */
int search(Node *head, int val)
{
Node *curr;
int pos = 1;
for (curr = head; curr != NULL; curr = curr->next) {
if (curr->data == val) return pos;
pos++;
}
return -1;
}
/* ── Count nodes — O(n) ──────────────────────────────────────── */
int length(Node *head)
{
Node *curr;
int count = 0;
for (curr = head; curr != NULL; curr = curr->next)
count++;
return count;
}
/* ── Display — O(n) ──────────────────────────────────────────── */
void display(Node *head)
{
Node *curr;
if (head == NULL) { printf("(empty list)\n"); return; }
for (curr = head; curr != NULL; curr = curr->next)
printf("%d → ", curr->data);
printf("NULL\n");
}
/* ── Free all nodes — O(n) ───────────────────────────────────── */
void freeList(Node *head)
{
Node *curr = head, *next;
while (curr != NULL) {
next = curr->next;
free(curr);
curr = next;
}
}
int main(void)
{
Node *head = NULL;
int pos;
/* Build the list */
head = insertEnd(head, 10);
head = insertEnd(head, 20);
head = insertEnd(head, 30);
head = insertEnd(head, 40);
head = insertFront(head, 5);
insertAfter(head, 20, 25);
printf("Initial list: "); display(head);
printf("Length: %d\n", length(head));
/* Search */
pos = search(head, 25);
printf("25 is at position: %d\n", pos);
pos = search(head, 99);
printf("99 is at position: %d (not found)\n\n", pos);
/* Delete middle node */
head = deleteNode(head, 25);
printf("After deleting 25: "); display(head);
/* Delete head */
head = deleteNode(head, 5);
printf("After deleting 5: "); display(head);
/* Delete tail */
head = deleteNode(head, 40);
printf("After deleting 40: "); display(head);
/* Delete non-existent */
head = deleteNode(head, 99);
printf("After deleting 99: "); display(head);
freeList(head);
return 0;
}
How to Compile and Run
gcc -ansi -Wall -Wextra -o linkedlist linkedlist.c
./linkedlist
Sample Output
Initial list: 5 → 10 → 20 → 25 → 30 → 40 → NULL Length: 6 25 is at position: 4 99 is at position: -1 (not found) After deleting 25: 5 → 10 → 20 → 30 → 40 → NULL After deleting 5: 10 → 20 → 30 → 40 → NULL After deleting 40: 10 → 20 → 30 → NULL 99 not found in list. After deleting 99: 10 → 20 → 30 → NULL
Step-by-Step Trace
Building the list:
insertEnd(NULL, 10): head → [10|NULL] insertEnd(head, 20): head → [10|→] → [20|NULL] insertEnd(head, 30): head → [10|→] → [20|→] → [30|NULL] insertEnd(head, 40): head → [10|→] → [20|→] → [30|→] → [40|NULL] insertFront(head, 5): head → [5|→] → [10|→] → [20|→] → [30|→] → [40|NULL] insertAfter( 20, 25): head → [5|→] → [10|→] → [20|→] → [25|→] → [30|→] → [40|NULL]
Deleting node 25 (middle):
Traverse: 5→10→20→25 (found at curr, prev=20's node) prev→next = curr→next (20's next now points to 30) free(curr) (25's node freed) Result: head → [5] → [10] → [20] → [30] → [40] → NULL
Deleting node 5 (head):
head→data == 5 (special case: deleting head) temp = head head = head→next (head now points to 10) free(temp) (5's node freed) Result: head → [10] → [20] → [30] → [40] → NULL
How the Implementation Works
insertFront: Creates a node, points itsnextto the current head, returns the new node as the new head. O(1).insertEnd: Traverses to the last node (wherenext == NULL), attaches the new node there. O(n). Adding atailpointer reduces this to O(1) at the cost of maintaining two pointers.deleteNode: The head-deletion case is special because there is noprev— we just advanceheadand free the old head. For all other nodes, we track bothprevandcurrand stitch them together withprev->next = curr->next.freeList: Savecurr->nextbefore freeingcurr— without this, freeing the current node destroys the pointer to the rest of the list.
Time and Space Complexity
| Operation | Time | Notes |
|---|---|---|
| Insert at front | O(1) | Update head pointer only |
| Insert at end | O(n) | O(1) with a tail pointer |
| Delete by value | O(n) | Must find the node first |
| Search | O(n) | No random access |
| Traverse / Display | O(n) | Visit each node once |
| Space (n nodes) | O(n) | One pointer overhead per node |
What This Program Teaches
- Dynamic memory management: every node is a separate
malloccall; the programmer is responsible for freeing each one — a leaked node means a memory leak - Pointer chasing: traversal follows
curr = curr->nextuntil NULL; mishandling this causes segmentation faults - The head-delete special case: deleting the first node changes the list’s entry point — returning the new head is the clean solution; a pointer-to-pointer (
Node **) is the alternative - The “save next before free” pattern:
next = curr->next; free(curr); curr = next;— forgetting the save is a classic use-after-free bug
Related Programs
- Doubly Linked List in C — two pointers per node, supports backward traversal
- Queue Using Linked List in C — FIFO queue built on linked list nodes
- Stack Using Linked List in C — LIFO stack built on linked list nodes
- Binary Search Tree in C — tree-structured nodes with left/right pointers
- Reverse a Linked List in C
As an Amazon Associate we earn from qualifying purchases.
Recommended Book
Pointers, structures, and dynamic allocation — the foundations of linked lists — are covered in detail in chapters 5 and 6 of The C Programming Language by Kernighan & Ritchie. Also on Amazon.com.