LinkBack URL
About LinkBacks
Have a tough assignment on linked lists and nothing in my book on doubly linked lists, I'm re-reading the chapter and trying to come up with something bnut any pointers would be greatly appreciated. I'll update it when I get something going:
Change the singly linked list code in the book to a doubly linked list - figure 12.3
To do this you should create a Node:
struct Node{
char d;
Node *next;
Node *prev;
}
so that you can move forward and backwards in the list.
You should implement insert and delete so that they work properly. You should implement a print_backwards to prove that your doubly linked list is working correctly.
Note that you should keep track of the head and tail of the list.
here is fig 12.3
Code:#include <stdio.h> #include <stdlib.h> /* self referential structure */ struct listNode { char data; /* each listNode contains a character */ struct listNode *nextPtr; /* pointer to the nextnode */ }; /* 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() { ListNodePtr startPtr = NULL; /* initially there are no nodes */ int choice; /* users 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 the 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 ) ) { 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; /* indicate sucessful 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 of instructions */ /* insert a new value into the list in sorted order */ void insert ( ListNodePtr *sPtr, char value) { ListNodePtr newPtr; /* pointer to a new node */ ListNodePtr previousPtr; /* pointer to previous node in list */ ListNodePtr currentPtr; /* pointer to current node on 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 begining 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 id */ 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 on list */ ListNodePtr currentPtr; /* pointer to current node on list */ ListNodePtr tempPtr; /* temperary 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 correct location on 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 list is empty, 0 otherwise */ int isEmpty ( ListNodePtr sPtr ) { return sPtr == NULL; } /* end function isEmpty */ /* Print the list */ void printList ( ListNodePtr currentPtr ) { /* if list id empty */ if ( currentPtr == NULL) { printf( " The 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 */
