How to sort a singly linked list?

Sorting a singly linked is simple. Find the method below for the same.

/* a function to sort a list */
struct node *sortlist(struct node *p)
{
        struct node *temp1,*temp2,*min,*prev,*q;
        q = NULL;
        while(p != NULL)
        {
                prev = NULL;
                min = temp1 = p;
                temp2 = p -> link;
                while ( temp2 != NULL )
                {
                        if(min -> data > temp2 -> data)
                        {
                                min = temp2;
                                prev = temp1;
                        }
                        temp1 = temp2;
                        temp2 = temp2-> link;
                }
                if(prev == NULL)
                        p = min -> link;
                else
                        prev -> link = min -> link;
                min -> link = NULL;
                if( q == NULL)
                        q = min; /* moves the node with lowest data value in the list
                                    pointed to by p to the list
                                    pointed to by q as a first node*/
                else
                {
                        temp1 = q;
                        /* traverses the list pointed to by q to get pointer to its
                           last node */
                        while( temp1 -> link != NULL)
                                temp1 = temp1 -> link;
                        temp1 -> link = min; /* moves the node with lowest data value
                                                in the list pointed to
                                                by p to the list pointed to by q at the end of list pointed by
                                                q*/
                }
        }

How to insert a node in a sorted linked list?

To insert a new node into an already sorted list, we compare the data value of the node to be inserted with the data values of the nodes in the list starting from the first node. This is continued until we get a pointer to the node that appears immediately before the node in the list whose data value is greater than the data value of the node to be inserted.

/* a function to sort a list */
struct node *sortlist(struct node *p)
{
        struct node *temp1,*temp2,*min,*prev,*q;
        q = NULL;
        while(p != NULL)
        {
                prev = NULL;
                min = temp1 = p;
                temp2 = p -> link;
                while ( temp2 != NULL )
                {
                        if(min -> data > temp2 -> data)
                        {
                                min = temp2;
                                prev = temp1;
                        }
                        temp1 = temp2;
                        temp2 = temp2-> link;
                }
                if(prev == NULL)
                        p = min -> link;
                else
                        prev -> link = min -> link;
                min -> link = NULL;
                if( q == NULL)
                        q = min; /* moves the node with lowest data value in the list
                                    pointed to by p to the list
                                    pointed to by q as a first node*/
                else
                {
                        temp1 = q;
                        /* traverses the list pointed to by q to get pointer to its
                           last node */
                        while( temp1 -> link != NULL)
                                temp1 = temp1 -> link;
                        temp1 -> link = min; /* moves the node with lowest data value
                                                in the list pointed to
                                                by p to the list pointed to by q at the end of list pointed by
                                                q*/
                }
        }
        return (q);
}

How to insert a node after a specified node in a linked list?

To insert a new node after the specified node in a singly linked list, first we get the number of the node in an existing singly linked list after which the new node is to be inserted. This is based on the assumption that the nodes of the list are numbered serially from 1 to n. The list is then traversed to get a pointer to the node, whose number is given. If this pointer is x, then the link field of the new node is made to point to the node pointed to by x, and the link field of the node pointed to by x is made to point to the new node.

Figure 1 and  2 show the list before and after the insertion of the node, respectively.

/* a function which inserts a newly created node after the specified
   node */
struct node * newinsert ( struct node *p, int node_no, int value )
{
        struct node *temp, * temp1;
        int i;
        if ( node_no <= 0 || node_no > length (p))
        {
                printf("Error! the specified node does not exist\n");
                exit(0);
        }
        if ( node_no == 0)
        {
                temp = ( struct node * )malloc ( sizeof ( struct node ));
                if ( temp == NULL )
                {
                        printf( " Cannot allocate \n");
                        exit (0);
                }
                temp -> data = value;
                temp -> link = p;
                p = temp ;
        }
        else
        {
                temp = p ;
                i = 1;
                while ( i < node_no )
                {
                        i = i+1;
                        temp = temp-> link ;
                }
                temp1 = ( struct node * )malloc ( sizeof(struct node));
                if ( temp == NULL )
                {
                        printf ("Cannot allocate \n");
                        exit(0)
                }
                temp1 -> data = value ;
                temp1 -> link = temp -> link;
                temp -> link = temp1;
        }
        return (p);
}

Linked List before Insertion of the new node

Linked List after Insertion of the new node

How to insert a node in a linked list recursively?

A linked list is a recursive data structure. A recursive data structure is a data structure that has the same form regardless of the size of the data. If you haven’t already gone through the concepts of a linked list, I recommend you to go through my previous article on linked list first.

The recursive method for inserting a node in a singly linked list is simple and given below:

struct node *insert(struct node *p, int n)
{
        struct node *temp;
        if(p==NULL)
        {
                p=(struct node *)malloc(sizeof(struct node));
                if(p==NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                p-> data = n;
                p-> link = NULL;
        }
        else
                p->link = insert(p->link,n);/* the while loop replaced by
                                               recursive call */
        return (p);
}

Deleting a node from doubly linked list

How do you delete a node from doubly linked list? This is basically manipulations of links and freeing the memory for deleted node. If you are not already familiar with concepts of doubly linked lists, I would recommend you go through that first.

Deleting a node from doubly linked list.

struct dnode * delete( struct dnode *p, int node_no, int *val)
{
        struct dnode *temp ,*prev=NULL;
        int i;
        if ( node_no <= 0 || node_no > nodecount (p))
        {
                printf("Error! the specified node does not exist\n");
                exit(0);
        }
        if ( node_no == 0)
        {
                temp = p;
                p = temp->right;
                p->left = NULL;
                *val = temp->data;
                return(p);
        }
        else
        {
                temp = p ;
                i = 1;
                while ( i < node_no )
                {
                        i = i+1;
                        prev = temp;
                        temp = temp-> right ;
                }
                prev->right = temp->right;
                if(temp->right != NULL)
                        temp->right->left = prev;
                *val = temp->data;
                free(temp);
        }
        return (p);
}