CODEWITHSUNDEEP
cpointersdata-structureslinked-listsingly-linked-list
BMAGS
BMAGS

Reputation: 29

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

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?

Upvotes: 2

Views: 71

Answers (3)

Chris
Chris

Reputation: 36611

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;
}

Upvotes: 2

BMAGS
BMAGS

Reputation: 29

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...

Upvotes: -1

Barmar
Barmar

Reputation: 781878

  • 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.

Upvotes: 0

Related Questions