1. Introduction
A linked list is a linear data structure where elements, called nodes, are not stored in contiguous memory. Instead, each node holds its data plus a pointer to the next node. In C, linked lists are built manually using structs and dynamic memory allocation (malloc), which makes them a core topic for understanding pointers, memory management, and dynamic data structures. Unlike arrays, linked lists can grow or shrink at runtime without needing to know the size in advance.
Cricket analogy: A Test match's over-by-over commentary isn't stored in one contiguous scrapbook, each entry is written on its own card with a pointer to next ball, just like linked-list nodes scattered in memory but chained by pointers.
Linked lists solve a key limitation of arrays: insertion and deletion in the middle of an array requires shifting elements, which is O(n) and wasteful. A linked list can insert or delete a node in O(1) time once you have a pointer to the right location, at the cost of losing O(1) random access (you must traverse from the head to reach a given node).
Cricket analogy: Inserting a new batsman into a fixed, pre-printed batting order requires rewriting every name below him, like an array shift, whereas a scorer's handwritten chain of notes just needs one arrow redrawn, like a linked list.
2. Syntax
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;The struct is self-referential: 'struct Node' contains a pointer to another 'struct Node'. The 'typedef' lets you refer to the type simply as 'Node' afterward. Note that inside the struct definition you must still write 'struct Node *next' (not just 'Node *next') because the typedef name 'Node' is not fully defined until the closing brace and semicolon are reached.
Cricket analogy: A player profile card that references the next player in the batting order by name, written while the order itself is still being finalized, mirrors why you must write struct Node *next, since Node isn't fully defined yet.
3. Explanation
A linked list is built from three core operations: (1) creating a node with malloc and initializing its fields, (2) inserting the node into the list by rewiring pointers (commonly at the head, since that is O(1)), and (3) traversing the list from 'head' until you reach a node whose 'next' is NULL, which marks the end of the list. Each node is allocated independently on the heap, so the nodes can live anywhere in memory — only the pointers connect them logically.
Cricket analogy: Building an innings involves three steps: bringing in a new batsman (malloc), sending them to the crease at the top of the order (insert at head), and watching the scoreboard tick until the innings ends at the last wicket (traverse to NULL).
Insertion at the head follows a fixed pattern: allocate a new node, set its 'data', point its 'next' to the current 'head', then update 'head' to point to the new node. Insertion at the tail requires traversing to the last node (the one whose 'next' is NULL) and attaching the new node there. Deletion requires updating the 'next' pointer of the previous node to skip over the node being removed, then freeing that node's memory to avoid a memory leak.
Cricket analogy: Sending a pinch-hitter straight to open the batting (insert at head) is quick, but slotting a specialist finisher at number 11 (insert at tail) means walking past every other batter first; retiring a player means updating the order and releasing their contract (free) so it isn't wasted.
Always check the return value of malloc before dereferencing it. If malloc fails, it returns NULL, and writing to a NULL pointer (e.g., newNode->data = x) causes undefined behavior — typically a crash. Also remember to free() every node when the list is destroyed, and never access a node's fields after it has been freed (a dangling pointer bug).
Time complexity: insertion/deletion at the head is O(1). Insertion/deletion at the tail or at an arbitrary position is O(n) for a singly linked list because you must traverse to reach that point first. Searching for a value is O(n) since there is no random access, unlike arrays.
4. Example
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
/* Insert a new node at the head of the list */
Node *insertAtHead(Node *head, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->next = head;
return newNode; /* new node becomes the head */
}
/* Traverse and print the list */
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
/* Free every node to avoid memory leaks */
void freeList(Node *head) {
Node *current = head;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
}
int main(void) {
Node *head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
printf("Linked list contents:\n");
printList(head);
freeList(head);
return 0;
}5. Output
Linked list contents:
10 -> 20 -> 30 -> NULL6. Key Takeaways
- A linked list node is a self-referential struct: data plus a pointer to the next node.
- Nodes are allocated dynamically with malloc; always check for NULL before use.
- Head insertion is O(1); tail insertion, search, and arbitrary access are O(n).
- Traversal always starts at head and stops when current->next (or current) is NULL.
- Every malloc'd node must eventually be freed to avoid memory leaks.
Practice what you learned
1. What does a singly linked list node in C typically contain?
2. Why must the struct definition use 'struct Node *next' instead of 'Node *next' inside its own body when using typedef?
3. What is the time complexity of inserting a new node at the head of a singly linked list?
4. What happens if you dereference a pointer returned by a failed malloc() call without checking for NULL?
5. How do you correctly free all nodes of a linked list without causing a memory leak or a use-after-free bug?
Was this page helpful?
You May Also Like
Stack Implementation in C
Master array-based stack implementation in C with push, pop, peek, overflow/underflow checks, and full working code.
Pointers in C
Learn C pointers with syntax, address-of and dereference operators, pointer arithmetic, and common pitfalls, with examples and output.
Dynamic Memory Allocation in C
Master C dynamic memory allocation with malloc, calloc, realloc, and free, including sizing, zero-initialization, and leak prevention.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics