I have a code for a doubly linked list, and I need to print it in reverse. I can't seem to figure out what I'm doing wrong, or maybe I just don't fully understand what I'm doing.

The part that I'm questioning is in the printList function. The while statement seems to never be true, so nothing ever gets printed. I tried adding the line currentPtr = currentPtr->prev , but my program crashes when I do. I'm guessing that it has something to do with currentPtr being NULL before I attempt to print the list backwards, but I have no idea how to fix it. How do I get the program to step backwards in the list and print it?

#include <stdio.h>
#include <stdlib.h>


struct node
{
char data;
struct node *next,*prev;

} *head=NULL, *tail=NULL, *newnode ,*Traverse;

typedef struct node ListNode; 
typedef ListNode *ListNodePtr;
typedef struct Node *NodePtr;


void insert( ListNodePtr *sPtr, char value );
char delete( ListNodePtr *sPtr, char value );
int isEmpty( ListNodePtr sPtr );
void printList( ListNodePtr currentPtr );
void instructions( void );

int main( void )
{ 
   ListNodePtr startPtr = NULL; 
   int choice; 
   char item;  

   instructions();
   printf( "? " );
   scanf( "%d", &choice );

   
   while ( choice != 3 ) { 

      switch ( choice ) { 

         case 1:
            printf( "Enter a character: " );
            scanf( "\n%c", &item );
            insert( &startPtr, item );
            printList( startPtr );
            break;

         case 2:

            
            if ( !isEmpty( startPtr ) ) { 
               printf( "Enter character to be deleted: " );
               scanf( "\n%c", &item );

            
               if ( delete( &startPtr, item ) ) { 
                  printf( "%c deleted.\n", item );
                  printList( startPtr );
               } 
                  else {
                  printf( "%c not found.\n\n", item );
               } 

            } 
            else {
               printf( "List is empty.\n\n" );
            } 

            break;

         default:
            printf( "Invalid choice.\n\n" );
            instructions();
            break;
      
      } 

      printf( "? " );
      scanf( "%d", &choice );
   } 

   printf( "End of run.\n" );
   
   return 0; 

} 


void instructions( void )
{ 
   printf( "Enter your choice:\n"
      "   1 to insert an element into the list.\n"
      "   2 to delete an element from the list.\n"
      "   3 to end.\n" );
} 


void insert( ListNodePtr *sPtr, char value )
{ 
   ListNodePtr newPtr;     
   ListNodePtr previousPtr; 
   ListNodePtr currentPtr;  

   newPtr = malloc( sizeof( ListNode ) );

   if ( newPtr != NULL ) { 
      newPtr->data = value; 
      newPtr->next = NULL; 

      previousPtr = NULL;
      currentPtr = *sPtr;

  
      while ( currentPtr != NULL && value > currentPtr->data ) { 
         previousPtr = currentPtr;          
         currentPtr = currentPtr->next; 
      } 

      
      if ( previousPtr == NULL ) { 
         newPtr->next = *sPtr;
         *sPtr = newPtr;
      } 
      else { 
         previousPtr->next = newPtr;
         newPtr->next = currentPtr;
      } 
   
   } 
   else {
      printf( "%c not inserted. No memory available.\n", value );
   } 

} 


char delete( ListNodePtr *sPtr, char value )
{ 
   ListNodePtr previousPtr; 
   ListNodePtr currentPtr;  
   ListNodePtr tempPtr;     
  
   


   if ( value == ( *sPtr )->data ) { 
      tempPtr = *sPtr; 
      *sPtr = ( *sPtr )->next; 
      free( tempPtr ); 
      return value;
   } 
   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->next;

     
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr;         
         currentPtr = currentPtr->next; 
      } 

      
      if ( currentPtr != NULL ) { 
         tempPtr = currentPtr;
         previousPtr->next = currentPtr->next;
         free( tempPtr );
         return value;
      } 
     
   }

   return '\0';

} 




int isEmpty( ListNodePtr sPtr )
{ 
   return sPtr == NULL;

} 


void printList( ListNodePtr currentPtr )
{ 

 ListNodePtr startPtr = NULL;
 
   
   if ( currentPtr == NULL ) {
      printf( "List is empty.\n\n" );
   
   } 
   else { 
      {printf( "The list is:\n" );

      while ( currentPtr != NULL ) { 
         printf( "%c --> ", currentPtr->data );
         currentPtr = currentPtr->next;}
      
      printf( "NULL\n" );
      


{ printf( "\nThe list in reverse is:\n" );

printf( "NULL" );
      
      
         while ( currentPtr != NULL ) { 
         printf( " <-- %c", currentPtr->data );
         currentPtr = currentPtr->prev;   
         
         }
         
         printf("\n\n");


}
} 
}    
}

You are coding doubly link list, and not taking care of prev pointer while inserting new items.

You have not type casted malloc.

You have used delete as function name, whic is wrong as delete is keyword. I have changed it.

In printList function, when u are printing list in forward direction u are making the currentPtr = NULL and again u are looping it in while like this:

while(currentPtr!=NULL)

it is already turned to NULL.:)


There many errors I have corrected, Please check it carefully.

Hope to work!!

#include <stdio.h>
#include <stdlib.h>


struct node
{
char data;
struct node *next,*prev;

} *head=NULL, *tail=NULL, *newnode ,*Traverse;

typedef struct node ListNode;
typedef ListNode *ListNodePtr;
typedef struct Node *NodePtr;


void insert( ListNodePtr *sPtr, char value );
char deleteNode( ListNodePtr *sPtr, char value );
int isEmpty( ListNodePtr sPtr );
void printList( ListNodePtr *currentPtr );
void instructions( void );

int main( void )
{
   ListNodePtr startPtr = NULL;
   int choice;
   char item;

   instructions();
   printf( "? " );
   scanf( "%d", &choice );


   while ( choice != 3 ) {

	  switch ( choice ) {

		 case 1:
			printf( "Enter a character: " );
			scanf( "\n%c", &item );
			insert( &startPtr, item );
			printList( &startPtr );
			break;

		 case 2:


			if ( !isEmpty( startPtr ) ) {
			   printf( "Enter character to be deleted: " );
			   scanf( "\n%c", &item );


			   if (deleteNode( &startPtr, item ) ) {
				  printf( "%c deleted.\n", item );
				  printList( &startPtr );
			   }
				  else {
				  printf( "%c not found.\n\n", item );
			   }

			}
			else {
			   printf( "List is empty.\n\n" );
			}

			break;

		 default:
			printf( "Invalid choice.\n\n" );
			instructions();
			break;

	  }

	  printf( "? " );
	  scanf( "%d", &choice );
   }

   printf( "End of run.\n" );

   return 0;

}


void instructions( void )
{
   printf( "Enter your choice:\n"
	  "   1 to insert an element into the list.\n"
	  "   2 to delete an element from the list.\n"
	  "   3 to end.\n" );
}


void insert( ListNodePtr *sPtr, char value )
{
   ListNodePtr newPtr;
   ListNodePtr previousPtr;
   ListNodePtr currentPtr;

   newPtr =(ListNodePtr) malloc( sizeof( ListNode ) );

   if ( newPtr != NULL ) {
	  newPtr->data = value;
	  newPtr->next = NULL;

	  previousPtr = NULL;
	  currentPtr = *sPtr;


	  while ( currentPtr != NULL && value > currentPtr->data ) {
		 previousPtr = currentPtr;
		 currentPtr = currentPtr->next;
		
	  }


	  if ( previousPtr == NULL ) {
		newPtr->next = *sPtr;
		 (*sPtr)->prev = newPtr;
		  newPtr->prev = NULL;
		 *sPtr = newPtr;

	  }
	  else {
		 previousPtr->next = newPtr;
		 newPtr->next = currentPtr;
		currentPtr->prev = newPtr;
		 newPtr->prev = previousPtr;
	  }

   }
   else {
	  printf( "%c not inserted. No memory available.\n", value );
   }

}


char deleteNode( ListNodePtr *sPtr, char value )
{
   ListNodePtr previousPtr;
   ListNodePtr currentPtr;
   ListNodePtr tempPtr;

   


   if ( value == ( *sPtr )->data ) { 
      tempPtr = *sPtr; 
      *sPtr = ( *sPtr )->next; 
      free( tempPtr ); 
      return value;
   } 
   else { 
      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->next;

     
      while ( currentPtr != NULL && currentPtr->data != value ) { 
         previousPtr = currentPtr;         
         currentPtr = currentPtr->next; 
      } 

      
      if ( currentPtr != NULL ) { 
         tempPtr = currentPtr;
         previousPtr->next = currentPtr->next;
         free( tempPtr );
         return value;
      } 
     
   }

   return '\0';

} 




int isEmpty( ListNodePtr sPtr )
{ 
   return sPtr == NULL;

} 


void printList(ListNodePtr *currentPtr )
{

   ListNodePtr startPtr = *currentPtr,temp=NULL;


   if ( startPtr == NULL ) {
	  printf( "List is empty.\n\n" );

   }
   else {
	  {printf( "The list is:\n" );

	  while ( startPtr != NULL ) {
		 printf( "%c --> ", startPtr->data );
		 temp = startPtr;
		 startPtr = startPtr->next;

		 }

	  printf( "NULL\n" );



{ printf( "\nThe list in reverse is:\n" );

printf( "NULL" );

		 startPtr = temp;
		 while ( startPtr != NULL ) {
		 printf( " <-- %c", startPtr->data );
		 startPtr = startPtr->prev;

		 }

		 printf("\n\n");


}
}
}
}

You have not type casted malloc.

In C, malloc() doesn't need to be typecase.

line 120 of your program: Need to test sPrev for NULL before using it because first time through it will be NULL.

if(*sPtr != NULL)
             (*sPtr)->prev = newPtr;

hey Ancient Dragon,

the conditon

if(*sPtr != NULL)

is already been checked in the while loop and depending upon the value of currentPtr the value of previousPtr is changing in that loop. If u see care fully in my post the line no: 111 is checking weather it is a first node or not, if not, it is assigning the value of currentPtr to previousPtr.

>>111 is checking weather it is a first node or not
Nope, that won't catch the problem. When *sPtr == NULL, then previousPtr will also be NULL at line 118, and consequently *sPtr is dereferenced (illegally) at line 120.

Yes I got your point Ancient Dragon.

For the first node startPtr = NULL and therefore should be checked.

Thanks.

I have been playing with the code, and from what I can find, this line is causing the program to crash:

currentPtr = currentPtr->prev;

. If I change any instance of this line to

currentPtr = currentPtr->next;

it works without crashing. Why is this?

This is what I have modified my code to. It would be at 145 in this code:

[LIST=1]
[*]#include <stdio.h>
[*]#include <stdlib.h>


[*]struct node
[*]{
[*]char data;
[*]struct node *next,*prev;

[*]} *head=NULL, *tail=NULL, *newnode ,*Traverse;

[*]typedef struct node ListNode; 
[*]typedef ListNode *ListNodePtr;
[*]typedef struct Node *NodePtr;


[*]void insert( ListNodePtr *sPtr, char value );
[*]char Cdelete( ListNodePtr *sPtr, char value );
[*]int isEmpty( ListNodePtr sPtr );
[*]void printList( ListNodePtr currentPtr );
[*]void instructions( void );

[*]int main( void )
[*]{ 
[*]   ListNodePtr startPtr = NULL; 
[*]   int choice; 
[*]   char item;  

[*]   instructions();
[*]   printf( "? " );
[*]   scanf( "%d", &choice );

[*]   
[*]   while ( choice != 3 ) { 

[*]      switch ( choice ) { 

[*]         case 1:
[*]            printf( "Enter a character: " );
[*]            scanf( "\n%c", &item );
[*]            insert( &startPtr, item );
[*]            printList( startPtr );
[*]            break;

[*]         case 2:

[*]            
[*]            if ( !isEmpty( startPtr ) ) { 
[*]               printf( "Enter character to be deleted: " );
[*]               scanf( "\n%c", &item );

[*]            
[*]               if ( Cdelete( &startPtr, item ) ) { 
[*]                  printf( "%c deleted.\n", item );
[*]                  printList( startPtr );
[*]               } 
[*]                  else {
[*]                  printf( "%c not found.\n\n", item );
[*]               } 

[*]            } 
[*]            else {
[*]               printf( "List is empty.\n\n" );
[*]            } 

[*]            break;

[*]         default:
[*]            printf( "Invalid choice.\n\n" );
[*]            instructions();
[*]            break;
[*]      
[*]      } 

[*]      printf( "? " );
[*]      scanf( "%d", &choice );
[*]   } 

[*]   printf( "End of run.\n" );
[*]   
[*]   return 0; 

[*]} 


[*]void instructions( void )
[*]{ 
[*]   printf( "Enter your choice:\n"
[*]      "   1 to insert an element into the list.\n"
[*]      "   2 to delete an element from the list.\n"
[*]      "   3 to end.\n" );
[*]} 


[*]void insert( ListNodePtr *sPtr, char value )
[*]{ 
[*]   ListNodePtr newPtr;     
[*]   ListNodePtr previousPtr; 
[*]   ListNodePtr currentPtr;  

[*]   newPtr = malloc( sizeof( ListNode ) );

[*]   if ( newPtr != NULL ) { 
[*]      newPtr->data = value; 
[*]      newPtr->next = NULL; 

[*]      previousPtr = NULL;
[*]      currentPtr = *sPtr;

[*]  
[*]      while ( currentPtr != NULL && value > currentPtr->data ) { 
[*]         previousPtr = currentPtr;          
[*]         currentPtr = currentPtr->next; 
[*]      } 

[*]      
[*]      if ( previousPtr == NULL ) { 
[*]         newPtr->next = *sPtr;
[*]         *sPtr = newPtr;
[*]      } 
[*]      else { 
[*]         previousPtr->next = newPtr;
[*]         newPtr->next = currentPtr;
[*]      } 
[*]   
[*]   } 
[*]   else {
[*]      printf( "%c not inserted. No memory available.\n", value );
[*]   } 

[*]} 


[*]char Cdelete( ListNodePtr *sPtr, char value )
[*]{ 
[*]   ListNodePtr previousPtr; 
[*]   ListNodePtr currentPtr;  
[*]   ListNodePtr tempPtr;     
[*]  
[*]   


[*]   if ( value == ( *sPtr )->data ) { 
[*]      tempPtr = *sPtr; 
[*]      *sPtr = ( *sPtr )->next; 
[*]      free( tempPtr ); 
[*]      return value;
[*]   } 
[*]   else { 
[*]      previousPtr = *sPtr;
[*]      currentPtr = ( *sPtr )->next;

[*]     
[*]      while ( currentPtr != NULL && currentPtr->data != value ) { 
[*]         previousPtr = currentPtr;         
[*]         currentPtr = currentPtr->next; 
[*]      } 

[*]      
[*]      if ( currentPtr != NULL ) { 
[*]         tempPtr = currentPtr;
[*]         previousPtr->next = currentPtr->next;
[*]         free( tempPtr );
[*]         return value;
[*]      } 
[*]     
[*]   }

[*]   return '\0';

[*]} 




[*]int isEmpty( ListNodePtr sPtr )
[*]{ 
[*]   return sPtr == NULL;

[*]} 


[*]void printList( ListNodePtr currentPtr )
[*]{ 

[*] ListNodePtr startPtr = currentPtr, temp=NULL;
[*] 
[*]   
[*]   if ( currentPtr == NULL ) {
[*]      printf( "List is empty.\n\n" );
[*]   
[*]   } 
[*]   else { 
[*]      {printf( "The list is:\n" );

[*]      while ( currentPtr != NULL ) { 
[*]         printf( "%c --> ", currentPtr->data );
[*]         temp=currentPtr;
[*]         currentPtr = currentPtr->next;}
[*]      
[*]      printf( "NULL\n" );
[*]      


[*]{ printf( "\nThe list in reverse is:\n" );

[*]printf( "NULL" );
[*]      
[*]         currentPtr=temp;
[*]         
[*]         while ( currentPtr != NULL ) {          
[*]         printf( " <-- %c", currentPtr->data );
[*]         currentPtr = currentPtr->prev;   
[*]         }
[*]         
[*]         printf("\n\n");

[*]}
[*]} 
[*]}    
[*]} 



[/LIST]

Hey have u checked the code that i posted. No you haven't.

I and Ancient dragon had mentioned some points there about the ur code. Did u understand those points.

Again,

You have not taken care of prev pointer while insertion new items in the list.
Then how can u able to use it while displaying it in reverse order.

Please sit back and take look at your code and our modified code also.

Ok, I see what you're saying now... I didn't realize that I left that out.


EDIT:

Well, I thought it was fixed, but now I have a different problem. If the entry into the list comes before the current entries, the program runs fine (z,y,x,etc.). But if I enter a, a, b, the program crashes when I enter the b, or any letter that would go to the end of the list. What could be causing that?

My bet is that you still have not done the insert() function correctly. Here is what I used and it works ok

void insert( ListNodePtr *sPtr, char value )
{ 
   ListNodePtr newPtr;     
   ListNodePtr previousPtr; 
   ListNodePtr currentPtr;  

   newPtr = malloc( sizeof( ListNode ) );

   if ( newPtr != NULL ) { 
      newPtr->data = value; 
      newPtr->next = NULL; 
      newPtr->prev = NULL;

      previousPtr = NULL;
      currentPtr = *sPtr;

  
      while ( currentPtr != NULL && value > currentPtr->data ) { 
         previousPtr = currentPtr;          
         currentPtr = currentPtr->next; 
      } 

      
      if ( previousPtr == NULL ) { 
         newPtr->next = *sPtr;
         if(*sPtr != NULL)
             (*sPtr)->prev = newPtr;
         *sPtr = newPtr;
      } 
      else { 
          newPtr->prev = previousPtr;
         previousPtr->next = newPtr;
         newPtr->next = currentPtr;
      } 
   
   } 
   else {
      printf( "%c not inserted. No memory available.\n", value );
   } 

}
This article has been dead for over six months. Start a new discussion instead.