Like Tree2Likes
  • 1 Post By anduril462
  • 1 Post By anduril462

C programming - Doubly linked list

This is a discussion on C programming - Doubly linked list within the C Programming forums, part of the General Programming Boards category; Hi, I am having problems with my doubly linked list program. when I delete the last character in the list, ...

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    6

    C programming - Doubly linked list

    Hi, I am having problems with my doubly linked list program. when I delete the last character in the list, it deletes the whole list - so I think i'm having a problem with my ptrs. Also, 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, and once the last letter entered is inputted to be deleted from the list, it outputs "the list is empty", even if not all the letters have been inputted to be deleted.

    Here is my current code:

    Code:
    
    #include <cstdlib>
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    
    
    using namespace std;
    
    
    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 */
          *tPtr = ( *tPtr)->prevPtr; /* update prevPtr of new head of list */
          
          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;
       
       previousPtr->nextPtr=previousPtr;
       
       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");
              }
              
          }




  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,465
    Code:
    $ make list
    gcc -Wall -g -std=c99 -pedantic  -lssl -lm -lpthread -lcurses -lefence  list.c   -o list
    list.c:1:19: error: cstdlib: No such file or directory
    list.c:2:20: error: iostream: No such file or directory
    list.c:7: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘namespace’
    make: *** 
    [list] Error 1
    The following 3 lines make this C++ code, but the rest looks like it's supposed to be C:
    Code:
    #include <cstdlib>
    #include <iostream>
    ...
    using namespace std;
    You need to figure out for sure which language you want to use.

    Next, you need to work on your indentation. If your code is hard to read, it's easy to make mistakes and hard to find or fix them. If it looks good in your editor, but not on the site, take the time to fix it here, so we don't have to deal with your crappy indentation. It will increase the quality of help you get too.

    Also, it is generally considered bad form to typedef a pointer since it makes it harder to read and harder to figure out exactly how many levels of indirection there are. The exception is a completely opaque data type, which you don't have, and if you did, you should avoid putting "Ptr" on the end of the type because it's opaque, so the user of that type shouldn't know anything about it's implementation.

    Now, on to your program. You appear to have the delete issue you mentioned, but you have an error building your list which should be sorted out first, since you can't expect your delete to work if the list isn't right to begin with:
    Code:
    Enter a character: a
    ...
    Enter a character: b
    the list is:
    a --> b --> NULL
    
    the list in reverse is:
    b --> a --> NULL
    
    ? 1
    Enter a character: 3
    the list is:
    3 --> a --> b --> NULL
    
    the list in reverse is:
    3 --> NULL
    Adding to the beginning of a non-empty list seems to be a problem. Your new element ends up with the correct next and prev pointers, but your tail pointer is screwed up. Line 112 is the culprit, because the if condition on line 109 is mixing up the "insert at beginning" case and the "insert in empty list" case.

    As for your delete problem, you seem to find the node correctly, but you screw up the pointers to the nodes around it. On line 188, you correctly set previousPtr->nextPtr to currentPtr->nextPtr, but then on line 190, you reset it to itself, creating an circular list with one element in the forward direction. You need to set currentPtr->nextPtr->prevPtr to previousPtr. Actually, you can do all this without the temp and previous pointers:
    Code:
    current->next->prev = current->prev  // set the following node's prev pointer to the previous node
    current->prev->next = current->next  // set the previous node's next pointer to the following node
    free(current)
    EDIT:
    Quote Originally Posted by pghpens91 View Post
    Also, 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, and once the last letter entered is inputted to be deleted from the list, it outputs "the list is empty", even if not all the letters have been inputted to be deleted.
    I'm not quite sure what you mean here, particularly the bit about holding a different character. Perhaps you could provide the input that causes the problem along with the output you expect and the output you actually get.
    Last edited by anduril462; 07-12-2012 at 03:43 PM.
    dmh2000 likes this.

  3. #3
    Registered User
    Join Date
    Jul 2012
    Posts
    6
    Thank you so much for your response.
    I am using the c programming language for this program.
    I'm sorry about the bad indentation, when I copy and paste from my compiler, the indentation was off.
    Also, my professor wanted us to use typedef for this program (not sure exactly why but I was just following his order)

    I made the changes you suggested (I switched lines 188&190 to what you said, and took out 112).

    Now when I run the program, it runs fine when I insert characters, but when I delete a character, it deletes all the characters except for one, and when I go to delete the last character, the program crashes..

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,465
    Your indentation issue is probably due to you using tab characters to indent your code instead of spaces. Most editors/IDEs have settings that let you control that. As for the typedef, just keep it in mind for when you have a professor that doesn't teach bad practices .

    As for the crash on delete problem, you will need to post your updated code. You can post just the new insert and delete functions if that is all you changed.

  5. #5
    Registered User
    Join Date
    Jul 2012
    Posts
    6
    Here is my insert and delete functions....

    Code:
    /* 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;
    
    
              }//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 */
          *tPtr = ( *tPtr)->prevPtr; /* update prevPtr of new head of list */
          
          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;
       currentPtr->nextPtr->prevPtr = currentPtr->prevPtr;  // set the following node's prev pointer to the previous node
       currentPtr->prevPtr->nextPtr = currentPtr->nextPtr;  // set the previous node's next pointer to the following node
       free(currentPtr);
       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");
              }
              
          }

    I was most concerned with this code in the delete function:
    Code:
       /* delete first node */   if ( value == ( *sPtr )->data)
          {/* Begin if loop */
          tempPtr = *sPtr; /* hold onto node being removed */
          *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
          *tPtr = ( *tPtr)->prevPtr; /* update prevPtr of new head of list */
          
          free( tempPtr ); /* free the de-threaded node */
          
         (*sPtr)->prevPtr = NULL;
          return value;
      } /* end if */

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,465
    You still have problems on insert:
    Code:
    Enter a character: a
    
    
    Enter a character: b
    
    
    Enter a character: c
    
    
    Enter a character: 1
    the list is:
    1 --> a --> b --> c --> NULL
    
    
    the list in reverse is:
    c --> b --> a --> NULL
    Where's the '1' in the reverse list?

    I have a sneaking suspicion you "figured out" how to write your insert and delete functions with the keyboard. Work through the process with a pencil and paper first, in plain English*. Draw out list nodes and pointers and connect all the arrows as you insert into a new list, and at the beginning, middle and end of an existing list, modifying the head and tail pointers as appropriate. Do the same for delete, deleting from the beginning, middle and end of a list, rearranging the next/prev pointers and adjusting the head and tail pointers if appropriate.

    To fix your insert problem, I think you simply need to set the previous pointer of the old start node to point to the new node.

    Also, I think the flow of your delete function is a little convoluted. Again, talk it out, and work it out on paper, in plain English*. Here is a template for the delete function.
    Code:
    if the list is empty
        do nothing
    
    search for the value to be deleted (some sort of loop)
    if you find it, store a pointer to it (I will call the variable "curr" for this example)
    
    if the value was not found
        do nothing
    
    if head and tail pointers are equal to curr
        the list has one element, remove it
    else if head == curr
        remove the first node
    else if tail == curr
        remove the last node
    else
        remove a middle node
    Remember, you don't need a temp or previous pointer, just curr and your head and tail (sPtr & tPtr).

    * Of course, you can use whatever your native language is, but do NOT use C or even pseudo code until you can explain the solution in human terms.

    EDIT:
    A quick note on development process:
    Programming is about problem solving, not typing. It is important to first understand the problem, then to plan your solution, and finally to code it and test it. You should not touch a keyboard until the actual coding phase. Come up with a solution in human terms, and sketch it out on paper. Work through your solution by hand, on paper, with sample input. Then turn that into pseudo code. Lastly, turn that pseudo code into C. Only write 5-10 lines at a time, compile, test and fix all errors. I'm very serious about that, a good development process that stresses understanding and planning before execution is crucial to being a good programmer, and will save you hours and hours of crappy debug work and waiting around on forums for help. University would have been 100 times easier if they would have taught me that freshman year, instead of me figuring it out on my own after I was working in industry.
    Last edited by anduril462; 07-12-2012 at 08:03 PM.
    laserlight likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list
    By BEN10 in forum C Programming
    Replies: 4
    Last Post: 07-21-2009, 09:32 AM
  2. doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 04-26-2007, 03:41 AM
  3. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 01:31 PM
  4. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 01:39 PM
  5. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21