SINGLY LINKED LIST
A singly linked list is a linked list in which each node contain only one link pointing to the next node
in the list.In a singly linked list , the first node always pointed by a pointer called HEAD.If the link of
the points to NULL , then that indicates the end of the list.
Eg: Consider a linked list that stores the roll number of students in a class.
struct student
int rno;
struct student * link;
}*header,*newnode,*ptr,*pptr;
Algorithm: GetNode()
Input: NODE is the type of the data for which a memory has to be allocated.
Output: Return a message if the allocation fails else the pointer to the memory block allocated.
Singly linked list Operations
1. Traversing (Display) all the elements of the list.
2. Inserting a node into the list.
i. insert an element at the beginning of the list
ii. insert an element at the end of the list
iii. insert an element at the specified position in the list
3. Deleting a node from the list
i. Delete an element from the beginning of the list
ii. Delete an element at the end of the list
iii. Delete an element at the specified position in the list
4. Copying the list to make a duplicate of it.
5. Merging the linked list with another one to make a larger list.
6. Searching for an element in the list.
7. Count the number of elements.
1. Traversing (Display) all the elements of the list.
Algorithm Traverse _SL
Input: HEADER is the pointer to the header node.
Output: According to the Process():- print the data content of a node or count the number of
nodes.
Data structure: A single linKed list whose address of the starting node is known from the
HEADER.
//sample code
void display()
ptr=header->link;
while(ptr!=NULL)
printf("\n %d",ptr->rno);
ptr=ptr->link;
2. Inserting a node into the list.
i. insert an element at the beginning of the list
The algorithm InsertFront_SL is used to insert a node at the front of a single linked list.
Algorithm InsertFront_SL
Input: HEADER is the pointer to the header node and X is the data of the node to be inserted.
Output: A singe linked list with a newly inserted node at the front of the list.
Data Structures: A single linked list whose address of the starting node is known from the HEADER.
//sample code
void insert_beg()
int r;
newnode=(struct student *)malloc(sizeof(struct student));
printf("\n enter the roll no;");
scanf("%d",&r);
newnode->rno=r;
newnode->link=NULL;
if(header->link==NULL)
header->link=newnode;
else
newnode->link=header->link ;
header->link=newnode;
ii. insert an element at the end of the list
The algorithm InsertEnd_SL is used to insert a node at the end of a single linked list.
Algorithm InsertEnd_SL
Input: HEADER is the pointer to the header node and X is the data of the node to be inserted.
Output: A singe linked list with a newly inserted node having data X at the end of the list.
Data Structures: A single linked list whose address of the starting node is known from the HEADER.
//sample code
void insert_end()
int r;
newnode=(struct student *)malloc(sizeof(struct student));
printf("\n enter the roll no;");
scanf("%d",&r);
newnode->rno=r;
newnode->link=NULL;
if(header->link==NULL)
{
header->link=newnode;
else
ptr=header->link;
while(ptr->link!=NULL)
ptr=ptr->link;
ptr->link=newnode;
iii. insert an element at the specified position in the list
The algorithm InsertAny_SL is used to insert a node into a single linked list at any position in the list.
Algorithm InsertAny_SL
Input: HEADER is the pointer to the header node and X is the data of the node to be inserted and KEY
being the data of the key node after which the node has to be inserted.
Output: A singe linked list enriched with newly inserted node having data X after the node with data
KEY.
Data Structures: A single linked list whose address of the starting node is known from the HEADER.
//sample code
void insert_mid()
int r,key;
newnode=(struct student *)malloc(sizeof(struct student));
printf("\n enter the roll no;");
scanf("%d",&r);
newnode->rno=r;
newnode->link=NULL;
printf("\n enter the locaton ,you want to insert");
scanf("%d",&key);
if(header->link==NULL)
header->link=newnode;
else
ptr=header->link;
while(ptr->rno!=key && ptr->link!=NULL)
ptr=ptr->link;
if(ptr->link==NULL)
printf("\n such key not in the list \n");
else
newnode->link=ptr->link;
ptr->link=newnode;
3.Deleting a node from the list
i. Delete an element from the beginning of the list
//sample code
void delete_beg()
if(header->link==NULL)
printf("\n list is empty");
else
ptr=header->link;
header->link=ptr->link;
ii. Delete an element at the end of the list
//sample code
void delete_end()
if(header->link==NULL)
{
printf("\n list is empty");
else
ptr=header->link;
if(ptr->link==NULL)
header->link=NULL;
else
while(ptr->link!=NULL)
pptr=ptr;
ptr=ptr->link;
pptr->link=NULL;
iii. Delete an element at the specified position in the list
//sample code
void delete_mid()
int key;
printf("\n enter the rollno, you want to delete ");
scanf("%d",&key);
if(header->link==NULL)
printf("\n list is empty");
}
else
ptr=header->link;
while(ptr->rno!=key && ptr->link!=NULL)
pptr=ptr;
ptr=ptr->link;
if(ptr->link==NULL)
printf("\n such key not in the list ");
else
pptr->link=ptr->link;
6. Searching for an element in the list.
void search()
int key,count=1;
printf("\n enter the rollno, you want to search ");
scanf("%d",&key);
if(header->link==NULL)
printf("\n list is empty");
else
ptr=header->link;
while(ptr->rno!=key && ptr->link!=NULL)
count++;
ptr=ptr->link;
if(ptr->link==NULL)
{
printf("\n such key not in the list ");
else
printf("\n such key found in the list at position %d",count);
Advantages
• They are a dynamic in nature which allocates the memory when required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.
Disadvantages
• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in singly linked list.
Applications
• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don’t need to know the size in advance.
