Linked List - Print Backwards
Hi, for my class, I had to modify an example of a linked list from my text book so that it is a doubly linked list. Then I had to prove that myprogram works properly by implementing a print backwards function. Here is the example program from the book:
Code:
/* Fig. 12.3: fig12_03.c
Operating and maintaining a list */
#include <stdio.h>
#include <stdlib.h>
/* self-referential structure */
struct listNode {
char data; /* each listNode contains a character */
struct listNode *nextPtr; /* pointer to next node*/
}; /* end structure listNode */
typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */
/* prototypes */
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; /* initially there are no nodes */
int choice; /* user's choice */
char item; /* char entered by user */
instructions(); /* display the menu */
printf( "? " );
scanf( "%d", &choice );
/* loop while user does not choose 3 */
while ( choice != 3 ) {
switch ( choice ) {
case 1:
printf( "Enter a character: " );
scanf( "\n%c", &item );
insert( &startPtr, item ); /* insert item in list */
printList( startPtr );
break;
case 2:
/* if list is not empty */
if ( !isEmpty( startPtr ) ) {
printf( "Enter character to be deleted: " );
scanf( "\n%c", &item );
/* if character is found, remove it */
if ( delete( &startPtr, item ) ) { /* remove item */
printf( "%c deleted.\n", item );
printList( startPtr );
} /* end if */
else {
printf( "%c not found.\n\n", item );
} /* end else */
} /* end if */
else {
printf( "List is empty.\n\n" );
} /* end else */
break;
default:
printf( "Invalid choice.\n\n" );
instructions();
break;
} /* end switch */
printf( "? " );
scanf( "%d", &choice );
} /* end while */
printf( "End of run.\n" );
return 0; /* indicates successful termination */
} /* end main */
/* display program instructions to user */
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" );
} /* end function instructions */
/* Insert a new value into the list in sorted order */
void insert( ListNodePtr *sPtr, char value )
{
ListNodePtr newPtr; /* pointer to new node */
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
newPtr = malloc( sizeof( ListNode ) ); /* create node */
if ( newPtr != NULL ) { /* is space available */
newPtr->data = value; /* place value in node */
newPtr->nextPtr = NULL; /* node does not link to another node */
previousPtr = NULL;
currentPtr = *sPtr;
/* loop to find the correct location in the list */
while ( currentPtr != NULL && value > currentPtr->data ) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* insert new node at beginning of list */
if ( previousPtr == NULL ) {
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
} /* end if */
else { /* insert new node between previousPtr and currentPtr */
previousPtr->nextPtr = newPtr;
newPtr->nextPtr = currentPtr;
} /* end else */
} /* end if */
else {
printf( "%c not inserted. No memory available.\n", value );
} /* end else */
} /* end function insert */
/* Delete a list element */
char delete( ListNodePtr *sPtr, char value )
{
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
/* delete first node */
if ( value == ( *sPtr )->data ) {
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
free( tempPtr ); /* free the de-threaded node */
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;
/* loop to find the correct location in the list */
while ( currentPtr != NULL && currentPtr->data != value ) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
return value;
} /* end if */
} /* end else */
return '\0';
} /* end function delete */
/* Return 1 if the list is empty, 0 otherwise */
int isEmpty( ListNodePtr sPtr )
{
return sPtr == NULL;
} /* end function isEmpty */
/* Print the list */
void printList( ListNodePtr currentPtr )
{
/* if list is empty */
if ( currentPtr == NULL ) {
printf( "List is empty.\n\n" );
} /* end if */
else {
printf( "The list is:\n" );
/* while not the end of the list */
while ( currentPtr != NULL ) {
printf( "%c --> ", currentPtr->data );
currentPtr = currentPtr->nextPtr;
} /* end while */
printf( "NULL\n\n" );
} /* end else */
} /* end function printList */
I have updated this code to make it a doubly linked list with a print backwards function, but I am not getting the correct output. I am having problems when with the list printing in reverse (the reverse list doesnt always print all the letters in the list) and also when I delete characters from the list. I noticed that when I delete letters (other than the last one entered), it holds a different character in place of the letter that was entered to be deleted.
Here is my current code:
Code:
#include <stdio.h>
#include <stdlib.h>
struct listNode {
char data;//each listNode contains a character
struct listNode *nextPtr; //pointer to next node
struct listNode *prevPtr; //pointer to previous node
}; // end structure listNode
typedef struct listNode ListNode; //synonym for struct listNode
typedef ListNode *ListNodePtr; //synonym for ListNode
/* prototypes */
void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value );
char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value);
int isEmpty( ListNodePtr sPtr);
void printList( ListNodePtr currentPtr );
void printBack( ListNodePtr currentPtr );
void instructions(void );
int main(int argc, char *argv[])
{
ListNodePtr startPtr=NULL; /* initially there are no nodes */
ListNodePtr tailPtr=NULL;
int choice; /* user's choice */
char item; /* char entered by user */
instructions(); /* display the menu */
printf("? ");
scanf("%d", &choice);
while(choice !=3){
switch(choice){
case 1:
printf("Enter a character: ");
scanf("\n%c", &item);
insert(&startPtr, &tailPtr, item); /* insert item in list */
printList(startPtr);
printBack(tailPtr);
break;
case 2: /* delete an element */
/* if list is no empty */
if(!isEmpty(startPtr)){
printf("Enter a character to be deleted: ");
scanf("\n%c", &item);
/* if character is found remove it */
if(deletechar(&startPtr, &tailPtr, item)){ /* remove item */
printf("%c deleted.\n", item);
printList(startPtr);
printBack(tailPtr);
}/* end if */
else{
printf("%c not found.\n\n", item);
}/* end else */
}/* end if */
else{
printf("List is empty.\n\n");
}/* end else */
break;
default:
printf("invalid choice. \n\n");
instructions();
break;
}/* end switch */
printf("? ");
scanf("%d", &choice);
}/* end while */
printf("end of run.\n");
return 0; /* indicates successful termination */
}/* end main*/
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");
}/* end function instructions */
/* Insert a new value into the list in sorted order */
void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
ListNodePtr newPtr; //pointer to new node
ListNodePtr previousPtr; //pointer to previous node in list
ListNodePtr currentPtr; //point to current node in list
newPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); //create node
if(newPtr!=NULL){ //is space available
newPtr->data=value; //place value in node
newPtr->nextPtr=NULL; //node does not link to another node
previousPtr=NULL;
currentPtr=*sPtr;
newPtr->prevPtr=NULL;
//loop to find the correct location in the list
while(currentPtr !=NULL&&value > currentPtr->data){
previousPtr=currentPtr; /* walk to ... */
currentPtr=currentPtr->nextPtr; /* ... next node*/
}//end while
if(previousPtr==NULL){ // inserted at beginning of list
newPtr->nextPtr=*sPtr;
*sPtr=newPtr;
*tPtr=newPtr;
}//end if
else{ //insert new node between previousPtr and currentPtr
if(currentPtr!=NULL){ // inserted in the middle
previousPtr->nextPtr=newPtr;
newPtr->nextPtr=currentPtr;
currentPtr->prevPtr=newPtr;
newPtr->prevPtr=previousPtr;
}
else{//inserted at end of list
*tPtr=newPtr;
previousPtr->nextPtr=newPtr;
newPtr->prevPtr=previousPtr;
}
} /* end else */
} /* end if */
else{
printf("%c not inserted. no memory available.\n", value);
}//end else
}//end function insert
/* delete a list element */
char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node in list */
ListNodePtr tempPtr; /* temporary node pointer */
if( *sPtr == NULL ){//checks to see if list is empty
return '\0';
}
if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
*tPtr=NULL;
}
/* delete first node */
if ( value == ( *sPtr )->data)
{/* Begin if loop */
tempPtr = *sPtr; /* hold onto node being removed */
*sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
free( tempPtr ); /* free the de-threaded node */
// (*sPtr)->prevPtr = NULL
return value;
} /* end if */
else {
previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;
/* loop to find the correct location in the list */
while ( currentPtr != NULL && currentPtr->data != value ) {
previousPtr = currentPtr; /* walk to ... */
currentPtr = currentPtr->nextPtr; /* ... next node */
} /* end while */
/* delete node at currentPtr */
if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
return value;
}/* end if */
} /* end else */
return '\0';
} /* end function delete */
/* Return 1 if the list is empty, 0 otherwise */
int isEmpty(ListNodePtr sPtr){
return sPtr==NULL;
}/* end function isEmpty */
void printList(ListNodePtr currentPtr){
//if list is empty
if(currentPtr==NULL){
printf("List is empty.\n\n");
}//end if
else{
printf("the list is:\n");
// while not the end of the list
while(currentPtr !=NULL){
printf("%c --> ", currentPtr->data );
currentPtr=currentPtr->nextPtr;
}//end while
printf("NULL\n\n");
}
}
void printBack(ListNodePtr currentPtr){
if(currentPtr==NULL){
printf("List is empty.\n\n");
}
else{
printf("the list in reverse is:\n");
while(currentPtr !=NULL){
printf("%c --> ", currentPtr->data );
currentPtr=currentPtr->prevPtr;
}
printf("NULL\n\n");
}
}
