Index
Linked List types
In C, there are different types of linked lists based on how they are structured and how nodes are linked together. The most common types include:
1. Singly linked list:
Each node in a singly linked list contains data and a pointer/reference to the next node in the sequence. It only allows traversal in one direction, usually from the head (start) of the list to the tail (end).
#include <stdio.h>
#include <stdlib.h>
// Define the Node struct
typedef struct Node {
int data;
struct Node* next;
} Node;
// Create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Print the linked list
void printList(Node* node) {
while (node) {
printf("%d -> ", node->data);
node = node->next;
}
printf("null\n");
}
int main() {
// Explicitly creating and connecting nodes
Node* node1 = createNode(4);
Node* node2 = createNode(5);
Node* node3 = createNode(6);
Node* node4 = createNode(2);
node1->next = node2;
node2->next = node3;
node3->next = node4;
printList(node1);
// Free the memory
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}
Output:
4 -> 5 -> 6 -> 2 -> null
2. Doubly Linked list
In a doubly linked list, each node contains data and two pointers/references: one to the next node and one to the previous node. This allows traversal in both directions: forward and backward.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
int main() {
Node* node1 = (Node*) malloc(sizeof(Node));
node1->data = 5;
node1->next = NULL;
node1->prev = NULL;
Node* node2 = (Node*) malloc(sizeof(Node));
node2->data = 7;
node2->next = NULL;
node2->prev = node1;
node1->next = node2;
Node* node3 = (Node*) malloc(sizeof(Node));
node3->data = 3;
node3->next = NULL;
node3->prev = node2;
node2->next = node3;
Node* node4 = (Node*) malloc(sizeof(Node));
node4->data = 2;
node4->next = NULL;
node4->prev = node3;
node3->next = node4;
Node* currentNode = node1;
printf("Forward: ");
while (currentNode) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("NULL\n");
currentNode = node4;
printf("Backward: ");
while (currentNode) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->prev;
}
printf("NULL\n");
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}
Output:
Forward: 5 -> 7 -> 3 -> 2 -> NULL
Backward: 2 -> 3 -> 7 -> 5 -> NULL
3. Circular linked list
Circular linked lists are like singly or doubly linked lists, but the last node in the list points back to the first node (for singly linked lists) or the last node points to the first node and the first node points to the last node (for doubly linked lists). This creates a circular structure.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
int main() {
Node* node1 = (Node*) malloc(sizeof(Node));
Node* node2 = (Node*) malloc(sizeof(Node));
Node* node3 = (Node*) malloc(sizeof(Node));
Node* node4 = (Node*) malloc(sizeof(Node));
node1->data = 7;
node2->data = 5;
node3->data = 3;
node4->data = 2;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node1; // Circular link
Node* currentNode = node1;
Node* startNode = node1;
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
while (currentNode != startNode) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("...\n"); // Indicating the list loops back
free(node1);
free(node2);
free(node3);
free(node4);
return 0;
}
Output:
7 -> 5 -> 3 -> 2 -> ...
Each type of linked list has its own advantages and use cases:
- Singly linked lists are simple and use less memory per node since they only have one pointer per node.
- Doubly linked lists support bidirectional traversal, making operations like deletion of nodes easier.
- Circular linked lists can be used in applications where traversal needs to loop back to the beginning, or where continuous access is required.
When choosing the appropriate type of linked list for a specific application, consider factors such as memory efficiency, traversal requirements, and the operations that need to be performed frequently on the list.
