Deleting a node from linked list in C

Question

My problem is deleting a node from linked list.

I have two structs :

typedef struct inner_list 
{
 int count;
 char word[100];
 inner_list*next;
} inner_list;
typedef struct outer_list
{
 char word [100];
 inner_list * head;
 int count;
 outer_list * next; 
} outer_list;

My problem is in deleting a node from outer_list linked list. For example when user entered aaa to delete, delete function should find the node with outer_list->word = aaa and delete this node and reconnect the list again. I tried the below code to do this. but After finding and deleting I'm losing the list. I don't know what's wrong. Please notice that outer_list have also a linked list of inner_list inside.

void delnode(outer_list **head,char num[100])//thanks to both Nir Levy and Jeremy P.
{
    outer_list *temp, *m;
    m=temp=*head; /*FIX #1*/
    while(temp!=NULL) {
        if(strcmp(temp->word,num)==0) {
            if(temp==*head) {
                delinner(temp->head); /* FIX#2 */
    *head=temp->next;

                free(temp);
                return;
            } else {
                delinner(temp->head); /* FIX#2 */ 
    m->next=temp->next;

                free(temp);
                return;
            }
        } else {
            m=temp;
            temp= temp->next;
        }
    }
    printf(" ELEMENT %s NOT FOUND ", num);
}
void delinner(inner_list *head) { /* FIX#2 */
    inner_list *temp;
    temp=head;
    while(temp!=NULL) {
        head=temp->next;
        free(temp);
        temp=head;
    }
}

Now my problem is updated. While deleting an element from inner list I am also trying the delete the same element from inner_list too.

For example: - Let's say aaa is an element of outer_list linked list and let's point it with outer_list *p - This aaa can also be in an inner_list linked list too. (it can be in p->head or another innerlist.) Now, the tricky part again. I tried to apply the same rules with outer_list deletion but whenever i delete the head element of inner_list it gives an error. Here is what I tried:

void delnode2(outer_list *up,inner_list **head,char num[100])
{
    inner_list *temp2,*temp, *m;
 outer_list *p;
 p = up;

 while(p!=NULL){m=temp=temp2=p->head; 
    while(temp!=NULL) {
        if(strcmp(temp->word,num)==0) {
            if(temp==(*head)) {
                *head=temp->next;

                free(temp);
                return;
            } else {
                m->next=temp->next;

                free(temp);
                return;
            }
        } else {
            m=temp;
            temp= temp->next;
        }
    }
 p=p->next;
 }
    printf(" ELEMENT %s NOT FOUND ", num);
}

Here i'm trying to send the node and checking all the inner_lists of outer_list elements and perform deletion however when the first element is deleted it crashes. Please ask for further information. I might use very untidy words.

Answer 1

m pointer is not set to any valid address before you dereference it and your program runs into undefined behavior.

In order to fix your implementation use two pointers - one onto the current element and the other to the previous one and update both of them as you traverse the list. You'll have to treat cases with zero and oneelemenats as special - be careful.

Answer 2

I don't think you are freeing your inner_list. You will get a memory leak.

Answer 3

Your if condition that is checking for the word, isn't it to supposed to be the following:

if(strcmp(temp->word, num)==0)

?

Answer 4

try this (only for the outer list, it wont release the inner one):

void delnode(outer_list *head,char num[100]) 
{ 
    outer_list *temp, *m. *helper; 
    temp=head; 
    while(temp!=NULL) 
    { 
        if(strcmp(temp->word,num)==0) 
        { 
            if(temp==head) 
            { 
                head=temp->next; 
                free(temp); 
                return; 
            } 
            else 
            { 
                m = temp;
                temp = temp->next;
                helper->next = temp; //link the previous item
                free(m); 
                return; 
            } 
        }
        else 
        { 
            helper = temp;
            temp= temp->next; 
        } 

    } 
    printf(" ELEMENT %s NOT FOUND ", num); 
} 

Answer 5

FIX#1 (optional) - it is a good practice to initialize all variables. note that in this specific case since you have handles the head secanrio then you should not have a problem becuase m is set to temp later on, but still..

FIX#2 - make sure you delete the inner list completely before you free a node.

Here is the code (untested, sorry)

void delnode(outer_list *head,char num[100])
{
    outer_list *temp, *m;
    m=temp=head; /*FIX #1*/
    while(temp!=NULL) {
        if(strcmp(temp->word,num)==0) {
            if(temp==head) {
                head=temp->next;
                delinner(temp->inner_list); /* FIX#2 */
                free(temp);
                return;
            } else {
                m->next=temp->next;
                delinner(temp->inner_list); /* FIX#2 */
                free(temp);
                return;
            }
        } else {
            m=temp;
            temp= temp->next;
        }
    }
    printf(" ELEMENT %s NOT FOUND ", num);
}
void delinner(inner_list *head) { /* FIX#2 */
    inner_list *temp;
    temp=head;
    while(temp!=NULL) {
        head=temp->next;
        free(temp);
        temp=head;
    }
}

Answer 6

There's a big problem in that if you end up needing to delete the first element of the outer list, you never pass back the new head of the list. Your origuinal code needs changing as follows (also put in all the other good suggestions):

void delnode(outer_list **tbd,char num[100]) // pass a pointer to tbd
{
    outer_list *temp, *m;
    temp = *tbd;
    while(temp!=NULL)
    {
        if(strcmp(temp->word,num)==0)
        {
            if(temp==*tbd)
            {
                // Delete the inner list here
                *tbd=temp->next;
                free(temp);
                return;
            }
     // rest of function

You'd call it like this:

outer_list* myList;

// lots of code including initialising and adding stuff to the list

delnode(&mylist, wordtoDelete);  // note the '&' sign