Recursive Function to delete a Node in the linked list.

Правка en5, от slow_hare, 2021-02-08 19:49:25
void del(node* &head, int val)
{
    if (head == NULL) {
        cout << "Element not present in the list\n";
        return;
    }
    if (head->info == val) {
        node* t = head;
        head = head->link;
        delete (t);
        return;
    }
    del(head->link, val);
}

Intuition:

  • We are passing node* (node pointer) as a reference to the 'del' function (as in node* &head).

  • Suppose node containing 'val' is the first node, head = head->next changes the actual head in the main function which now points to the current beginning of the list (which was second node before deletion).

  • Deleting any other node, now since current node* is derived from previous node's next and previous node's next is passed by reference , thus we can say that the pointer being on the current node can alter previous node's next.

  • Thus when we do head = head->next means previous node's next gets changed to head->next which is the required operation while deletion of a node in the linked list.

  • Thus there is no need to have a separate case for deletion of first node or last node.

Теги #data structure, #linked list, #recursion, #delete

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский slow_hare 2021-02-08 19:49:25 40
en4 Английский slow_hare 2021-02-08 19:43:09 1559
en3 Английский slow_hare 2021-02-08 19:21:00 10
en2 Английский slow_hare 2021-02-08 19:14:45 13
en1 Английский slow_hare 2021-02-08 19:10:58 2823 Initial revision (published)