deletion of single linked list
When it comes to deleting a node from a linked list, there are several situations that may arise. Here are some common scenarios:
- Deleting the first occurrence of a node with a given data value:
Traverse the linked list from the head node onwards. Find the node with the specified data value. Adjust the next pointers of the previous and current nodes to bypass the node to be deleted. Free the memory allocated for the node. - Deleting a node at a given position:
Traverse the linked list to the node at the specified position. Adjust the next pointers of the previous and current nodes to skip the node to be deleted. Free the memory allocated for the node. - Deleting a node given a pointer to that node:
Update the next pointer of the previous node to bypass the node to be deleted. Free the memory allocated for the node.
Deleting the first occurrence of a given Data Value:
When it comes to deleting the first occurrence of a node with a given data value in a linked list, you can follow these steps:
- Find the previous node of the node to be deleted:
Traverse the linked list starting from the head node and stop when the next node's data value matches the given key. Keep track of the previous node while traversing. - Change the next pointer of the previous node:
Once the previous node is found, update its next pointer to skip the node to be deleted. Set it to point to the next node after the node is deleted. - Free the memory for the node to be deleted:
Release the memory allocated for the node that is no longer needed.
implementation in Java to delete the first occurrence of a node with a given data value in a linked list:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void deleteNode(int key) {
Node current = head;
Node previous = null;
// Check if the head node itself contains the key
if (current != null && current.data == key) {
head = current.next;
return;
}
// Traverse the linked list to find the node to be deleted
while (current != null && current.data != key) {
previous = current;
current = current.next;
}
// If the node is not found
if (current == null) {
return;
}
// Update the next pointer of the previous node to skip the node to be deleted
previous.next = current.next;
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating nodes
Node node1 = new Node(4);
Node node2 = new Node(3);
Node node3 = new Node(2);
Node node4 = new Node(1);
Node node5 = new Node(0);
// Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0
list.head = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
// Deleting the node with data value 2
list.deleteNode(2);
// Displaying the updated linked list: 4 -> 3 -> 1 -> 0
list.display();
}
}
In this Java code, we have a Node class representing each node in the linked list. The LinkedList class serves as a container for the nodes and provides methods for manipulating the list.
The deleteNode method is used to delete the first occurrence of a node with the given data value. It takes the key as a parameter and follows the steps mentioned above to find the previous node of the node to be deleted and update the next pointer of the previous node.
The display method is used to print the data values of all the nodes in the list by traversing the list from the head to the last node.
In the main function, we create an instance of the LinkedList class. Nodes with values 4, 3, 2, 1, and 0 are created and linked together. We then delete the node with a data value of 2 using the deleteNode method. Finally, the contents of the updated linked list are displayed using the display method.
The output of this program will be:
4 3 1 0implementation in C++ to delete the first occurrence of a node with a given data value in a linked list:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
public:
Node* head;
LinkedList() {
this->head = nullptr;
}
void deleteNode(int key) {
Node* current = head;
Node* previous = nullptr;
// Check if the head node itself contains the key
if (current != nullptr && current->data == key) {
head = current->next;
delete current;
return;
}
// Traverse the linked list to find the node to be deleted
while (current != nullptr && current->data != key) {
previous = current;
current = current->next;
}
// If the node is not found
if (current == nullptr) {
return;
}
// Update the next pointer of the previous node to skip the node to be deleted
previous->next = current->next;
delete current;
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Creating nodes
Node* node1 = new Node(4);
Node* node2 = new Node(3);
Node* node3 = new Node(2);
Node* node4 = new Node(1);
Node* node5 = new Node(0);
// Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0
list.head = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
// Deleting the node with data value 2
list.deleteNode(2);
// Displaying the updated linked list: 4 -> 3 -> 1 -> 0
list.display();
return 0;
}
Deleting a node at a given position:
- If the node to be deleted is the root node (position 0):
Update the head pointer to point to the next node, effectively deleting the root node. - If the node to be deleted is somewhere in between (position > 0):
i)Traverse the linked list starting from the head node and stop at the node just before the node to be deleted.
ii)Once the previous node is found, update its next pointer to skip the node to be deleted, effectively removing it from the list.
In both cases, memory for the deleted node can be freed to avoid memory leaks.
Java implementation to delete a node at a given position in a linked list:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void deleteNodeAtPosition(int position) {
if (head == null) {
return; // Empty list, nothing to delete
}
if (position == 0) {
head = head.next; // Update the head to skip the first node
return;
}
Node previous = head;
int count = 0;
// Traverse to the node just before the position
while (previous != null && count < position - 1) {
previous = previous.next;
count++;
}
if (previous == null || previous.next == null) {
return; // Invalid position, node not found
}
Node nodeToDelete = previous.next;
previous.next = nodeToDelete.next; // Update the next pointer to skip the node
// Free memory for the deleted node (optional, depending on the language)
nodeToDelete.next = null;
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating nodes
Node node1 = new Node(4);
Node node2 = new Node(3);
Node node3 = new Node(2);
Node node4 = new Node(1);
Node node5 = new Node(0);
// Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0
list.head = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
// Deleting the node at position 2 (data value 2)
list.deleteNodeAtPosition(2);
// Displaying the updated linked list: 4 -> 3 -> 1 -> 0
list.display();
}
}
In this Java code, we have a Node class representing each node in the linked list. The LinkedList class serves as a container for the nodes and provides methods for manipulating the list.
The deleteNodeAtPosition method is used to delete a node at a given position in the linked list. It takes the position as a parameter and follows the steps mentioned above to find the previous node of the node to be deleted, update the next pointer of the previous node, and free the memory for the deleted node if desired.
The display method is used to print the data values of all the nodes in the list by traversing the list from the head to the last node.
In the main function, we create an instance of the LinkedList class. Nodes with values 4, 3, 2, 1, and 0 are created and linked together. We then delete the node at position 2 (data value 2) using the deleteNodeAtPosition method. Finally, the contents of the updated linked list are displayed using the display method.
The output of this program will be:
4 3 1 0
The time complexity of this operation in the worst case is O(N) where N is the number of nodes in the Linked List.
C++ implementation to delete a node at a given position in a linked list:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
public:
Node* head;
LinkedList() {
this->head = nullptr;
}
void deleteNodeAtPosition(int position) {
if (head == nullptr) {
return; // Empty list, nothing to delete
}
if (position == 0) {
Node* temp = head;
head = head->next; // Update the head to skip the first node
delete temp;
return;
}
Node* previous = head;
int count = 0;
// Traverse to the node just before the position
while (previous != nullptr && count < position - 1) {
previous = previous->next;
count++;
}
if (previous == nullptr || previous->next == nullptr) {
return; // Invalid position, node not found
}
Node* nodeToDelete = previous->next;
previous->next = nodeToDelete->next; // Update the next pointer to skip the node
delete nodeToDelete; // Free memory for the deleted node
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Creating nodes
Node* node1 = new Node(4);
Node* node2 = new Node(3);
Node* node3 = new Node(2);
Node* node4 = new Node(1);
Node* node5 = new Node(0);
// Constructing the linked list: 4 -> 3 -> 2 -> 1 -> 0
list.head = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
// Deleting the node at position 2 (data value 2)
list.deleteNodeAtPosition(2);
// Displaying the updated linked list: 4 -> 3 -> 1 -> 0
list.display();
return 0;
}
Deleting a node whose pointer is given:
When it comes to deleting a specific node in a linked list when its pointer is given, we can follow the following approach:
- Copy the data from the next node to the node to be deleted: Since we don't have access to the previous node, we cannot update its next pointer. Instead, we can copy the data from the next node to the node that needs to be deleted. This allows us to preserve the linked list's structure while effectively removing the desired node.
- Delete the next node: Once we have copied the data, we can proceed to delete the next node in the linked list. This involves updating the current node's next pointer to skip the next node and releasing the memory allocated for the next node.
By using this approach, we can delete the desired node with a time complexity of O(1), making it an efficient solution.
Note that this approach assumes that the given node is not the last node in the linked list, as deleting the last node requires access to its previous node to update the next pointer.
Java implementation to delete a node in a linked list when its pointer is given:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void deleteNode(Node nodeToDelete) {
if (nodeToDelete == null || nodeToDelete.next == null) {
return; // Cannot delete the last node or a null node
}
Node nextNode = nodeToDelete.next;
nodeToDelete.data = nextNode.data;
nodeToDelete.next = nextNode.next;
nextNode.next = null; // Release the memory for the deleted node
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Inserting nodes
list.head = new Node(1);
Node secondNode = new Node(2);
Node thirdNode = new Node(3);
Node fourthNode = new Node(4);
list.head.next = secondNode;
secondNode.next = thirdNode;
thirdNode.next = fourthNode;
// Displaying the linked list before deletion
System.out.println("Linked List before deletion:");
list.display();
// Deleting the second node
list.deleteNode(secondNode);
// Displaying the linked list after deletion
System.out.println("Linked List after deletion:");
list.display();
}
}
The output of this program will be:
Linked List before deletion:
1 2 3 4
Linked List after deletion:
1 3 4
C++ implementation to delete a node in a linked list when its pointer is given:
#include <iostream>
struct Node {
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(nullptr) {}
void deleteNode(Node* nodeToDelete) {
if (nodeToDelete == nullptr || nodeToDelete->next == nullptr) {
return; // Cannot delete the last node or a null node
}
Node* nextNode = nodeToDelete->next;
nodeToDelete->data = nextNode->data;
nodeToDelete->next = nextNode->next;
delete nextNode; // Release the memory for the deleted node
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Inserting nodes
list.head = new Node(1);
Node* secondNode = new Node(2);
Node* thirdNode = new Node(3);
Node* fourthNode = new Node(4);
list.head->next = secondNode;
secondNode->next = thirdNode;
thirdNode->next = fourthNode;
// Displaying the linked list before deletion
std::cout << "Linked List before deletion:" << std::endl;
list.display();
// Deleting the second node
list.deleteNode(secondNode);
// Displaying the linked list after deletion
std::cout << "Linked List after deletion:" << std::endl;
list.display();
return 0;
}
No comments