Linked List Using Recursion

This program maintains a linked list using recursive function. addatend( ), display( ), compare( ), copy( ), length( ) are all recursive functions. compare( ) finds out whether the two linked lists possess same elements. copy( ) copies elements from one linked list to another. length( ) counts the number of nodes present in the linked list. But there are some limitations while using recursion. Since there are number of calls to the same function, the program tends to become slow. Also, same type of variables are created recursively at each call. So consumption of memory is considerable. Above all, there is chance of stack overflow if the calls are too many.

#include "alloc.h"

/* structure containing a data part and link part */

struct node

{

int data ;

struct node *link ;

} ;

main ( )

{

struct node *p, *first, *second ;

clrscr( ) ;

p = first = second = NULL ; /* empty linked list */

addatend ( &p, 1) ;

addatend ( &p, 2) ;

addatend ( &p, 3) ;

addatend ( &p, 4) ;

addatend ( &p, 5) ;

display( p ) ;

printf ( "\nLength of linked list = %d\n", length ( p ) ) ;

/* code to compare two linked lists using recursion */

addatend ( &first, 1) ;

addatend ( &first, 2) ;

addatend ( &first, 3) ;

display( first ) ;

addatend ( &second, 1) ;

addatend ( &second, 2) ;

addatend ( &second, 3) ;

display( second ) ;

if ( compare ( first, second ) )

printf ( "\nBoth linked lists are EQUAL" ) ;

else

printf ( "Linked lists are DIFFERENT" ) ;

/* copy one linked list into another */

addatend ( &first, 1) ;

addatend ( &first, 2) ;

addatend ( &first, 3) ;

addatend ( &first, 4) ;

addatend ( &first, 5) ;

addatend ( &first, 6) ;

addatend ( &first, 7) ;

display ( first ) ;

printf ( "\n" ) ;

copy ( first, &second ) ;

display ( second ) ;

printf ( "\n" ) ;

addatend ( &p, 1) ;

addatend ( &p, 2) ;

addatend ( &p, 3) ;

addatend ( &p, 4) ;

addatend ( &p, 5) ;

addatend ( &p, 6) ;

addatend ( &p, 10) ;

display ( p ) ;

}

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

length ( struct node *q )

{

static int l ;

/* if list is empty or if NULL is encountered */

if ( q == NULL )

return ( 0 ) ;

else

{

/* go to next node */

l = 1 + length ( q -> link ) ;

return ( l ) ;

}

}

/* compares 2 linked lists and returns 1 if linked lists are equal and 0 if unequal */

compare ( struct node *q , struct node *r )

{

static int flag ;

if ( ( q == NULL ) && ( r == NULL ) )

flag = 1 ;

else

{

if ( q == NULL || r == NULL )

flag = 0 ;

if ( q -> data != r -> data)

flag = 0 ;

else

compare ( q -> link, r -> link ) ;

}

return ( flag ) ;

}

/* copies a linked list into another */

copy ( struct node *q, struct node **s )

{

if ( q != NULL )

{

*s = malloc ( sizeof ( struct node ) ) ;

( *s ) -> data = q -> data ;

( *s ) -> link = NULL ;

copy ( q->link, & ( ( *s ) -> link ) ) ;

}

}

/* displays the contents of the linked list */

display ( struct node * q )

{

if ( q != NULL )

{

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

display ( q -> link ) ;

}

else

return ;

}

/* adds a new node at the end of the linked list */

addatend ( struct node **s, int num )

{

if ( *s == NULL )

{

*s = malloc ( sizeof ( struct node ) ) ;

( *s ) -> data = num ;

( *s ) -> link = NULL ;

}

else

addatend ( &( ( *s) -> link ), num ) ;

}