Deleting a node ( Linked list) - Dieptranivsr/DroneIVSR GitHub Wiki

Let us formulate the problem statement to understand the deletion process. Given a ‘key’, delete the first occurrence of this key in the linked list.

Iterative Method:

To delete a node from the linked list, we need to do the following steps.

Find the previous node of the node to be deleted.
Change the next of the previous node.
Free memory for the node to be deleted. Since every node of the linked list is dynamically allocated using malloc() in C, we need to call free() for freeing memory allocated for the node to be deleted.

// A complete working C++ program to
// demonstrate deletion in singly
// linked list with class
#include <bits/stdc++.h>
using namespace std;

// A linked list node
class Node{
public:
	int data;
	Node* next;
};

// Given a reference (pointer to pointer)
// to the head of a list and an int,
// inserts a new node on the front of the
// list.
void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node();
	new_node->data = new_data;
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}

// Given a reference (pointer to pointer)
// to the head of a list and a key, deletes
// the first occurrence of key in linked list
void deleteNode(Node** head_ref, int key)
{
	// Store head node
	Node* temp = *head_ref;
	Node* prev = NULL;
	
	// If head node itself holds
	// the key to be deleted
	if (temp != NULL && temp->data == key)
	{
		*head_ref = temp->next; // Changed head
		delete temp;		 // free old head
		return;
	}

	// Else Search for the key to be deleted,
	// keep track of the previous node as we
	// need to change 'prev->next' */
	else
	{
	while (temp != NULL && temp->data != key)
	{
		prev = temp;
		temp = temp->next;
	}

	// If key was not present in linked list
	if (temp == NULL)
		return;

	// Unlink the node from linked list
	prev->next = temp->next;

	// Free memory
	delete temp;
	}
}

// This function prints contents of
// linked list starting from the
// given node
void printList(Node* node)
{
	while (node != NULL)
	{
		cout << node->data << " ";
		node = node->next;
	}
}

// Driver code
int main()
{
	// Start with the empty list
	Node* head = NULL;

	// Add elements in linked list
	push(&head, 7);
	push(&head, 1);
	push(&head, 3);
	push(&head, 2);

	puts("Created Linked List: ");
	printList(head);

	deleteNode(&head, 1);
	puts("\nLinked List after Deletion of 1: ");
	
	printList(head);
	
	return 0;
}

Output

   Created Linked List: 
    2  3  1  7 
   Linked List after Deletion of 1: 
    2  3  7

Recursive Method:

To delete a node of a linked list recursively we need to do the following steps.

We pass node* (node pointer) as a reference to the function (as in node* &head)
Now since current node pointer is derived from previous node’s next (which is passed by reference) so now if the value of the current node pointer is changed, previous next node’s value also gets changed which is the required operation while deleting a node (i.e points previous node’s next to current node’s (containing key) next).
Find the node containing the given value.
Store this node to deallocate it later using free() function.
Change this node pointer so that it points to it’s next and by performing this previous node’s next also get properly linked.

Untitleddesign

Below is the implementation of the above approach.

// C++ program to delete a node in
// singly linked list recursively

#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 (recursive method)
*/
void deleteNode(node*& head, int val)
{
	
	// Check if list is empty or we
	// reach at the end of the
	// list.
	if (head == NULL) {
		cout << "Element not present in the list\n";
		return;
	}
	// If current node is the node to be deleted
	if (head->info == val) {
		node* t = head;
		head = head->link; // If it's start of the node head
						// node points to second node
		delete (t); // Else changes previous node's link to
					// current node's link
		return;
	}
	deleteNode(head->link, val);
}

// Utility function to add a
// node in the linked list
// Here we are passing head by
// reference thus no need to
// return it to the main function
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)
{
	// cout<<endl gets implicitly
	// typecasted to bool value
	// 'true'
	if (head == NULL and cout << endl)
		return;
	cout << head->info << ' ';
	print(head->link);
}

int main()
{
	// Starting with an empty linked list
	node* head = NULL;

	// Adds new element at the
	// beginning of the list
	push(head, 10);
	push(head, 12);
	push(head, 14);
	push(head, 15);

	// original list
	print(head);

	deleteNode(head, 20); // Call to delete function
	print(head); // 20 is not present thus no change in the
				// list

	deleteNode(head, 10);
	print(head);

	deleteNode(head, 14);
	print(head);

	return 0;
}

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

Deleting a node ( Linked list) - Dieptranivsr/DroneIVSR GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️