Last Updated on May 25, 2023 by Prepbytes
This article dives into the world of singly linked lists in C, offering a comprehensive understanding of their inner workings and practical implementation. We will explore how singly linked lists enable the creation of dynamic data structures, facilitating flexible and efficient data manipulation.
By delving into the fundamentals of singly linked lists, we aim to equip readers with the knowledge needed to develop and optimize their own linked list programs in C. Whether you’re a novice programmer seeking to expand your repertoire or a seasoned developer in search of a refresher, this article serves as an invaluable resource to navigate the intricacies of singly linked lists.
Throughout this article, we will discuss the key components of singly linked lists, including nodes, pointers, and the various operations that can be performed on them. We will delve into the mechanics of creating, inserting, and deleting elements, as well as traversing the list to access or modify data. Additionally, we will explore techniques to handle common challenges, such as handling edge cases and memory management.
Singly Linked List
A single linked list is a particular kind of linked list that can only be navigated from head to tail. A node is the term used to describe each item in a linked list. A single node that helps maintain the list’s structure holds data as well as a pointer to the node after it.
The list’s head node, which permits access to all other components and points to the list’s root node, is the first node. Since the last node points in the direction of the NULL pointer, we identify it as the tail node. Let’s see representation of node of the singly linked list in c:
struct Node{
int data;
struct Node *next;
};Operations on singly linked list:
1. Insertion
A singly linked list’s first node can be added by following the steps below.
- Point the new node at HEAD.
- Make the HEAD point to the new node.
void insertStart(struct Node** head, int data){
// dynamically create memory for this newNode
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//re-assign head to this newNode
*head = newNode;
printf("Inserted %d\n",newNode->data);
} 2. Deletion
As shown below, the singly linked list’s initial node can be removed,
- Make the HEAD point to its next element.
void deleteStart(struct Node** head){
struct Node* temp = *head;
// If head is NULL it means Singly Linked List is empty
if(*head == NULL){
printf("Impossible to delete from empty Singly Linked List");
return;
}
// move head to next node
*head = (*head)->next;
printf("Deleted: %d\n", temp->data);
free(temp);
} 3. Display
We must go from first to last in the singly linked list in order to display it all.
In contrast to arrays, a linked list’s nodes cannot be accessed arbitrarily. Therefore, in order to get to the nth element, we must first walk through all (n-1) elements.
void display(struct Node* node){
printf("\nLinked List: ");
// as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
} Code Implementation
#include<stdlib.h>
#include<stdio.h>
struct Node{
int data;
struct Node *next;
};
void deleteStart(struct Node** head){
struct Node* temp = *head;
// If head is NULL it means Singly Linked List is empty
if(*head == NULL){
printf("Impossible to delete from empty Singly Linked List");
return;
}
// move head to next node
*head = (*head)->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}
void insertStart(struct Node** head, int data){
// dynamically create memory for this newNode
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
// assign data value
newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;
//re-assign head to this newNode
*head = newNode;
printf("Inserted %d\n",newNode->data);
}
void display(struct Node* node){
printf("\nLinked List: ");
// as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}
int main()
{
struct Node* head = NULL;
insertStart(&head,100);
insertStart(&head,80);
insertStart(&head,60);
insertStart(&head,40);
insertStart(&head,20);
display(head);
deleteStart(&head);
deleteStart(&head);
display(head);
return 0;
} Output
Inserted 100
Inserted 80
Inserted 60
Inserted 40
Inserted 20
Linked List: 20 40 60 80 100
Deleted: 20
Deleted: 40
Linked List: 60 80 100 Time Complexity
- Inserting a new node at the start is an O(1) operation.
- Deleting the first node of a singly linked list is an O(1) operation.
- Since the entire linked list is traversed, the operation costs us O(N) time complexity.
Uses of Linked List
Some of the real-world applications of the singly linked list are as follows:
- polynomials with one or two variables are stored using this.
- serve as a base for many data structures, including Graph, Queue, and Stack.
- a plan for file allocation methods based on operating systems.
- Check the backup disk’s free space availability. All of the open areas can be connected.
- In turn-based games, the player who is about to be played can be determined using a circular linked list. Once that person has finished their turn, we move on to the next.
- to keep a record of anything that may be accessed again, such as music, movies, pictures, websites, etc.
Conclusion
Singly linked lists in C provide a versatile and efficient approach to organizing and manipulating data. Throughout this article, we have explored the inner workings of singly linked lists, delving into their fundamental components and practical implementation.
By understanding the structure and mechanics of singly linked lists, programmers gain a powerful tool to manage dynamic data structures effectively. The use of nodes and pointers allows for flexible insertion, deletion, and traversal of elements, enabling efficient data manipulation and organization.
We have examined the essential operations associated with singly linked lists, including creating a list, inserting and deleting elements, and traversing the list to access or modify data. By mastering these operations, developers can tackle a wide range of programming challenges, from implementing algorithms and data structures to solving real-world problems.
FAQ related to Singly Linked List Program in C
Q1: How do I delete an element from a singly linked list?
Ans. To delete an element from a singly linked list, you locate the node containing the target element by traversing the list. Then, you update the pointers of the preceding node to bypass the node to be deleted, and free the memory occupied by the deleted node using the free() function.
Q2: How do I traverse a singly linked list?
Ans. To traverse a singly linked list, you start from the head node (the first node) and follow the pointers to visit each subsequent node in sequence until you reach the end of the list. During traversal, you can access and process the data stored in each node.
Q3: How do I check if a singly linked list is empty?
Ans. To check if a singly linked list is empty, you can simply verify if the head pointer is NULL. If the head pointer is NULL, it indicates that the list has no nodes and is therefore empty.
Q4: Can a singly linked list contain duplicate elements?
Ans. Yes, a singly linked list can contain duplicate elements. Each node in the list stores a data element, and multiple nodes can hold the same value.
Q5: How do I free the memory occupied by a singly linked list?
Ans. To free the memory occupied by a singly linked list, you need to traverse the list and use the free() function to release the memory allocated for each node. It is essential to update the pointers correctly while traversing to avoid losing track of the remaining nodes.
Other C Programs
C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C
Doubly Linked List Program in C
FCFS Scheduling Program in C
Insertion Sort Program in C