Linked Lists 2

Linked Lists

Reversing A Linked List

How about reversing the links in the existing linked list such that the last node becomes the first node and the first becomes the last? Here is a program which shows how this reversal of links can be achieved.

 

#include "alloc.h"

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

struct node

{

int data ;

struct node *link ;

} ;

reverse ( struct node ** ) ;

main( )

{

struct node *p ;

p = NULL ; /* empty linked list */

addatbeg ( &p, 1 ) ;

addatbeg ( &p, 2 ) ;

addatbeg ( &p, 3 ) ;

addatbeg ( &p, 4 ) ;

addatbeg ( &p, 5 ) ;

addatbeg ( &p, 6 ) ;

clrscr( ) ;

display ( p ) ;

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;

reverse ( &p ) ;

display ( p ) ;

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;

}

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

addatbeg ( struct node **q, int num )

{

struct node *temp ;

/* add new node */

temp = malloc ( sizeof ( struct node ) ) ;

temp -> data = num ;

temp -> link = *q ;

*q = temp ;

}

reverse ( struct node **x )

{

struct node *q, *r, *s ;

q = *x ;

r = NULL ;

/* trasverse the entire linked list */

while ( q != NULL )

{

s = r ;

r = q ;

q = q -> link ;

r -> link = s ;

}

*x = 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 ;

}

In reverse( ) two variables s and r of type struct node* play an important role for reversing the links of the existing linked list. The variable q also of type struct node* is used to traverse the linked list till the end. While traversing the linked list, r stores address of current node and s stores the address of the previous node. Subsequently, the link part of the node to which r points is assigned the value stored in s. Finally, the last node is made the head node as you see in the last statement in reverse( ).