A singly linked list is one in which one node points to the next node and so on, where node contains an information part and an address to the next node of the same type.  The concept of linked list may be illustrated using the following figure: A singly linked list is uni-directional.  That is, the first node points to the next node, but the next node does not contain the address of the previous node.  Thus such lists can be easily traversed and operated upon from left to right i.e in one direction.  Though, manipulations to the above may result in the other way traversal also, which is discussed in further sections.

A linked list is represented by a structure in ‘C’, which is generally composed of two parts, first part is the information part and the other part is the address of the next node pointed to be the previous node.  Thus such a structure results in a self-referential structure.  The structure definition is as follows:

struct list
{int info;
struct list *next;
};

A global variable head is declared, which is considered to be the first node of the linked list.  However, you may also declare head as a local variable to main function, but that requires passing head as an argument to each function for operating upon the linked list and returning the same from within the function, whereas, global definition avoids this condition of passing head as an argument and returning head pointer.

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

/*In-order traversal*/

{
list *temp;
{printf(“nList is empty.”);
return;
}

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*/

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

for(i=1;i<=count;i++)
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*/
{
list *temp;
{printf(“nList is empty.”);
return;
}
/*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;
}
}

Sorted searchIn 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*/
{
list *temp;
{printf(“List is empty.”);
return;
}

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

Insertion:

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

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

/*Insertion at beginning*/
{
list *temp,*ptr=makenode(x);
}
else
}
}

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 *temp,*ptr=makenode(x);
}
else
while(temp->next!=NULL)
temp=temp->next;
temp->next=ptr;
}
}

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 *temp,*ptr=makenode(x);
{printf(“nGiven node does not exist. List empty”);
}
else
while(temp->n!=node)
temp=temp->next;
if(temp==NULL)
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}

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 *temp,*ptr=makenode(x);
{printf(“nGiven node does not exist. List empty”);
}
else
}
else
while(temp->next->n!=node)
temp=temp->next;
if(temp==NULL)
}
else
{ptr->next=temp->next;
temp->next=ptr;
}
}
}
}

Deletion:

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

Deletion at beginning:

/*function to delete first node*/
{list *temp;
{printf(“nList is empty!”);
}
free(temp);
}

Deletion at end:

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

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 *temp,*ptr;
{printf(“nList is empty.”);
}
/*locate given node in the list*/
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
}
ptr=temp->next;
temp->next=ptr->next;
free(ptr);
}

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 *temp,*temp1,*ptr;
{printf(“nList is empty.”);
}
{printf(“nCannot delete before first node.”);
}
/*locate given node in the list*/
while((temp->next->n!=node) && (temp!=NULL))
{temp1=temp;
temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist in the list.”);
}
ptr=temp1->next;
temp1->next=ptr->next;
free(ptr);
}

Reversing list:

/*Reversing list*/
{
int i,j,count=0;
{printf(“nList is empty.”);
}
for(i=1;i<=count;i++)
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;
}
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
printf(“bb “);
while(temp!=NULL)
{ptr=temp;
temp=temp->next;
free(ptr);
}
}

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

{
list *ptr,*temp;
printf(“nPress any key to continue…”);
free(temp);
}
}

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*/
{
while(temp->next!=NULL)
temp=temp->next;
}

Splitting:

• Middle
• Alternate nodes
• After/Before given node

Splitting at middleThe 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*/
{
int i,count=0;
count++;
/*i is 1 since temp is already at first node*/
for(i=1;i<count/2;i++)
temp=temp->next;
temp->next=NULL;
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
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*/
{
int i;
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp->n;
ptr->next=NULL;
/*creating odd list*/
if(i%2!=0)
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
else /*creating even list*/
else
while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=ptr;
}
}
}
printf(“nAlternate node Splitting list task over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
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*/
while((temp!=NULL)&&(temp->n!=node))
{temp=temp->next;
}
if(temp==NULL)
{printf(“nGiven node does not exist.”);
return;
}
if(temp->n==node)
temp->next=NULL;
}
printf(“nSplit task after given node is over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
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*/
/*if there is only one node*/
if(temp->n==node)
}
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)
temp->next=NULL;
}
}
printf(“nSplit task before given node is over.”);
printf(“nDisplaying first list:”);
printf(“%d->”,temp->n);
printf(“bb “);
printf(“nDisplaying second list:”);
printf(“%d->”,temp->n);
printf(“bb “);
}

MergingMerging 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:

while((temp1!=NULL)&&(temp2!=NULL))
{if(temp1->n<temp2->n)
{
ptr=(list *)malloc(sizeof(list));
ptr->n=temp1->n;
ptr->next=NULL;
else
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;
else
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;
else
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;
else