Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

I discussed the introduction of linked lists and list insertion in my previous article on single linked lists. Let’s develop problem statements to understand the deletion process. Given a “key”, deletes the first occurrence of that key in the linked list.

Iteration: To remove a node from a linked list, we do the following steps.

  1. Find the last node of the node you want to delete.
  2. Change the next of the previous node.
  3. Free memory of the node to be deleted.

Since each node of the linked list is dynamically allocated in C using malloc(), we need to call free() to free the memory allocated for the node to be deleted.

#include <bits/stdc++.h>
using namespace std;

class Node{
public:
	int data;
	Node* next;
};
void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void deleteNode(Node** head_ref, int key)
{
	Node* temp = *head_ref;
	Node* prev = NULL;
	if(temp ! =NULL && temp->data == key)
	{
		*head_ref = temp->next; 
		delete temp;		 
		return;
	}
	else
	{
	while(temp ! =NULL&& temp->data ! = key) { prev = temp; temp = temp->next; }if (temp == NULL)
		return;
	prev->next = temp->next;
	deletetemp; }}void printList(Node* node)
{
	while(node ! =NULL)
	{
		cout << node->data << ""; node = node->next; }}int main(a)
{
	Node* head = NULL;
	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;
}
Copy the code

The output

Created Linked List: 
 2  3  1  7 
Linked List after Deletion of 1: 
 2  3  7
Copy the code

Recursive method:

To recursively remove the nodes of the linked list, we need to perform the following steps.

1. We pass node* (node pointer) as a reference to a function (e.g. Node * &head)

2. Now due to the current node pointer is next to a node in the former (pass by reference) derived, so now if change the value of the current node pointer, the previous value of the next node will also change, this is the operations necessary to delete the node (that is, pointing to a node before the next of the current node (including key) the next).

3. Find the node that contains the specified value.

4. Store this node for later unallocation using the free() function.

5. Change the pointer to this node to point to its next, and get the correct link by executing the next of the previous node.

The following is an implementation of the above method.

#include <bits/stdc++.h>
using namespace std;

struct node {
	int info;
	node* link = NULL;
	node() {}
	node(int a)
		: info(a)
	{
	}
};
void deleteNode(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;
	}
	deleteNode(head->link, val);
}
void push(node*& head, int data)
{
	node* newNode = new node(data);
	newNode->link = head;
	head = newNode;
}
void print(node* head)
{
	if (head == NULL and cout << endl)
		return;
	cout << head->info << ' ';
	print(head->link);
}

int main(a)
{
	node* head = NULL;
	push(head, 10);
	push(head, 12);
	push(head, 14);
	push(head, 15);
	print(head);

	deleteNode(head, 20); 
	print(head); 
	deleteNode(head, 10);
	print(head);
	deleteNode(head, 14);
	print(head);
	return 0;
}
Copy the code

The output

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

🥇 past quality articles

Teach you make a small game gobang in Java Single AI minesweeping game using the python list of singly linked list data structure is introduced | first set of singly linked list data structure in the linked list and array | second singly linked list data structure of chain table insert | third taught you how to use python snake game Make a great weather Web application using HTML, CSS, JS, and apis

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.