Thread: Modify to make Doubly Linked List

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    8
    ....
    Last edited by Dampecram; 10-29-2008 at 11:22 AM.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    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 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, char value );
    char delete( ListNodePtr *sPtr, char value );
    int isEmpty( ListNodePtr sPtr );
    void printList( ListNodePtr currentPtr );
    void instructions( void );
    void printBackwards (ListNodePtr currentPtr );
    
    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 );
    			printBackwards( 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 );
    					printBackwards( 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 */
    		newPtr->prevPtr = NULL;
    		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 */
    
    		        /* add here , point up stream */
    		} /* end while */
    
    		/* insert new node at begining of list */
    		if ( previousPtr == NULL ) {
    			newPtr->nextPtr = *sPtr;
    			
                    	if(*sPtr != NULL)
                        	    (*sPtr)->prevPtr = newPtr;
                  
                    	*sPtr = newPtr;
    		} /* end if */
    		else { /* insert new node between previousPtr and currentPtr */
    			newPtr->prevPtr = previousPtr;
                		previousPtr->nextPtr = newPtr;
    			newPtr->nextPtr = currentPtr;
                            if (currentPtr != NULL)
                                currentPtr->prevPtr = newPtr;
    			
    		} /* 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 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 is 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 */
    
    void printBackwards ( ListNodePtr currentPtr )
    {
         ListNodePtr temp = NULL;
     
    	  while ( currentPtr != NULL ) {
    		 temp = currentPtr;
    		 currentPtr = currentPtr->nextPtr;
    		 
    		 }
    		 
          printf( "\nThe list in reverse is:\n" );
          printf( "NULL" );
     
    		 currentPtr = temp;
    		 while ( currentPtr !=  NULL) {
    		 printf( " <-- %c", currentPtr->data );
    		 currentPtr = currentPtr->prevPtr;
    		 }
    		 
    		 printf("\n\n");
    		 
    }

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    8
    wow thank you so much. This topic in C has been driving me crazy.. Ive been stumped on that part for a while.. Thanks a lot, now thats one less thing to worry about, now its time to work on the delete function, heh

    thank you again

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Why did you remove your original question, now no one else knows for sure what this was about.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    I agree with citizen you should not have removed your original post. You might want to repost your question for the sake of everyone.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I'm not a fan of playing Jeopardy either.

    Next time we'll either quote your entire post to reply, or we simply wont answer at all.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    If I wanted to take a stab at "why" my guess would be that the teacher wonders through the forums periodically. But who knows.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    8
    My original problem was that I was missing part of the link in the program for prevPtr. When I ran the program, the print forward would work fine, but the print backwards wasn't working correctly. I was losing part of my list in my insert function and couldn't figure out why. For example.. When I entered the word dog.. when my program would display.. the "g" would be lost when printed in reverse and that showed my prevPtr had something wrong with it.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Okay cool. Thanks for coming back to put that back in.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    24
    i have a question, the double link list right, i was told it points to both the previous and the next nodes but i dont fully understand how they work and also the circular link list.

  11. #11
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I use circular linked lists for memory management frequently. The proven advantage of circular linked lists is it very easy to insert elements without having any sort of "special case"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  2. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  3. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM