Linked list is an important part of data structure. Among them, single linked list is the simplest of linked list. Today we will learn what is single linked list, how it works and its usage step by step.
What is Single Linked List ?
A singly linked list is a linear data structure where the nodes are arranged in a specific pattern. These nodes do not occupy consecutive spaces in memory like an array does. Each node in a singly linked list consists of two parts:
- Data: The data part stores the node’s data (e.g.: number, string, object).
- Next Pointer: The next pointer stores the address of the next node.
The NEXT pointer of the last node points to NULL or zero, which refers to the last node in the list.
We can access a list only through the head node, which refers to the starting node of a singly linked list.
Example:
Suppose we want to store the numbers 3, 5, 9 and 21 using a singly linked list.
1. Create First Node (3):
- I created a node whose data is 3.
- Since this is now the only node, its next pointer will be NULL .
Head --> [3 | NULL]
2. Add Second Node (5):
- I have created a new node again with data = 5 and next = NULL.
- We now need to update the next pointer of our first node (3) with the address of this new node (5).
Head --> [3 | ] --> [5 | NULL]
3. Add Third and Fourth Node (9 and 21):
- Then I add two more nodes 9 and 21.
- The next of 5 will point to 9 and the next of 9 to 21, and the next of 21 will point to nothing and will be NULL, which will indicate the end of that list.
Head --> [3 | ] --> [5 | ] --> [9 | ] --> [21 | NULL]
This chain-like connection method is called the core of a linked list.
#include <stdio.h>
#include <stdlib.h>
// Declare a node structure
struct Node {
int data; // Data stored in the node
struct Node* next; // Address of the next node
};
// Function to print by traversing the list
void printList(struct Node* n) {
while (n != NULL) {
printf("%d -> ", n->data);
n = n->next;
}
printf("NULL\n");
}
int main() {
// Create a node
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// Allocate memory
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
// Assigning values ??to nodes and linking
head->data = 3;
head->next = second;
second->data = 5;
second->next = third;
third->data = 9;
third->next = NULL; // The third node is the end of the list
// Printing the list
printList(head);
return 0;
}
Advantage of Single Linked List
- Dynamic Size: It is very easy to add or remove nodes at code run time.
- Memory Effiecents: Use memory as needed, no need to allocate blocks like arrays
- Insert/Delete: Any data or node can be deleted and added very easily. Unlike arrays, you don’t have to shift all the data, which is a very complicated method, but it is very easy to do in a linked list.
Disadvantage of Single Linked List
- Extra Memory: Extra memory is required for each node and for pointing to another node.
- Specific data cannot be accessed.: To reach the first node in a linked list, you have to traverse from the head to the end. You cannot access data directly like in an array.
- Traverse backwards is difficult:A singly linked list can access data from front to back. It cannot access data from back to front, which can get complicated later.
Where is it used?
- Operation System In process scheduling
- Browser History store
- Music Player Playlist Managment
- Stack & Queue Data Structure Implementation.
