Linked List in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Build a singly linked list with struct nodes, dynamic memory, insertion, and traversal.
A linked list is a linear data structure made of nodes. Each node stores data and a link to another node.
In an array, elements are stored side by side in memory. In a linked list, nodes can be stored at different memory locations, and each node keeps the address of the next node.
This is why linked lists are useful when data grows, shrinks, or needs frequent insertion and deletion.
Why Linked List Is Needed
Arrays are simple and fast for index access, but their size is usually fixed once created. If we need to insert an element in the middle of an array, many elements may need to shift.
A linked list solves this by connecting nodes with pointers. To insert or delete a node, we mostly change links instead of shifting many values.
Node Structure
A singly linked list node usually has two parts.
- `data` stores the value
- `next` stores the address of the next node
```c
struct Node {
int data;
struct Node *next;
};
```
Here, `struct Node *next` means `next` can store the address of another node of the same type.
Head Pointer
`head` stores the address of the first node. If the list is empty, `head` is `NULL`.
If `head` changes, the first node of the list changes. That is why insertion at the beginning usually returns the new head.
For beginners, this is the most important linked list idea: you do not directly hold the whole list. You hold the address of the first node, and from there you travel node by node.
Types of Linked List
- Singly linked list: each node points to the next node
- Doubly linked list: each node points to the previous and next node
- Circular linked list: the last node points back to the first node
Most students should learn singly linked list first because it clearly teaches pointer movement and `NULL` handling.
Insertion at Beginning
To insert at the beginning, create a new node, point it to the current head, then make the new node the head.
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *insertAtBeginning(struct Node *head, int value) {
struct Node *newNode = malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return head;
}
newNode->data = value;
newNode->next = head;
return newNode;
}
void printList(struct Node *head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
void freeList(struct Node *head) {
while (head != NULL) {
struct Node *temp = head;
head = head->next;
free(temp);
}
}
int main(void) {
struct Node *head = NULL;
head = insertAtBeginning(head, 30);
head = insertAtBeginning(head, 20);
head = insertAtBeginning(head, 10);
printList(head);
freeList(head);
return 0;
}
```
Traversal
Traversal means visiting each node one by one from `head` until `NULL` is reached.
```c
struct Node *current = head;
while (current != NULL) {
current = current->next;
}
```
This pattern is used for printing, counting, searching, deleting, and finding the last node.
Insertion at End
To insert at the end, create a new node and move a temporary pointer until it reaches the last node. The last node is the node whose `next` is `NULL`.
After reaching the last node, set its `next` to the new node.
Deletion Idea
Deletion means removing a node from the chain and reconnecting the remaining nodes.
If the first node is deleted, `head` must move to the second node. If a middle node is deleted, the previous node should point to the deleted node's next node.
In C, after deleting a dynamically allocated node, use `free` to release memory.
Linked List vs Array
- Arrays give fast direct access using index
- Linked lists do not provide direct index access
- Arrays store elements in continuous memory
- Linked lists store nodes using dynamic memory
- Linked lists are good when insertion and deletion are frequent
- Arrays are better when random access is important
Memory and Pointer Safety
Linked lists depend heavily on pointers, so pointer handling must be careful.
- Check whether `malloc` returned `NULL`
- Do not lose the `head` pointer while traversing
- Use a temporary pointer for movement
- Free nodes when they are no longer needed
- Stop traversal when the pointer becomes `NULL`
Complexity
- Insertion at beginning: O(1)
- Traversal: O(n)
- Searching: O(n)
- Insertion at end: O(n) in a normal singly linked list
- Deletion after finding the node: O(1)
Practice Question
Create a singly linked list, insert three values at the end, print the list, and count how many nodes are present.