Code for deletion of last node of linked list not working

Question

I am trying to perform insertion and deletion operation on singly linked list, but the deletelast() (deleting the last node of the linked list) function is not working for a linked list having more than 2 nodes.

Here is the code:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};
typedef struct node node;

node *head = NULL;

void insertbegin(int *a)
{
    node *newnode = (node *)malloc(sizeof(node));
    newnode->next = head;
    head = newnode;
    newnode->data = *a;
    printf("success!!");
}

void display()
{
    if (head != NULL)
    {
        node *temp = head;
        while (temp != NULL)
        {
            printf("%d\t", temp->data);
            temp = temp->next;
        }
    }
    else if (head == NULL)
    {
        printf("the linked list is empty\n");
    }
}

void insertlast()
{
    int b;
    printf("enter the value of the element:\n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->next == NULL)
        {
            temp->next = newnode;
            newnode->next = NULL;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
    temp = NULL;
}

void insertspecific()
{
    int n, b;
    printf("enter the value after which you want to insert a node: \n");
    scanf("%d", &n);
    printf("enter te data of the node to be inserted: \n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->data == n)
        {
            newnode->next = temp->next;
            temp->next = newnode;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
}

void deletebegin()
{
    if (head == NULL)
        printf("the list is empty.\n");
    else
    {
        node *newhead = head;
        head = newhead->next;
        printf("success deletion");
        free(newhead);
    }
}

void deletelast()
{
    if (head == NULL)
    {
        printf("the list is empty\n");
    }
    else if (head->next->next == NULL)
    {
        node *temp = NULL;
        temp = head->next;
        head->next = NULL;
        free(temp);
        temp = NULL;
    }
    else
    {
        node *temp = head;
        node *ptr = NULL;
        while (temp != NULL)
        {
            if (temp->next->next == NULL)
            {  
                ptr = temp->next;
                temp->next == NULL;
                free(ptr);
                ptr = NULL;
            }
            temp = temp->next;
        }
        printf("deleted the node from the last\n");
    }
}

void main()
{
    int a;
    int choice = 0;
    while (choice != 9)
    {
        printf("\n\n*********Main Menu*********\n");
        printf("\nChoose one option from the following list ...\n");
        printf("\n===============================================\n");
        printf("\n1.Insert at begining\n2.Insert at last\n3.Insert after a specific position\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.traverse\n8.Display the Linked list\n9.Exit\n");
        printf("\nEnter your choice?\n");
        scanf("\n%d", &choice);
        switch (choice)
        {
        case 1:
            printf("enter the value you want to insert: \n");
            scanf("%d", &a);
            insertbegin(&a);
            break;
        case 2:
            insertlast();
            break;
        case 3:
            insertspecific();
            break;
        case 4:
            deletebegin();
            break;
        case 5:
            deletelast();
            break;
        case 6:
            // deletespecific();
            break;
        case 7:
            // traverse();
            break;
        case 8:
            display();
            break;
        case 9:
            exit(0);
            break;
        default:
            printf("Please enter valid choice..");
        }
    }
}

I am inserting the nodes using the insertbegin() function and using the display() function to view the linked list but the deletelast() function is working and giving no output for more than 2 nodes. My logic was to traverse the linked list using temp pointer and when I reach the second last node, I change the its next value to NULL and free the last node using ptr pointer... but for some reason it is not working.

I am fairly new to DSA.

My output screen when I run the deletelast() function

Answer 1

For starters it is a bad idea to define functions such a way that they depend on a global variables as in your code where function definitions depend on the global variable head. In this case you will be unable or it will be very hard for example to use two lists in a program simultaneously.

Passing an integer to the function insertbegin through a pointer to it

void insertbegin(int *a)

does not make sense. The function should be declared like

void insertbegin(int a)

Within the function display the pointer temp should be declared as having type const node *

void display()
{
    if (head != NULL)
    {
        const node *temp = head;
        //...

because the list within the function is not changed.

And instead of else if

else if (head == NULL)

there is enough to use just else

else
//...

The function insertlast has several drawbacks.

void insertlast()
{
    int b;
    printf("enter the value of the element:\n");
    scanf("%d", &b);
    node *temp = head;
    node *newnode = (node *)malloc(sizeof(node));
    while (temp != NULL)
    {
        if (temp->next == NULL)
        {
            temp->next = newnode;
            newnode->next = NULL;
            newnode->data = b;
        }
        temp = temp->next;
    }
    free(temp);
    temp=NULL;
}

For starters it should accept a value that will be inserted to the list through a parameter the same way as the function insertbegin So it should be declared at least like

void insertlast( int b );

The function inserts nothing if the list is empty that is when head is equal to NULL. And if the list is empty and a value is inserted in the list then the pointer head shall be changed.

If the list is not empty then this while loop

while (temp != NULL)
{
    if (temp->next == NULL)
    {
        temp->next = newnode;
        newnode->next = NULL;
        newnode->data = b;
    }
    temp = temp->next;
}

is an infinite loop.

The function can be declared and defined the following way

int insertlast( int data )
{
    node *newnode = malloc( sizeof( *newnode ) );
    int success = newnode != NULL;

    if ( success )
    {
        newnode->data = data;
        newnode->next = NULL;

        if ( head == NULL )
        {
            head = newnode;
        }
        else
        {       
            node *temp = head;

            while ( temp->next != NULL ) temp = temp->next;

            temp->next = newnode;
        }
    }

    return success;
}

The function insertspecific also should not ask any question to the user. It is the caller of the function that should provide required values through function parameters. The function does not report to the user whether a node with the specified value was found in the list. If such a node is not found the function will produce a memory leak. So at least before allocating a new node you need at first to find the target node after which the new node will be inserted.

The function deletelast is also invalid.

void deletelast()
{
    if (head == NULL)
    {
        printf("the list is empty\n");
    }
    else if(head->next->next==NULL)
    {
        node *temp=NULL;
        temp=head->next;
        head->next=NULL;
        free(temp);
        temp=NULL;
    }
    else
    {
        node *temp = head;
        node *ptr=NULL;
        while (temp != NULL)
        {
            if (temp->next->next == NULL)
            {  
                ptr=temp->next;
                temp->next == NULL;
                free(ptr);
                ptr=NULL;
            }
            temp=temp->next;
        }
        printf("deleted the node from the last\n");
    }
}

For example if the list has only one node then this if statement

else if(head->next->next==NULL)

invokes undefined behavior. And it is unclear why it is present in the function.

The same problem with undefined behavior exists in the following while loop in this if statement

if (temp->next->next == NULL)

after deleting the last node because the loop continues its iterations.

Using your approach the function can look the following way.

void deletelast()
{
    if ( head == NULL )
    {
        printf("the list is empty\n");
        return;            
    }

    if ( head->next == NULL )
    {
        node *temp = head;
        head = NULL;
        free( temp );
    }
    else
    {
        node *temp = head;

        while ( temp->next->next != NULL ) temp = temp->next;

        free( temp->next );
        temp->next = NULL;
    }

    puts( "deleted the node from the last" );
}

And pay attention to that according to the C Standard the function main without parameters shall be declared like

int main( void )

Answer 2

Imagine you have an empty list: your first branch detects there's nothing to do.

Imagine that you have a list with one node only:

• head is not NULL and points to the sole node;
• head->next points to NULL;
• head->next->next is undefined behavior, because you try to dereference an NULL pointer. OUCH !!

A better version of this code would then be:

else if(head->next==NULL)    // list with only one node
{
    free(head);             // delete the node
    head=NULL;              // and the list is empty now
}

If you have more than one node, you'd land in the else branch. Unfortunately, in this branch you try the next->next again, and it will fail for the same reasons.

This being said, there is no need to make a difference between a list of one and more than one node. You could therefore simplify and process both in the same kind of loop:

while (head) {  // as long as there are nodes:  
    temp = head->next   // keep track of the next node before current is deleted
    free (head);        // kill current node
    head = next;        // ready to process next node unless (could be null)
}

Even better, you no longer need if (head==NULL), because the loop process well this special case, doing nothing if head is NULL.