[FIXED] Why deleting a node in linked list fails when explicitly using a variable to save the head of the list?

Issue

I'm using this function to create a list by pushing a new node to the front.

void push(struct Node **head, int newValue)
{    
    if (*head == NULL)
    {
        puts("List is empty. The first node will be created now... ");
    }
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->data = newValue;
    new_node->next = (*head);
    (*head) = new_node;
}

I'm populating the list by doing this:

  push(&head, 10);
  push(&head, 20);
  push(&head, 30);
  push(&head, 40);

This gives me the following list: 40->30->20->10

Now, I want to delete the element at the head of the list. Here's my delete function:

void delete (struct Node **head, int key)
{
    // struct Node *currentNode = (*head);
    
    if ((*head)->data == key)
    {
        struct Node *tmp = (*head);
        (*head) = (*head)->next;
        free(tmp);
    }
}

Then:

delete(&head, 40);
printList(head);

and I get the expected output (i.e. 30->20->10).

However, if I un-comment the struct Node *currentNode = (*head); line and use the currentNode pointer instead of (*head) like so:

void delete (struct Node **head, int key)
{
    struct Node *currentNode = (*head);

    //if the key is at HEAD (the first node)
    if (currentNode->data == key)
    {
        struct Node *tmp = currentNode;
        currentNode = currentNode->next;
        free(tmp);
    }
}

, and I call delete(&head, 40) and printList(&head) again, Iget some values that I believe are garbage (i.e. 0->1).

My printList is this:

void printList(struct Node *list)
{
    int index = 0;
    
    while (list != NULL)
    {
        index++;
        list = list->next;
    }
}

and Node is this:

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

What's going on?

Update

For this struct,

struct Test
{
    int x;
};

int main()
{
    struct Test *myPtr = malloc(sizeof(struct Test));
    myPtr->x = 111;
    printf("Before copyStructOne x is: %d\n", myPtr->x);

    copyStructOne(&myPtr);
    //would expect this print 111 and not 500
    printf("After copyStructOne x is: %d\n", myPtr->x); 
}
void copyStructOne(struct Test **testPtr)
{
 //doesn't this create a local copy like in my original question?
    struct Test *testStr = (*testPtr); 
    testStr->x = 500;
    printf("Inside copyStructOne x is: %d\n", testStr->x);
}

Solution

In the case where you're using currentNode, it contains a copy of what is in *head. However, you only modify the copy, not *head, so the head of the list doesn't actually change. So after the function returns, head now points to memory that has been freed, so reading that pointer triggers undefined behavior.

The reason for passing a pointer-to-pointer is to allow a pointer in the calling function to be modified by the called function.

Answered By - dbush

Answer Checked By - Cary Denson (PHPFixing Admin)