CODEWITHSUNDEEP
cdata-structureslinked-list
Jack022
Jack022

Reputation: 1257

Deleting a node appended at the end of a linked list in C

I have a linked list where each node stores a word and a number. I can add nodes at the top of the list (push), at the center of the list (insertAfter) and at the end of the list (append). I now added a function to delete nodes, where it will take a char, it will search that char through the list and delete the node that stores that char.

The problem is that deleteNode will work with a normal node added at the top of the list, but when i append a node at the end or add it at the middle of the list it won't work.

Tl;dr deleteNode works with nodes created with push but not with nodes created with append or insertAfter.

The error i get is segmentation fault, so i don't have a specific error from the compiler. I'm trying to debug it by running different parts of the code but i still can't find the problem.

struct Node
{
  int data;
  char *word;
  struct Node *next;
};


void push(struct Node** head_ref, int new_data, char *new_word)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;


    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = (*head_ref);

    (*head_ref)    = new_node;
}

/* Given a node prev_node, insert a new node after the given 
   prev_node */
void insertAfter(struct Node* prev_node, int new_data, char *new_word)
{

    if (prev_node == NULL)
    {
      printf("the given previous node cannot be NULL");
      return;
    }

    struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = prev_node->next;
    prev_node->next = new_node;
}


void append(struct Node** head_ref, int new_data, char *new_word)
{

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    struct Node *last = *head_ref;  


    new_node->data  = new_data;

    new_node->word= malloc(strlen(new_word));
    strcpy(new_node->word, new_word);

    new_node->next = NULL;


    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }


    while (last->next != NULL)
        last = last->next;


    last->next = new_node;
    return;
}



void deleteNode(struct Node **head_ref, char *word)
{

    struct Node* temp = *head_ref, *prev;
    if (strcmp(word, (*head_ref)->word)==0)
    {
        *head_ref = temp->next;   // Changed head
        free(temp);               // free old head
        return;
    }



    while (strcmp(word, (*head_ref)->word)!=0)
    {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;


    prev->next = temp->next;

    free(temp);  // Free memory

}

Upvotes: 1

Views: 68

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59184

The answers you have are OK, but just for the record, after enough practice it should look kinda like this:

void deleteNode(struct Node **pplist, char *word)
{
    for (struct Node *n = *pplist; n; n=*(pplist = &(n->next)))
    {
        if (!strcmp(n->word,word))
        {
            *ppnode = n->next;
            free(n->word);
            free(n);
            break;
        }
    }
}

The point is that you can just move the pointer to the node pointer through the list instead of treating the head as a special case.

Similarly, you can do append like this:

void append(struct Node** pplist, int new_data, char *new_word)
{
    for(; *pplist; pplist=&((*pplist)->next));
    push(pplist, new_data, new_word);
}

and insert_after(prev... is just push(&(prev->next)...

Upvotes: 1

arorias
arorias

Reputation: 318

Apart from what was stated by @4386427, you are not allocating enough space for your strings there:

new_node->word= malloc(strlen(new_word));

Notice that the C library function size_t strlen(const char *str) computes the length of the string str up to, but not including the terminating null character. So i would rather suggest:

new_node->word= malloc(strlen(new_word) + 1);
new_node->word[strlen(new_word)] = '\0';

This can cause you some problems with the memory. ;)

Or event better, use calloc, so the second line will be unnecessary: 

new_node->word= calloc(strlen(new_word) + 1, sizeof(char));

Upvotes: 1

4386427
4386427

Reputation: 44274

This part looks strange:

while (strcmp(word, (*head_ref)->word)!=0)
{
    prev = temp;
    temp = temp->next;
}

In the strcmp you use head_ref but in the body you update temp to move to the next element.

Did you intend to do:

while (strcmp(word, temp->word)!=0)
{
    prev = temp;
    temp = temp->next;
}

Further there should probably some check for temp being NULL. Like:

while (temp && strcmp(word, temp->word)!=0)

Upvotes: 2

Related Questions