Optimized Recursive function to delete a node of a linked list containing the given value .

Revision en1, by slow_hare, 2021-02-08 19:10:58

Examples:

INPUT: Linked list = 15 -> 14 -> 12 -> 10 and val = 14

OUTPUT: 15 -> 12 -> 10

INPUT: Linked list = 15 -> 12 -> 10 and val = 20

OUTPUT: Element not present in the list

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.

Linked List implementation code:

//Author: @yoji_20 aka Yogesh Vaishnav
#include<bits/stdc++.h>
using namespace std;

struct node{
	int info;
	node *link = NULL;
	node(){}
	node(int a):info(a){}
};


//Deletes the node containing 'info' part as val and alter the head of the linked list

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);
}



//Utility function to add a node in the linked list
void push(node* &head, int data){
	node* newNode = new node(data);
	newNode->link = head;
	head = newNode;
}


//Utility function to print the linked list (recursive method)
void print(node* head){
	if(head == NULL and cout<<endl)return; //cout<<endl gets implicitly typecasted to bool value 'true'
	cout<<head->info<<' ';
	print(head->link);
}

int main(){
	
	node* head = NULL;
	push(head, 10);
	push(head, 12);
	push(head, 14);
	push(head, 15);
	print(head);
	del(head, 20);
	print(head);
	del(head,10);
	print(head);
	del(head,14);
	print(head);
	del(head, 15);
	print(head);
	
	return 0;
}

OUTPUT: 15 14 12 10 Element not present in the list 15 14 12 10 15 14 12 15 12 12

Tags #data structure, #linked list, #recursion, #delete

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English slow_hare 2021-02-08 19:49:25 40
en4 English slow_hare 2021-02-08 19:43:09 1559
en3 English slow_hare 2021-02-08 19:21:00 10
en2 English slow_hare 2021-02-08 19:14:45 13
en1 English slow_hare 2021-02-08 19:10:58 2823 Initial revision (published)