Linked Lists

Linked Lists

Maintaining An Ascending Ordered Linked List

How 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 ;

struct node *link ;

} ;

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 ) ) ;

}

/* adds node to an ascending order linked list */

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 ) )

{

r -> link = temp -> link ;

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

{

old -> link = temp -> link ;

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

}

}

printf ( "\nElement %d not found", num ) ;

}

Have a look at add( ) in the above program. While traversing the linked list the data part of the node to be inserted is compared with that of the current node and that of it's subsequent one and accordingly inserted.