slow_hare's blog

Recursive Function to delete a Node in the linked list.
By slow_hare, history, 3 years ago, In English 
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.

  • Vote: I like it
  • -28
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the point in deleting an element in $$$\mathcal{O}(n)$$$ time? Please don't use linked list when other data structures work better.

Second, there is already a singly-linked list and a doubly-linked list in C++ standard library (std::forward_list and std::list).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we have to use inbuilt list and forward_list then what's the point in reading even a single line about Linked List

    It's not about the Time complexity, it's about the different cases we have to handle while doing operations on a linked list.

    I thought this way, coded this function so as to avoid handling different cases while deleting a node in the linked list.

    Thanks anyways :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      If we have to use inbuilt list and forward_list then what's the point in reading even a single line about Linked List

      Well, you kinda have to know how structures work to use them correctly and efficiently. This post is clearly an example of inefficiency. Time complexity always matters, not only in competitive programming. The only case when using linked list and deleting data by value is OK is when you have a very large array stored on disk that you often update but seldom erase, but that's still iffy.

      I thought this way, coded this function so as to avoid handling different cases while deleting a node in the linked list.

      What were these different cases? The only two cases I see is when the element is present in set and when it's not present. Even then, your implementation is far from being optimal because of recursion. Try rewriting it to a while loop.

      → Reply