Maintaining An Ascending Ordered Linked List

 Maintaining An Ascending Ordered Linked ListHow about ensuring that every element added to the linked list gets inserted at such a place that thelinked list is always maintained in ascending order? The following program illustrates the same. And if you know how to maintain a linked list then maintaining it in ascending order is very simple.

#include "alloc.h"

struct node

{

int data ;

} ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

add ( &p, 5 ) ;

add ( &p, 1 ) ;

add ( &p, 6 ) ;

add ( &p, 4 ) ;

add ( &p, 7 ) ;

clrscr( ) ;

display ( p ) ;

printf ( "\nNo. of elements in Linked List = %d", count ( p ) ) ;

delete ( &p, 7 ) ;

delete ( &p, 4 ) ;

delete ( &p, 5 ) ;

delete ( &p, 9 ) ;

display ( p ) ;

printf ( "\nNo. of elements in Linked List = %d", count ( p ) ) ;

}

add ( struct node **q, int num )

{

struct node *r, *temp = *q ;

r = malloc ( sizeof ( struct node ) ) ;

r -> data = num ;

/* if list is empty or if new node is to be inserted before the first node */

if ( *q == NULL || ( *q ) -> data > num )

{

*q = r ;

( *q ) -> link = temp ;

}

else

{

/* traverse the entire linked list to search the position to insert the new node */

while ( temp != NULL )

{

if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ) )

{

temp -> link = r ;

return ;

}

temp = temp -> link ; /* go to the next node */

}

r -> link = NULL ;

temp -> link = r ;

}

}

/* displays the contents of the linked list */

display ( struct node *q )

{

printf ( "\n" ) ;

/* traverse the entire linked list */

while ( q != NULL )

{

printf ( "%d ", q -> data ) ;

q = q -> link ;

}

}

/* counts the number of nodes present in the linked list */

count ( struct node *q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> link ;

c++ ;

}

return c ;

}

/* deletes the specified node from the linked list */

delete ( struct node **q, int num )

{

struct node *old, *temp ;

temp = *q ;

while ( temp != NULL )

{

if ( temp -> data == num )

{

/* if node to be deleted is the first node in the linked list */

if ( temp == *q )

{

*q = temp -> link ;

/* free the memory occupied by the node */

free ( temp ) ;

return ;

}

/* deletes the intermediate nodes in the linked list */

else

{

free ( temp ) ;

return ;

}

}

/* traverse the linked list till the last node is reached */

else

{

old = temp ; /* old points to the previous node */

temp = temp -> link ; /* go to the next node */

}

}