Thread: 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);
    }
}

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.

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.

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.

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?

Originally Posted by vart

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!