Singly Linked List

In-order traversal:  The function for traversing a linked list in In-order way is as follows:

 /*In-order traversal*/

void displaylist(list *head)
{
list *temp;
if(head==NULL)
{printf(“nList is empty.”);
return;
}

temp=head;

while(temp!=NULL)
{printf(“%d->”,temp->n);
temp=temp->next;
}

printf(“bb  “);
}

Reverse-order traversal:  For reading a linked list in reverse order, we can use any of the methods, such as reading last element in first scan, second last element in second scan, where number of scans is equal to the total number of elements in the linked list or by maintaining an array of pointers that point to each node of the linked list and using this array of pointers read the linked list in reverse order.

The function for traversing/ reading a linked list in reverse order is as follows:

/*Reverse order traversal*/

void displaylistreverse(list *head)
{
list *temp;
int i,j,count=0;
if(head==NULL)
{printf(“nList is empty.”);
return;
}

for(temp=head;temp!=NULL;temp=temp->next,count++);

for(i=1;i<=count;i++)
{temp=head;
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
}
printf(“bb  “);
}

Unsorted search:  Search is the process of searching an element in a given linked list.  Search process may be sorted as well as unsorted.  Unsorted search means search is performed in a linked list containing elements that are not sorted.  Thus sorting operation must be performed for n nodes of a linked list.

The ‘C’ function for unsorted search is as follows:

/*UnSorted search on an unsorted list*/
void unsortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“nList is empty.”);
return;
}
temp=head;
/*searches for equality until number is found*/
/*best case is when first number is the required number*/
/*worst case is number does not exist*/
/*or number is present at last position in list*/
while(temp!=NULL)
{if(temp->n==val)
{printf(“nNumber found.”);
return;
}
temp=temp->next;
}
printf(“nNumber not found.”);
}

Sorted search:  In case of sorted search, there are two cases.  If the linked list is sorted in ascending order, as soon as the number to be searched becomes smaller than the element in the linked list, search process terminates without resuming upto n elements.  On the other hand, if the linked list is sorted in descending order, then while scanning from the first element onwards, as soon as the number to be searched becomes greater than the element in the linked list, the search process terminates.  Thus efficiency of a sorted search is higher as compared to that of unsorted search for a given set of numbers.

The function to perform sorted search is as follows:

/*Sorted search on a list sorted in ascending order*/
void sortedsearch(list *head,int val)
{
list *temp;
if(head==NULL)
{printf(“List is empty.”);
return;
}
temp=head;

while((temp->n!=val) && (val>temp->n) && (temp!=NULL))
temp=temp->next;
if(temp->n==val)
printf(“nNumber found.”);
else
printf(“nNumber not found.”);
}

Insertion:

• Beginning
• End
• After given element/node
• Before given element/node

Insertion at Beginning:  The ‘C’ function is as follows:

/*Insertion at beginning*/
list *insertbegin(list *head,int x)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{ptr->next=head;
head=ptr;
}
return head;
}

Insertion at End:  For inserting an element at the end of the linked list, we must take a temp pointer that points to the head node (first node of the linked list) and moves forwards until the next node of temp becomes NULL.  After temp pointer is positioned at the last element, new node may be inserted by setting appropriate pointers as follows:

/*Insertion at end*/
list *insertend(list *head,int x)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{head=ptr;
}
else
{temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
return head;
}

Insertion after given node:  For inserting an element after a given node, we must search that element in the list.  If that element is not found, error is reported, otherwise the new element is inserted after the searched element by setting pointers which are shown in the following function:

/*Insertion after given element/node*/
list *insertafternode(list *head,int x,int node)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{printf(“nGiven node does not exist. List empty”);
}
else
{temp=head;
while(temp->n!=node)
temp=temp->next;
if(temp==NULL)
{printf(“nGiven node not found in list.”);
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
return head;
}

Insertion before given node:  If you wish to insert a new node before a given node, then locate the node before which you wish to insert and maintain the address of its previous node.  Once this is done, this case becomes similar to that of insertion after a given node, by considering the pointer to the previous node of the searched node.  The ‘C’ function is as follows:

/*Insertion before given element/node*/
list *insertbeforenode(list *head,int x,int node)
{
list *temp,*ptr=makenode(x);
if(head==NULL)
{printf(“nGiven node does not exist. List empty”);
}
else
{if(head->n==node)
{ptr->next=head;
head=ptr;
return head;
}
else
{temp=head;
while(temp->next->n!=node)
temp=temp->next;
if(temp==NULL)
{printf(“nGiven node not found in list.”);
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}
return head;
}

 

Deletion:

• Beginning
• End
• After given element/node
• Before given element/node

Deletion at beginning:

/*function to delete first node*/
list *delfirstnode(list *head)
{list *temp;
if(head==NULL)
{printf(“nList is empty!”);
return head;
}
temp=head;
head=head->next;
free(temp);
return head;
}

Deletion at end:

/*function to delete last node*/
list *dellastnode(list *head)
{list *ptr,*temp;
if(head==NULL)
{printf(“nList is empty!”);
return head;
}
if(head->next==NULL)
{temp=head;
head=NULL;
free(temp);
return head;
}
temp=head;
if(temp->next->next==NULL)
{ptr=temp->next;
temp->next=NULL;
free(ptr);
return head;
}
while(temp->next->next!=NULL)
temp=temp->next;
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
return head;
}

Deletion after a given node:  To delete a node after a given node, input the node after which you wish to delete.  Then, locate that node in the linked list.  If that node is not found in the list, report an error, otherwise place a pointer temp on that node.  Perform deletion of the next node by setting appropriate pointers.

/*function to delete node after a given node*/
list *delafternode(list *head,int node)
{
list *temp,*ptr;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
/*locate given node in the list*/
for(temp=head;((temp->n!=node) && (temp!=NULL));temp=temp->next);
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
return head;
}
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
return head;
}

Deletion before a given node:  To delete a node before a given node, input the node before which you wish to delete.  Locate that node in the list and place two pointers, one on the node before given node and other before the node to be deleted.  Then perform necessary pointer adjustments for deleting the node before the given node as follows:

/*function to delete node before a given node*/
list *delbeforenode(list *head,int node)
{
list *temp,*temp1,*ptr;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->n==node)
{printf(“nCannot delete before first node.”);
return head;
}
/*locate given node in the list*/
temp=head;
while((temp->next->n!=node) && (temp!=NULL))
{temp1=temp;
temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
return head;
}
ptr=temp1->next;
temp1->next=ptr->next;
free(ptr);
return head;
}

Reversing list:

/*Reversing list*/
list *reverselist(list *head)
{
list *temp,*head1=NULL,*ptr,*temp1;
int i,j,count=0;
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
for(temp=head;temp!=NULL;temp=temp->next,count++);
for(i=1;i<=count;i++)
{temp=head;
for(j=1;j<=count-i;j++)
{temp=temp->next;
}
printf(“%d->”,temp->n);
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
if(head1==NULL)
{head1=ptr;
}
else
{temp1=head1;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
printf(“bb “);
temp=head;
while(temp!=NULL)
{ptr=temp;
temp=temp->next;
free(ptr);
}
return head1;
}

Disposing list:  Disposing a linked list means removing all the elements of the linked list.  The function is as follows:

/*Disposing linked list*/
list *dispose(list *head)
{
list *ptr,*temp;
printf(“nDisposing the linked list.”);
printf(“nPress any key to continue…”);
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}

Concatenation:  The concatenation operation results in combining two lists such that the second list is attached at the last nodal point of the first list.  The ‘C’ function for concatenation is as follows:

/*Concatenating list*/
list *concatenate(list *head1,list *head2)
{
list *temp=head1;
while(temp->next!=NULL)
temp=temp->next;
temp->next=head2;
return head1;
}

Splitting:

• Middle
• Alternate nodes
• After/Before given node

Splitting at middle:  The splitting at middle involves dividing a given linked list into two equal parts.  However, if the odd number of nodes are present in the list, then it is splitted from the node which is achieved by dividing the size of the list by 2.  The ‘C’ function to split the node from the middle is as follows:

/*Splitting from middle*/
void splitmiddle(list *head)
{
list *head1=NULL,*temp;
int i,count=0;
for(temp=head;temp!=NULL;temp=temp->next)
count++;
temp=head;
/*i is 1 since temp is already at first node*/
for(i=1;i<count/2;i++)
temp=temp->next;
head1=temp->next;
temp->next=NULL;
printf(“nSplitting list task over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}

Splitting alternate nodes:  The split operation at alternate nodes results in creating two lists – an odd list and an even list.  The odd list contains nodes at position 1, 3, 5 and so on, whereas an even list contains nodes at position 2, 4, 6 and so on.  The ‘C’ function to split a given linked list at alternate nodes is as follows:

/*Splitting alternate nodes*/
void splitalternatenodes(list *head)
{
list *head1=NULL,*head2=NULL,*temp,*temp1,*ptr;
int i;
for(i=1,temp=head;temp!=NULL;temp=temp->next,i++)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
/*creating odd list*/
if(i%2!=0)
{if(head1==NULL)
head1=ptr;
else
{temp1=head1;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
else /*creating even list*/
{if(head2==NULL)
head2=ptr;
else
{temp1=head2;
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
}
printf(“nAlternate node Splitting list task over.”);
printf(“nDisplaying first list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head2;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}

Splitting after given element/node:  The node after which the deletion operation is to be performed is taken as an input from the user.  This node is located in the linked list.  The node next to located node, if it exists, is removed by appropriate pointer adjustments.  If the given node does not exist in the list, an error is flashed.  The ‘C’ function is as follows:

/*Splitting after a given node*/
void splitafternode(list *head,int node)
{list *temp,*head1=NULL;
temp=head;
while((temp!=NULL)&&(temp->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->n==node)
{head1=temp->next;
temp->next=NULL;
}
printf(“nSplit task after given node is over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}

Splitting before given element/node:  The node before which deletion is to be performed is taken as an input.  Then the next node from head is searched for this node.  Two pointers one on previous to given node and other to previous to previous is maintained.  If the node is found, then deletion is performed by setting pointers appropriately and freeing the memory for the deleted node.  The ‘C’ function is as follows:

/*Split before given node*/
void splitbeforenode(list *head,int node)
{list *temp,*head1=NULL;
temp=head;
/*if there is only one node*/
if(temp->n==node)
{head1=temp;
head=NULL;
}
else
{
while((temp!=NULL)&&(temp->next->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->next->n==node)
{head1=temp->next;
temp->next=NULL;
}
}
printf(“nSplit task before given node is over.”);
printf(“nDisplaying first list:”);
for(temp=head;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
for(temp=head1;temp!=NULL;temp=temp->next)
printf(“%d->”,temp->n);
printf(“bb “);
}

Merging:  Merging two sorted lists is the process of combining two lists such that the resultant list is also sorted.  For example: consider list one as {1,3,5,7} and list two as {2,4,6,8}.  Then merging of both these lists result in a third list that contains the following elements: {1,2,3,4,5,6,7,8}.  The ‘C’ function to perform merging is given below:

list *merge(list *head1,list *head2)
{list *head=NULL,*temp1,*temp2,*ptr,*tmp;
temp1=head1;
temp2=head2;
while((temp1!=NULL)&&(temp2!=NULL))
{if(temp1->n<temp2->n)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
else
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
}
while(temp1!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp1=temp1->next;
}
while(temp2!=NULL)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp2->n;
ptr->next=NULL;
if(head==NULL)
head=ptr;
else
{tmp=head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
temp2=temp2->next;
}
return head;
}
 
Program for operations on a Singly Linked List