Sorted linked list – Insertion of elements & Removal of duplicate elements

Since we covered the basics of linked list in the previous post, let’s work on an exercise that would help us to have a good grasp on linked list. Let us see on how to insert elements into a sorted linked list and remove duplicate elements from a sorted linked list.
In this post I’m gonna cover three major functions that can be performed on a linked list

1. Insertion of elements into a singly linked list in a sorted order
2. Printing the elements of a singly linked list
3. Removing duplicate nodes from a sorted linked list

Code :

#include <stdio.h>
#include<stdlib.h>

/*create a node that has a data and link to the next node*/
struct node{

int data;
struct node* next;
};
/*Function 1 :Inserting nodes to a linked list in a sorted order */
void insert(struct node** head, struct node* newnode)
{
struct node* run;
/* case 1: Inserting first node , Check if head is NULL
case 2: The node to be inserted is lesser than the head node*/
if (*head == NULL || (*head)->data >= newnode->data)
{
newnode->next = *head;
*head = newnode;
}
/*Inserting nodes in their right positions, by traversing the linked list */
else
{

run = *head;

while (run->next!=NULL && run->next->data < newnode->data)
{
run = run->next;
}
newnode->next = run->next;
run->next = newnode;
}
}
/*Function2: Remove duplicates by comparing a node with its next node*/
void remove_duplicates(struct node* head)
{
struct node* run=(struct node*)malloc(sizeof(struct node));
struct node* next=(struct node*)malloc(sizeof(struct node));
run=head;
next=run->next;
if(run==NULL)
return;
while(run->next!=NULL)
{
if(run->data==run->next->data)
{

/*when both the nodes have the same data, link the current node to the node one after*/
run->next=next->next;

free(next);
next=run->next;
}

else
{
run=run->next;
next=next->next;
}

}
}
/*Function 3: Print every element in the linked list*/
void traverse(struct node *run)
{
/*traversing from head node to last node*/
while(run!=NULL)
{
printf(“%d-> “, run->data);
run = run->next;
}
printf(“NULL”);
}
/*Allocating memory and data to a node*/
struct node* Newnode(int data)
{
struct node* newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=data;
newnode->next=NULL; //its a good practice to assign NULL to the next pointer
return (newnode);
}
main()
{
struct node* head=(struct node*)malloc(sizeof(struct node));
struct node* newnode;
head=NULL;
newnode=Newnode(1);
insert(&head,newnode);
newnode=Newnode(5);
insert(&head,newnode);
newnode=Newnode(3);
insert(&head,newnode);
newnode=Newnode(8);
insert(&head,newnode);
newnode=Newnode(11);
insert(&head,newnode);
newnode=Newnode(9);
insert(&head,newnode);
newnode=Newnode(2);
insert(&head,newnode);
newnode=Newnode(7);
insert(&head,newnode);
newnode=Newnode(9);
insert(&head,newnode);
newnode=Newnode(2);
insert(&head,newnode);
newnode=Newnode(7);
insert(&head,newnode);
newnode=Newnode(3);
insert(&head,newnode);
newnode=Newnode(3);
insert(&head,newnode);
printf(“\n Linked list after inserting all the elements\n “);
traverse(head);
printf(“\n”);
printf(“\n….Removing duplicate elements….. \n “);
remove_duplicates(head);

printf(“\n Linked list after removing duplicates from the list\n “);
traverse(head);

}
OUTPUT:

Linked list after inserting all the elements
1-> 2-> 2-> 3-> 3-> 3-> 5-> 7-> 7-> 8-> 9-> 9-> 11-> NULL

….Removing duplicate elements…..

Linked list after removing duplicates from the list
1-> 2-> 3-> 5-> 7-> 8-> 9-> 11-> NULL
Thats it. try on with many such functions on linked list. Any doubts, leave me a comment…
“Happy coding!!!”

 

Latest posts by abirami vijayakumar (see all)

Leave a Reply

Your email address will not be published. Required fields are marked *