Singly vs Doubly Linked List in C: Key Differences and Usage
singly linked list in C has nodes with a pointer to the next node only, making it simple and memory-efficient. A doubly linked list has nodes with pointers to both next and previous nodes, allowing easier backward traversal but using more memory.Quick Comparison
Here is a quick side-by-side comparison of singly and doubly linked lists in C.
| Factor | Singly Linked List | Doubly Linked List |
|---|---|---|
| Node Structure | Contains data and pointer to next node | Contains data and pointers to next and previous nodes |
| Memory Usage | Less memory (one pointer per node) | More memory (two pointers per node) |
| Traversal | Forward only | Forward and backward |
| Insertion/Deletion | Simpler at head, harder at tail or middle | Easier at both ends and middle |
| Complexity | Simpler to implement | More complex due to extra pointer management |
| Use Case | When memory is limited and simple traversal suffices | When bidirectional traversal or easy deletion is needed |
Key Differences
A singly linked list node contains a data field and a pointer to the next node only. This makes it simple and uses less memory, but you can only move forward through the list. Operations like insertion or deletion at the end or middle require traversal from the head, which can be slower.
In contrast, a doubly linked list node has two pointers: one to the next node and one to the previous node. This allows moving both forward and backward easily. It simplifies operations like deletion or insertion at any position because you can access the previous node directly. However, it uses more memory and requires careful pointer updates to avoid errors.
Overall, singly linked lists are good for simple, memory-efficient tasks with forward-only access, while doubly linked lists are better when you need flexible navigation and easier modifications.
Code Comparison
Here is a simple example in C showing how to create a singly linked list, add a node at the front, and print the list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// Add node at front
void push(Node** head_ref, int new_data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
// Print list
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
push(&head, 3);
push(&head, 2);
push(&head, 1);
printList(head);
return 0;
}Doubly Linked List Equivalent
This example shows how to create a doubly linked list, add a node at the front, and print the list forward.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
// Add node at front
void push(Node** head_ref, int new_data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = *head_ref;
new_node->prev = NULL;
if (*head_ref != NULL) {
(*head_ref)->prev = new_node;
}
*head_ref = new_node;
}
// Print list forward
void printList(Node* node) {
while (node != NULL) {
printf("%d <-> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
push(&head, 3);
push(&head, 2);
push(&head, 1);
printList(head);
return 0;
}When to Use Which
Choose a singly linked list when you want a simple, memory-efficient structure and only need to traverse forward. It is ideal for stacks or simple queues where backward traversal is unnecessary.
Choose a doubly linked list when you need to traverse both forward and backward easily or perform frequent insertions and deletions at both ends or in the middle. It is useful for complex data structures like navigation systems, undo functionality, or when quick bidirectional access is required.