Delete last node of single linked list using tail pointer

0
votes

I'm creating a singly linked list in C which has head and tail pointers where the head pointer points to starting node of SLL and tail pointer points to the last node of SLL. I don't want to traverse till the end of the list using the head pointer to delete the node. Is there a way so that I can use the tail pointer to delete the last element of SLL?

Following is node addition function. head and tail are initiated NULL.

void add_node_last(Node** head, Node** tail, int data) {

    Node* new_node = (Node *) malloc(sizeof(Node));

    new_node -> data = data;
    new_node -> ptr  = NULL;

    if(*head == NULL && *tail == NULL) {
        *head = new_node;
        *tail = new_node;
        return;
    }

    (*tail) -> ptr = new_node;

    *tail = new_node;

}

To delete the first node, the following function is used:

void del_first(Node **head) {
    if(*head == NULL) {
        return;
    }
    *head = (*head) -> ptr;
    free(*head);
}
2
cpointerslinked-listsingly-linked-list
BTW free(*head); is wrong. - BLUEPIXY
@BLUEPIXY What is correct statement then? - Plochie
Node *temp = *head; *head = (*head) -> ptr; free(temp); Also if become *head == NULL then Need set tail to NULL. - BLUEPIXY
Can u elaborate why its wrong? - Plochie
After updating it destroys the list. - BLUEPIXY

2 Answers

2
votes

You can free the node's memory, but only once. After the first removal, your tail pointer, and the ptr of the second to last node, will be invalid pointers. In order to make sure both pointers are always correct you either need to traverse the entire list or make it a doubly linked list.

That's a long way of saying no (thanks to @stark).

0
votes

in order for this to work without making it a doubly linked list, you could have the tail's *next pointer point to the head of the list, then traverse through it till you reach the node before the tail. once there you can NULL its *next pointer which would essentially detach the original tail from the list. you would then set the tail to the current node, then finally free the original tail.

void del_last(Node **head, Node **tail) {
    struct node *new_head = *head;
    struct node *current = *tail;

    current->next = head;

    while(current-> != *tail)    //getting the node right before the original tail
    {
         current = current->next
    }

    current->next = NULL;   //detaches original tail form list

    free(**tail);   //gets rid of original tail
    **tail = current;   // sets current node to tail pointer
}