Home > Software engineering >  How to remove a node in a pointer to linked list?
How to remove a node in a pointer to linked list?

Time:03-18

I'm trying to remove the last node of a linked list while returning its value. But all this pointers is confusing, like am I really removing it by calling p = NULL??

typedef struct node {
    ElemType val;
    struct node *next;
} NODE;

struct list_struct {
    NODE *front;
    NODE *back;
};

/**
If list is empty, do nothing and return arbitrary value
otherwise, the last element in the list is removed and its value is returned.
**/
ElemType popBack(LIST *l) {
    NODE *p = l->front;
    NODE *previous = NULL;
    while (p != NULL) {
        if (p->next == NULL) {
            ElemType value = p->val;
            p = NULL;
            l->back = previous;
            return value;
        }
        previous = p;
        p = p->next;
    }
    return DEFAULT;
}

CodePudding user response:

For starters to use a singly-linked list to remove its last element is not an efficient approach. Instead you should use in this case a doubly-linked list.

Nevertheless in any case you need to free the memory occupied by the deleted node and correctly update not only the pointer back but also the pointer front of the list and the data member next of the pointer previous.

The function can look the following way

ElemType popBack( LIST *l)  
{
    ElemType value = DEFAULT;

    if ( l->front != NULL )
    {
        if ( l->front->next == NULL )
        {
            value = l->front->val;
            free( l->front );
            l->front = l->back = NULL;
        }
        else
        {
            node *current = l->front;

            while ( current->next->next != NULL )
            {
                current = current->next;
            }
        
            value = current->next->val;
        
            free( current->next );
            current->next = NULL;

            l->back = current;
        }
    }

    return value;
}
  • Related