link list not deleteing

This is a discussion on link list not deleteing within the C Programming forums, part of the General Programming Boards category; I get a string from the user and store it in a linked list in proper order and then print ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    9

    Question link list not deleteing

    I get a string from the user and store it in a linked list in proper order and then print the final list. This works fine. However when it comes to deleting the bottom node on the stack, my code doesn't work. Here is what I have:
    Code:
    /*This code is representative of many revisions to try to get the solution and thus may be far removed from any actual solution.
    As I got more desperate to solve it, I simply began changing it a lot and running it and debugging it to see if I could see the answer. 
    obviously, I did not find the answer.*/
    void deleteNode(node_Ptr *listStarter)
    {
        node_Ptr previPtr, curPtr, temp;
    
        if ((*listStarter)->next==NULL)
        {
            previPtr=*listStarter;
            (*listStarter)->next=NULL;
            previPtr=NULL;
            free(previPtr);
        }
        else
        {
            while (curPtr!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
            previPtr->next=NULL;
            free(curPtr);
        }
        printf("\n\n");
    }
    It should delete from the top up but it doesn't work at all. Any help would be appreciated.

    Here is all the code:
    Code:
    /********************************************************************************
    
    <header stuff goes here>
    
    ********************************************************************************/
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<ctype.h>
    #define MAXWORD 16
    
    typedef struct node
    {
        char word[MAXWORD];
        struct node *next;
    } node_t;
    
    typedef node_t *node_Ptr;
    
    void getWord(char theWord[]);
    void insertNode(node_Ptr *listStarter, char tempWord[MAXWORD]);
    char willContinue(void);
    void printList(node_Ptr curPtr, char noEntered);
    void flushTheBuffer(void);
    void deleteNode(node_Ptr *listStarter);
    
    int main(void)
    {
        char tempWord[MAXWORD*3];
        node_Ptr listStart=NULL;
        int numOfLoops=0;
    
        printList(listStart, 'y');
    
        do
        {
            getWord(tempWord);
            insertNode(&listStart, tempWord);
            printList(listStart, 'y');
            numOfLoops++;
        }
        while (willContinue()=='y');
    
        printList(listStart, 'n');
        printf("\n%78s","Deleting nodes one at a time\n");
    
        while (numOfLoops>0)
        {
        deleteNode(&listStart);
        printList(listStart, 'y');
        numOfLoops--;
        }
    
        return 0;
    }
    
    void deleteNode(node_Ptr *listStarter)
    {
        node_Ptr previPtr, curPtr, temp;
    
        if ((*listStarter)->next==NULL)
        {
            previPtr=*listStarter;
            (*listStarter)->next=NULL;
            previPtr=NULL;
            free(previPtr);
        }
        else
        {
            while (curPtr!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
            previPtr->next=NULL;
            free(curPtr);
        }
        printf("\n\n");
    }
    
    void insertNode(node_Ptr *listStarter, char tempWord[MAXWORD])
    {
        node_Ptr newPtr, previPtr, curPtr;
    
        newPtr=malloc(sizeof(*newPtr));
    
        if (newPtr!=NULL)
        {
            strcpy(newPtr->word, tempWord);
            newPtr->next=NULL;
    
            previPtr=NULL;
            curPtr=*listStarter;
    
            while (curPtr!=NULL && strcmp(tempWord, curPtr->word) > 0)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
    
            if (previPtr==NULL)
            {
                newPtr->next=*listStarter;
                *listStarter=newPtr;
            }
            else
            {
                previPtr->next=newPtr;
                newPtr->next=curPtr;
            }
        }
        else
        {
            printf("There is not enough memory available to complete the requested process.  Terminating.\n");
        }
    }
    
    /********************************************************************************
    
    willContinue    This function asks the user if they wish to continue using
    the program and parses their response
    
    Inputs:    None
    Outputs:   isAnswer - The answer to the question, a y or an n
    
    ********************************************************************************/
    char willContinue(void)
    {
        char isAnswer;
    
        printf("\nDo you wish to enter another word? Y or N? ");
        scanf(" %c", &isAnswer);
        flushTheBuffer();
        isAnswer=tolower(isAnswer);
        if (isAnswer!='y' && isAnswer!='n')
        {
            printf("HUH?");
            return willContinue();
        }
        else
        {
            return isAnswer;
        }
    }
    
    void printList(node_Ptr curPtr, char noEntered)
    {
        if (curPtr==NULL)
        {
            printf("%65s","List is empty.\n\n");
        }
        else
        {
            if (noEntered=='n')
            {
                printf("%69s","The final list is:\n\n");
    
                while (curPtr!= NULL)
                {
                    printf("%54s\n", curPtr->word);
                    curPtr=curPtr->next;
                }
            }
            else
            {
                while (curPtr!= NULL)
                {
                    printf("%54s\n", curPtr->word);
                    curPtr=curPtr->next;
                }
            }
        }
    }
    
    /********************************************************************************
    
    flushTheBuffer    This function fixes the fact that scanf doesn't fully clean
    out the input buffer
    
    Inputs:    charFromBuffer - any and all remaining characters in stdin
    Outputs:    None
    
    ********************************************************************************/
    void flushTheBuffer(void)
    {
        int charFromBuffer;
        while((charFromBuffer=getchar())!='\n'&&charFromBuffer!=EOF);
    }
    
    void getWord(char * theWord)
    {
        printf("Enter a word: ");
        scanf(" %s", theWord);
        if (strlen(theWord)>=MAXWORD)
        {
            getWord(theWord);
        }
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Deleting from "first to last":
    Code:
    void foo( node *l )
    {
        if( l )
        {
            node * n = l->next;
            free( l );
            foo( n );
        }
    }
    Deleting from "bottom to top":
    Code:
    void foo( node *l )
    {
        if( l )
        {
            node * n = l->next;
            foo( n );
            free( l );
        }
    }
    Assuming you really mean to delete the entire list--or at least everything from the passed node down.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    9
    First of all, thanks for the reply. Secondly, it indeed has to be bottom up on the stack. And finally, we have to not just free the node but properly de-thread it first.

    Also, your example doesn't "walk" to the end of the linked list.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    > First of all, thanks for the reply. Secondly, it indeed has to be bottom up on the stack.
    > Also, your example doesn't "walk" to the end of the linked list.

    Would you be able to come to a conclusion regarding which example is right if I told you that you could say the first example uses a first-in-first-out stack, and the second example uses a last-in-first-out stack? The LIFO version builds the entire stack before deleting, so it does walk to the end.
    Last edited by whiteflags; 04-12-2010 at 11:50 PM.

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    9
    Okay I can see that. Still, it doesn't help me to understand why my code isn't functioning properly as I thought I was de-threading and freeing properly.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    Lists with one node wont be deleted properly because you set the pointer you wanted to delete to NULL before calling free with your pointer as an argument. In a regular run, you should get a segmentation fault.

    Lists with more than one node won't be deleted because the code says walk to the end, delete the last node, and then return. If you really have to delete the list from back to front, then the easiest way is to use a stack, and the easiest way to get a stack is with a recursive implementation, like quzah showed you. If you must implement the stack yourself, then transform the list to an array of nodes first and treat it like your stack.

  7. #7
    Registered User
    Join Date
    Mar 2010
    Posts
    9

    Thanks for the reply

    I got the first one working again. I had it working previously but fudged it up.

    Code:
    void deleteNode(node_Ptr *listStarter)
    {
        node_Ptr previPtr, curPtr, temp;
    
        if ((*listStarter)->next==NULL)
        {
            previPtr=*listStarter;
            (*listStarter)->next=NULL;
            *listStarter=NULL;
            free(previPtr);
        }
        else
        {
            previPtr=(*listStarter);
            curPtr=(*listStarter)->next;
            while (curPtr!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
            previPtr->next=NULL;
            free(curPtr);
        }
        printf("\n\n");
    }
    The second part still doesn't work.

    You said that this is walking to the end and deleting the node and returning. Why does the deleted node comeback after it was deleted? Am I doing something wrong?

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    Code:
     while (curPtr!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
    //when you got here currPtr is NULL
            previPtr->next=NULL;
            free(curPtr); //free(NULL) does nothing
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Registered User
    Join Date
    Mar 2010
    Posts
    9
    Quote Originally Posted by vart View Post
    Code:
     while (curPtr!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
    //when you got here currPtr is NULL
            previPtr->next=NULL;
            free(curPtr); //free(NULL) does nothing
    YES! Vart! I figured that out myself at the end of Math class. I came here to post my resolution. I finally got it! Here's the final deleteNode function I came up with that works in case it helps anyone else:
    Code:
    void deleteNode(node_Ptr *listStarter)
    {
        node_Ptr previPtr, curPtr, tempPtr;
    
        if ((*listStarter)->next==NULL)
        {
            previPtr=*listStarter;
            (*listStarter)->next=NULL;
            *listStarter=NULL;
            free(previPtr);
        }
        else
        {
            previPtr=(*listStarter);
            curPtr=(*listStarter)->next;
            while (curPtr->next!=NULL)
            {
                previPtr=curPtr;
                curPtr=curPtr->next;
            }
            previPtr->next=NULL;
            free(curPtr);
        }
        printf("\n\n");
    }
    The solution was so easy I had to hit myself!

  10. #10
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,794
    Code:
    typedef node_t *node_Ptr;
    Just a nit, but that can sometimes cause problems when you hide a pointer by wrapping it up into a typedef.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  2. Link List Insert prob
    By Bebs in forum C Programming
    Replies: 8
    Last Post: 12-03-2008, 09:28 PM
  3. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 09:11 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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