The task of inserting a value into the current location in a sorted
linked list involves two operations:
1.
Finding the node before which
the new node has to be inserted. We
call this node as ‘Key node’.
2.
Creating a new node with the
value to be inserted and inserting the new node by manipulating pointers
appropriately.
In order to illustrate the process of insertion, we use a sorted
linked list created by the create function discussed in Example 13.3. Figure 13.11 shows a complete program that
creates a list (using sorted input data) and then inserts a given value into
the correct place using function insert.
INSERTING A NUMBER IN A SORTED LIST
Program
#include <stdio.h>
#include<stdio.h>
#define NULL 0
struct linked_list
{
int
number;
struct
linked-list *next;
};
typedef struct linked_lit node;
main()
{
int n;
node
*head;
void
create(node *p);
node
*insert(node *p, int n);
void
print(node *p);
head =
(node *)malloc(sizeof(node));
create(head);
printf(“\n”);
printf(“Original
list: “);
print(head);
printf(“\n\n”);
printf(“Input
number to be inserted: “);
scanf(“%d”,
&n);
head =
inert(head,n);
printf(“\n”);
printf(“New
list: “);
print(head);
}
void create(node *list)
{
printf(“Input
a number \n”);
printf(“(type
–999 at end): “);
scanf(“%d”,
&list->number);
if(list->number
== -999)
{
list->next
= NULL;
}
else /* create next node */
{
list->next
= (node *)malloc(sizeof(node));
create(list->next);
}
return:
}
void print(node *list)
{
if(list->next
!= NULL)
{
printf(“%d
-->”, list->number);
if(list
->next->next = = NULL)
printf(“%d”,
list->next->number);
print(list->next);
}
return:
}
node *insert(node *head, int x)
{
node *p1,
*p2, *p;
p1 =
NULL;
p2 =
head; /* p2 points to first node */
for( ;
p2->number < x; p2 = p2->next)
{
p1 =
p2;
if(p2->next->next
== NULL)
{
p2
= p2->next; /* insertion at end */
break;
}
}
/*key
node found and insert new node */
p =
(node )malloc(sizeof(node)); / space for new node */
p->number
= x; /* place value in the new node */
p->next
= p2; /*link new node to key node */
if (p1
== NULL)
head
= p; /* new node becomes the first node */
else
p1->next
= p; /* new node inserted in middle */
return
(head);
}
Output
Input a number
(type –999 at end ); 10
Input a number
(type –999 at end ); 20
Input a number
(type –999 at end ); 30
Input a number
(type –999 at end ); 40
Input a number
(type –999 at end ); -999
Original list: 10
-->20-->30-->40-->-999
Input number to be inserted: 25
New list:
10-->20-->25-->30-->40-->-999
No comments:
Post a Comment