Delete a Node From Linked List
Introduction
This article will show how to delete a node from a linked list. The steps involved in this operation, the importance of considering special conditions such as the head and node, and the impact of this procedure. By understanding the logic behind removing a node from a linked list, You can apply this knowledge to design different solutions to different computational challenges.
Why do we need to delete a node from the linked list?
Deleting a node from a linked list is a necessary process allowing us to modify and manage the list dynamically.
Following are some of the reasons why we may need to remove a node from the linked list
Data Management: When the data in a linked list changes, we may need to remove some nodes that are no longer relevant or inappropriate at the present time.
Memory Optimization: Linked List can be used to manage dynamically allocated memory. When a node is no longer needed, it is possible to remove it to make memory available for repurposing it.
Update of list: Deleting a node can be part of a more complex operation that is helpful for changing or updating the structure of the list.
For example, we can remove nodes to integrate two linked lists, or remove nodes to ensure no repeated values.
Maintaining Data Integrity: While working with data structures, it is important to maintain data integrity. Data corruption is avoided by keeping the linked list structured from deletion.
Tail Management: Linked lists can have a tail pointer. Removing from the end allows us to safely remove the last element .
User Interference: Nodes may need to be deleted in some contexts, such as deleting items from a user's shopping cart or deleting messages from an inbox.
Ways to delete a node from linked list
There are three ways to delete a node from linked list
- delete from the Beginning
- delete from the Middle
- delete from the End.
Delete from the Beginning
To delete the linked list from the beginning, follow these steps
- Check if the linked list is empty. If the head pointer is nullptr, there is nothing to delete, so return.
- If the linked list is not empty, delete the first node by updating the head pointer, which will point to the second node.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Method to append data at the end of the linked list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node lastNode = head;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = newNode;
}
// Method to delete a node from the beginning of the linked list
void deleteFromBeginning() {
// Check if the linked list is empty
if (head == null) {
System.out.println("Linked list is empty. Nothing to delete.");
return;
}
// Update the head pointer to the second node
head = head.next;
}
// Method to print the elements of the linked list
void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
System.out.println("Original Linked List:");
linkedList.printList();
linkedList.deleteFromBeginning();
System.out.println("\nLinked List after deleting from the beginning:");
linkedList.printList();
}
}
Output
Delete from the Middle
To delete the linked list from Middle, follow these steps
- First, find the middle node which you want to delete.
- Start from the head node and traverse the linked list.
- After traversing, compare the data of each node to delete the target node, which is from the Middle in this case.
- While traversing the linked list, keep track of the previous node.
- Once the node we want to detect updates, the previous node's next pointer is to skip the node to be delete
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Method to append data at the end of the linked list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node lastNode = head;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = newNode;
}
// Method to delete a node from the middle of the linked list
void deleteFromMiddle(int key) {
Node current = head;
Node prev = null;
// Find the node to be deleted and its previous node
while (current != null && current.data != key) {
prev = current;
current = current.next;
}
// If the node is not found
if (current == null) {
System.out.println("Node with data " + key + " not found in the linked list.");
return;
}
// If the node to be deleted is the head node
if (current == head) {
head = current.next;
} else {
prev.next = current.next;
}
// Free the memory of the deleted node (Java automatically handles memory deallocation)
}
// Method to print the elements of the linked list
void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
System.out.println("Original Linked List:");
linkedList.printList();
linkedList.deleteFromMiddle(2);
System.out.println("\nLinked List after deleting node with data 2:");
linkedList.printList();
}
}
Output
Delete from the End
To delete the linked list from End, follow these steps
- First, check if the linked list is empty. If the head pointer is nullptr, the list is empty and has nothing to delete and return from the function.
- If it is not nullptr, find the second last node.
- To reach the second to last node traverse the link list until you find it.
- Once you have found the second-to-last node, update its next pointer to null.
- It will delete the last node from the linked list.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Method to append data at the end of the linked list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node lastNode = head;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = newNode;
}
// Method to delete a node from the end of the linked list
void deleteFromEnd() {
// Check if the linked list is empty
if (head == null) {
System.out.println("Linked list is empty. Nothing to delete.");
return;
}
// If there is only one node, delete it
if (head.next == null) {
head = null;
return;
}
// Traverse to the second-to-last node
Node secondLast = head;
while (secondLast.next.next != null) {
secondLast = secondLast.next;
}
// Set the next pointer of the second-to-last node to null
secondLast.next = null;
}
// Method to print the elements of the linked list
void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
System.out.println("Original Linked List:");
linkedList.printList();
linkedList.deleteFromEnd();
System.out.println("\nLinked List after deleting from the end:");
linkedList.printList();
}
}
Output
Example Codes to delete a node with data 2
Python Code
# Node class to create individual nodes
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Linked list class to manage the operations
class LinkedList:
def __init__(self):
self.head = None
# Method to append data at the end of the linked list
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
# Method to delete a node from the linked list
def delete_node(self, key):
current_node = self.head
previous_node = None
# Find the node to be deleted and its previous node
while current_node and current_node.data != key:
previous_node = current_node
current_node = current_node.next
# If the node is not found
if not current_node:
print("Node with data {} not found in the linked list.".format(key))
return
# If the node to be deleted is the head node
if current_node == self.head:
self.head = current_node.next
else:
previous_node.next = current_node.next
# Free the memory of the node to be deleted
del current_node
# Method to print the elements of the linked list
def print_list(self):
current_node = self.head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("None")
# Example usage:
if __name__ == "__main__":
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print("Original Linked List:")
linked_list.print_list()
linked_list.delete_node(2)
print("\nLinked List after deleting node with data 2:")
linked_list.print_list()
Output
Java Code
// Node class to create individual nodes
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Linked list class to manage the operations
class LinkedList {
Node head;
// Method to append data at the end of the linked list
void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node lastNode = head;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = newNode;
}
// Method to delete a node from the linked list
void deleteNode(int key) {
Node currentNode = head;
Node prevNode = null;
// Find the node to be deleted and its previous node
while (currentNode != null && currentNode.data != key) {
prevNode = currentNode;
currentNode = currentNode.next;
}
// If the node is not found
if (currentNode == null) {
System.out.println("Node with data " + key + " not found in the linked list.");
return;
}
// If the node to be deleted is the head node
if (currentNode == head) {
head = currentNode.next;
} else {
prevNode.next = currentNode.next;
}
}
// Method to print the elements of the linked list
void printList() {
Node currentNode = head;
while (currentNode != null) {
System.out.print(currentNode.data + " -> ");
currentNode = currentNode.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
System.out.println("Original Linked List:");
linkedList.printList();
linkedList.deleteNode(2);
System.out.println("\nLinked List after deleting node with data 2:");
linkedList.printList();
}
}
Output
C++ Code
#include <iostream>
// Node class to create individual nodes
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// LinkedList class to manage the operations
class LinkedList {
public:
Node* head;
LinkedList() {
head = nullptr;
}
// Method to append data at the end of the linked list
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* lastNode = head;
while (lastNode->next != nullptr) {
lastNode = lastNode->next;
}
lastNode->next = newNode;
}
// Method to delete a node from the linked list
void deleteNode(int key) {
Node* current = head;
Node* prev = nullptr;
// Find the node to be deleted and its previous node
while (current != nullptr && current->data != key) {
prev = current;
current = current->next;
}
// If the node is not found
if (current == nullptr) {
std::cout << "Node with data " << key << " not found in the linked list." << std::endl;
return;
}
// If the node to be deleted is the head node
if (current == head) {
head = current->next;
} else {
prev->next = current->next;
}
// Free the memory of the deleted node
delete current;
}
// Method to print the elements of the linked list
void printList() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
LinkedList linkedList;
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
std::cout << "Original Linked List:" << std::endl;
linkedList.printList();
linkedList.deleteNode(2);
std::cout << "\nLinked List after deleting node with data 2:" << std::endl;
linkedList.printList();
return 0;
}
Output
Time Complexity
The time taken to remove a node from the linked list is O(n), where n is the number of nodes present in the linked list. In the worst case, we may need to traverse the linked list to find the node to delete.
Space Complexity
The Space Complexity is O(1) because we use the current node, previous node, and temporary variables during the deletion process.
Note: - continually update the pointers in the correct order when deleting nodes so as not to lose track of any nodes and create a dangling pointer. Also, please consider exceptional trivial cases like an empty list or a list with only one node, and handle them appropriately.
Conclusion
In conclusion, we have seen why do we need to delete a node from the linked list, and three ways to delete a node from linked list , used technique like traversal deleting a node from a linked list is a fundamental data management operation essential in data management and memory optimization. By carefully adjusting pointers and considering different conditions, programmers can maintain the integrity of the linked list while adapting it to ever-changing data requirements.