# 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.