Why is the function for deleting the last node of the linked list not working?

Question

The function deleteLast() is not working.

struct node
{
    int data;
    struct node* next;
};
struct node *head=NULL, *newNode, *temp;

void insertFirst(int data)
{
    newNode= new node;
    newNode->data=data;
    newNode->next=head;
    head=newNode;
}

void deleteFirst()
{
    newNode=head;
    head=head->next;
    free(newNode);
}

void deleteLast()
{
    newNode=head;
    while(newNode->next!=NULL)
    {
        newNode=newNode->next;
        temp=newNode->next;
    }
    newNode->next=NULL;
    free(temp);

}

void print()
{
    newNode=head;
    while(newNode!=NULL)
    {
        printf("%d ",newNode->data);
        newNode=newNode->next;
    }
    printf("\n");
}

int main()
{
    insertFirst(10);
    insertFirst(20);
    insertFirst(30);
    deleteLast();
    insertFirst(40);
    print();

    return 0;
}

The output is: 40 30 20 10.

If the deleteLast() function worked, the output would be: 40,30,20.

The function is supposed to remove the last node of the linked list. So, where is the mistake in the function?

Update: Now it works after I edited the function this way:

void deleteLast()
{
    newNode=head;
    while(newNode->next->next!=NULL)
    {
        newNode=newNode->next;
        temp=newNode->next;
    }
    newNode->next=NULL;
    free(temp);

}

Answer 1

For starters instead of the C function free you shall use the C++ operator delete.

Provided that initially the pointer head is not equal to nullptr then after this while loop the pointer newNode->next is equal to NULL while the pointer temp has either an indeterminate value or is equal to NULL.

void deleteLast()
{
    newNode=head;
    while(newNode->next!=NULL)
    {
        newNode=newNode->next;
        temp=newNode->next;
    }
    newNode->next=NULL;
    free(temp);

}

Also if the deleted node is the node pointed to by head then the pointer head is not updated.

Using your approach with global variables (it is a bad approach when functions depend on global variables) the function can be defined the following way

void deleteLast()
{
    if ( head )
    {
        if ( head->next == nullptr )
        {
            delete head;
            head = nullptr;
        }
        else
        {
            newNode = head;

            while ( newNode->next->next ) newNode = newNode->next;

            delete newNode->next;
            newNpde->next = nullptr;
        }
    }
}

Also within the function deleteFirst you shall check whether the pointer head is equal to nullptr.

Answer 2

There are a number of problems with your code:

• Using global variables for local tasks is bad design. There is no reason for newNode or temp to be global at all.

• Mixing new with free() is undefined behavior. You need to delete anything you new.

• Neither deleteFirst() nor deleteLast() are accounting for the possibility that the list may be empty (ie, when head is NULL).

• main() is leaking memory. It is not freeing any of the nodes it creates before exiting.

Now, to answer your question -

The logic in deleteLast() is simply wrong. You are free()'ing the wrong node. Provided that head is not NULL, when your loop ends, newNode is pointing at the last node, and temp is NULL. You are not removing the last node at all, you are merely setting the last node's next member to NULL (which it already is) and then you are calling free() with a NULL pointer as input, which is a no-op.

You need to set the 2nd-to-last node's next member to NULL, and then delete the last node. Also, when the list contains only 1 node in it, the last node is the head node, but deleteLast() is not setting head to NULL in that scenario.

With that said, try this instead:

#include <iostream>

struct node
{
    int data;
    node* next;
};
node *head = NULL;

void insertFirst(int data)
{
    node *newNode = new node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

void deleteFirst()
{
    if (head != NULL)
    {
        node *temp = head;
        head = head->next;
        delete temp;
    }
}

void deleteLast()
{
    if (head != NULL)
    {
        node *temp = head, *prev = NULL;
        while (temp->next != NULL)
        {
            prev = temp;
            temp = temp->next;
        }
        if (prev)
            prev->next = NULL;
        else
            head = NULL;
        delete temp;
    }
}

void deleteAll()
{
    while (head != NULL)
    {
        node *temp = head->next;
        delete head;
        head = temp;
    }
}

void print()
{
    node *temp = head;
    while (temp != NULL)
    {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    std::cout << "\n";
}

int main()
{
    insertFirst(10);
    insertFirst(20);
    insertFirst(30);
    print();

    deleteLast();
    insertFirst(40);
    print();

    deleteAll();
    print();

    return 0;
}

Online Demo

Alternatively, deleteLast() can be implemented like this instead, eliminating the need for the prev variable:

void deleteLast()
{
    if (head != NULL)
    {
        node **temp = &head;

        while ((*temp)->next != NULL) {
            temp = &((*temp)->next);
        }

        delete *temp;
        *temp = NULL;
    }
}

Online Demo

That being said, you really should be using the standard std::list container instead of a manual implementation, eg:

#include <iostream>
#include <list>

std::list<int> myList;

void print()
{
    for (auto data : myList) {
        std::cout << data << " ";
    }
    std::cout << "\n";
}
     
int main()
{
    myList.push_front(10);
    myList.push_front(20);
    myList.push_front(30);
    print();

    myList.pop_back();
    myList.push_front(40);
    print();

    myList.clear();
    print();

    return 0;
}

Online Demo