Linked-lists and deleting nodes through *headRef

4
votes

I'm working through some pointer/linked-list problems. One of the problems is to delete all nodes in a list and point the head to NULL.

My solution differs from the given answer. I'm new to this, so I'm having trouble figuring out if and why mine doesn't work. The main problem I'm having is trying to understand what the result of free(*headRef); is, and if *headRef can share a different pointee after that.

My thinking is: because I have compliment point to the next node, I can free *headRef which is pointing at the first node (or, more generally, the node before the one compliment is pointing to). Then, I can point *headRef to compliment and the process can continue.

Here's my code:

void DeleteList(struct node** headRef){

    struct node* compliment = *headRef;

    while (compliment != NULL){
            compliment = compliment->next;
            free(*headRef);
            *headRef = compliment;
    }
    *headRef = NULL;
}

Assume each node carries two attributes: an int and a ->next pointer.

2
cpointersdata-structureslinked-list
What problem are you having? - imreal
You're in trouble if headRef is NULL. The *headRef = NULL; after the while isn't necessary. Otherwise, looks okay. - Daniel Fischer
@DanielFischer- I would assume that the caller should never be passing a NULL pointer into this function. I'm guessing the intended usage is DeleteList(&pointerToHeadOfList). - templatetypedef
@templatetypedef Correct. I could have thrown in an assert(), I suppose. However, this is an exercise so I admit I cut some corners. - d0rmLife

2 Answers

5
votes

The code that you've posted is fine. The key step in deleting all nodes is to make sure that you don't try deleting a pointer and then following its next pointer. Since you use the compliment pointer to hold the next node on each iteration, what you have looks fine.

As for free(*headRef) - this deallocates the pointer pointed at by headRef. Once you've done this, you should be sure not to follow the pointer *headRef anymore. Since you immediately change *headRef in the next line to point to the next node in the linked list, you don't have anything to worry about. The main concern is not to free a pointer and then try dereferencing it. freeing a pointer doesn't somehow "poison" the pointer variable and make it bad; instead it destoys the pointee and makes that bad.

One detail - the very last line of your function isn't necessary, since when you visit the last node of the linked list and traverse its next pointer, you will get NULL. This means that the final iteration of the loop will set *headRef to point to NULL for you.

Hope this helps!

1
votes

You could do with less code:

void DeleteList(struct node **headRef){

    struct node *tmp;

    while ((tmp = *headref)){
            *headRef = tmp->next
            free(tmp);                
    }
}

Explanation:

  • you can only get into the loop if there is something to delete at *headref
  • inside the loop: tmp cannot be NULL, so it is safe to dereference tmp, so *headref = tmp->next; is valid
  • after the loop, there is a guarantee that *headref == NULL