Why does this Linked List C function not work properly if previousNode->next is not set to NULL?

Question

Node* deleteAtTail(Node* head)
{
    if (head == NULL)                               /* If List is empty... */
    {
        return NULL;
    }
    else                                            /* If List has 1 item... */
    if (head -> next == NULL)
    {
        free(head);
        return NULL;
    }
    else
    {
        Node* currentNode = head;                   /* Traversal Pointer */
        Node* previousNode = NULL;                  /* Traversal Pointer */

        while(currentNode -> next != NULL)
        {
            previousNode = currentNode;             /* Move up previous node */
            currentNode = currentNode -> next;      /* Move up current node */
        }

        previousNode -> next = NULL;                /* Make previousNode the new tail */
        free(currentNode);                          /* Delete currentNode pointer */
        return head;
    }
}

If I remove/comment out previousNode -> next = NULL;, the program falls into an infinite loop.

Why is this the case? It seems to me that head and its list is unchanged, only copied to the currentNode pointer, and I am returning an unchanged list. previousNode and currentNode stay within the scope of the function, so why is it that the program fails if previousNode's next pointer is not set to NULL?

Debugging requests should include a minimal reproducible example. In this case, the error in your routine is obvious, but explaining the particular details of how the enclosing program fails due to this error would require seeing the program. Likely, your program tries to use the list again after deleteAtTail is called, and then the list had been corrupted by the error in deleteAtTail. While your reasoning that previousNode and currentNode exist only during the function’s execution, they are only pointers to nodes that exist in the list beyond the function’s execution. You must handle those nodes correctly. — Eric Postpischil
– Eric Postpischil, Commented Jul 9, 2024 at 20:10

Chris · Accepted Answer · 2024-07-09 21:24:13Z

2

You've freed the last node in the list (currentNode). If you don't set previousNode->next (which was the same pointer as currentNode) to NULL then you're left with a dangling pointer, and iterating over the list can invoke undefined behavior when it tries to dereference that pointer.

I would suggest refactoring your code a bit. As both guards return, the else is extraneous and the extra indentation can be elided.

Node* deleteAtTail(Node* head) {
    if (head == NULL) {
        return NULL;
    }
    
    if (head->next == NULL) {
        free(head);
        return NULL;
    }

    Node* currentNode = head; 
    Node* previousNode = NULL;    

    while (currentNode->next != NULL) {
        previousNode = currentNode;  
        currentNode = currentNode->next; 
    }

    previousNode->next = NULL;
    free(currentNode); 

    return head;
}

Further, we can identify the second to last node with just one pointer if we stop currentNode at the next to last node. We can also realize that NULL is false, and use that to streamline our conditions.

Node* deleteAtTail(Node* head) {
    if (!head) {
        return NULL;
    }
    
    if (!head->next) {
        free(head);
        return NULL;
    }

    Node* currentNode = head;   

    while (currentNode->next && currentNode->next->next) {
        currentNode = currentNode->next; 
    }

    free(currentNode->next); 
    currentNode->next = NULL;

    return head;
}

edited Jul 9, 2024 at 21:24

answered Jul 9, 2024 at 20:06

Chris

38.2k6 gold badges33 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user17592432 Over a year ago

Pretty sure while (currentNode->next->next) { is all that is needed at that point in the function...

Barmar · Accepted Answer · 2024-07-09 20:15:27Z

0

The last node in a linked list is the one whose next pointer contains NULL.
In order to remove the last node in a list, you need to make the 2nd-to-last name the last node.
Ergo, you must set the next pointer of the 2nd-to-last node to NULL.

The loop ends when currentNode points to the last node and previousNode points to the 2nd-to-last node. So previousNode->next = NULL; accomplishes the above requirement, and free(currentNode); reclaims the memory of the node that's being removed.

answered Jul 9, 2024 at 20:15

Barmar

789k57 gold badges555 silver badges669 bronze badges

Comments

BMAGS · Accepted Answer · 2024-07-09 20:24:26Z

-1

I figured it out myself. I was thinking in terms of values with currentNode and previousNode, and not recognizing that they are the literal memory addresses. I was thinking that currentNode is just a variable that copied the value of head, and not that it literally is head. I hope I explained that clearly and correctly. Just a silly CS student mistake...

answered Jul 9, 2024 at 20:24

BMAGS

291 silver badge4 bronze badges

1 Comment

Eric Postpischil Over a year ago

currentNode is not head. It is a pointer. It is initially set to head, which means its value (an address) is a copy of the value of head (also an address). It is not head. They both point to the same node (until currentNode) is changed. It is the node in the list that must be changed; the next member of the new last node of the list must be changed. If you are to be successful with C, you must learn the difference between a pointer to a thing and the thing itself.

Collectives™ on Stack Overflow

Why does this Linked List C function not work properly if previousNode->next is not set to NULL?

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related