Linked List In C is a linear data structure consisting of nodes. Each node in a linked list is divided into two sections that hold data and the address of the successive node, stored at the random address in the memory.
Arrays are stored contiguously in the memory; when the given array size is large and the consecutive memory is unavailable to store array elements, we can not use an array in that case. To overcome this problem, we have a linked list in c. where data can be stored at random locations and easily accessed by which they are linked together.
What Is a Singly Linked List in C?
A Singly linked list is a collection of data called nodes, where each node is divided into two parts to store data and address at some random addresses. The pointer next, points to the address of the next node in a list.
- Compared to the array data structure, the size of the linked list elements is not fixed. Due to this, there is an efficient memory utilization in a singly linked list.
- Implementing a singly linked list to perform operations like insertion and deletion is easy.
- Elements are accessed easily in a singly linked list.
Let's understand the singly linked list practically with the help of a simple program.
Program to Implement a Singly Linked List in C.
#include <stdio.h>
#include <stdlib.h>
void display();
struct Node {
int data;
struct Node* next;
};
int main()
{
struct Node* first;
struct Node* second;
struct Node* third;
struct Node* fourth;
first = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
second->data = 20;
third->data = 30;
fourth->data = 40;
first->next = second;
second->next = third;
third->next = fourth;
fourth->next = NULL;
display(first);
return 0;
}
void display(struct Node* ptr)
{
while (ptr != NULL) {
printf(
printf(" %d ", ptr->data);
ptr = ptr->next;
}
}
Output:
Moving ahead, Let's look at the memory representation of a singly linked list in c.
Memory Representation of Singly Linked List
Let's consider four elements to insert into the list.
We have four nodes, each consisting of a data part and address part stored at some address. In the singly linked list, we have a special node called the head node that holds the address of the first node, and the last node points to Null.
Every node in a linked list connects with the other through a pointer that points to the address of the next node, and arrows in the above-given diagram represent that.
In a linked list, each node connects through a pointer that points to the address of its next node, and arrows in the above-given diagram represent that.
For Example:
Let our elements to insert be 10, 20, 30, and 40.
- The head node holds the address of the first node.
- The next part of the first node holds the address of the next node, address 2.
- Similarly, the second node holds the address of the third node, address 3.
- The third node holds the address of its next node, address 4. which follows till the last node that is pointing to the Null. In this way, they link together.
Now we know the memory representation of a singly linked list with the help of a diagram. Advancing, let's have a look at the syntax.
Syntax of Singly Linked List
struct node
{
int data;
struct node* next;
};
In order to add or remove nodes from the list we have a certain operation to perform on the singly linked list.
Operations on Singly Linked List:
- Insertion operation
- Deletion operation
- Traversal operation
Let's understand them in detail.
Insertion Operation:
Operation |
Description |
|
Insertion at beginning |
Insert the element at the beginning of the linked list |
|
Insertion at end |
Insert the element at the end of the list |
|
Insertion after specific node |
Insert element after specific element. |
Let's understand it practically.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertionAtBegin(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = (*head);
(*head) = new;
}
void insertionAtEnd(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
struct Node* lastnode = *head;
new->data = new_data;
new->next = NULL;
if (*head == NULL) {
*head = new;
return;
}
while (lastnode->next != NULL) lastnode = lastnode->next;
lastnode->next = new;
return;
}
void insertionAfternode(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = prev_node->next;
prev_node->next = new;
}
void display(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
insertionAtEnd(&head, 11);
insertionAtBegin(&head, 20);
insertionAtBegin(&head, 13);
insertionAtEnd(&head, 44);
insertionAfternode(head->next, 15);
printf("Linked list elements are: ");
display(head);
}
Output:
Deletion Operation:
Operation |
Description |
|
Deletion at beginning |
delete the element from the beginning of the linked list |
|
Deletion at end |
delete the element from the end of the list |
|
Deletion after specific node |
delete element after specified element |
Program to perform deletion operation on singly Linked List.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertionAtBegin(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = (*head);
(*head) = new;
}
void insertionAtEnd(struct Node** head, int new_data)
{
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
struct Node* lastnode = *head;
new->data = new_data;
new->next = NULL;
if (*head == NULL) {
*head = new;
return;
}
while (lastnode->next != NULL) lastnode = lastnode->next;
lastnode->next = new;
return;
}
void insertionAfternode(struct Node* prev_node, int new_data)
{
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = prev_node->next;
prev_node->next = new;
}
void deletionNode(struct Node** head, int key) {
struct Node *ptr = *head, *prev;
if (ptr != NULL && ptr->data == key) {
*head = ptr->next;
free(ptr);
return;
}
while (ptr != NULL && ptr->data != key) {
prev = ptr;
ptr = ptr->next;
}
if (ptr == NULL)
return;
prev->next = ptr->next;
free(ptr);
}
void display(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}
int main() {
struct Node* head = NULL;
insertionAtEnd(&head, 11);
insertionAtBegin(&head, 20);
insertionAtBegin(&head, 13);
insertionAtEnd(&head, 44);
insertionAfternode(head->next, 15);
printf("Linked list elements: ");
display(head);
printf("\nAfter deleting an element: ");
deletionNode(&head, 13);
display(head);
}
Output:
Traversal Operation:
Operation |
Description |
|
Traversal |
Visiting every node in a list at least once |
In a Singly linked list traversal operation, we visit every node at least once to display all the data elements or perform operations.
Function to perform traversal operation on singly linked list
void traversal(struct Node* node)
{
printf("\nLinked List elements: ");
while(node!=NULL)
{
printf("%d ",node->data);
node = node->next;
}
traversal(head);
}
Therefore, we have reached the end of this tutorial on Singly Linked List In C.
If you're eager to gain the skills required to work in a challenging, rewarding, and dynamic IT role - we've got your back! Discover the endless opportunities through this innovative Post Graduate Program in Full Stack Web Development course designed by our partners at Caltech CTME. Enroll today!
Next Steps
"Doubly Linked List In C" can be your next topic. So far, you have learned the Singly Linked List In C. The following fundamentals will be the data structures and the varieties in data structures used for different purposes.
If you are interested in software development, you can explore Simplilearn's Courses that will give you the work-ready software development training you need to succeed today. Are you looking for a comprehensive training program in the most in-demand software development skills, tools, and languages? Our Post Graduate Program in Full Stack Web Development should be the right thing for your career. Explore the course and enroll soon.
Please let us know in the comment section below if you have questions regarding the "Singly Linked List In C" tutorial. Our experts will get back to you at the earliest.
