# deletion of single linked list

Given the head pointer pointing to the Head of a singly linked list and a node to be deleted from the list. Delete the given node from the Linked List.

Like inserting a node in a linked list, there can be many situations when it comes to deleting a Node from a Linked List. Some of the most frequent such situations are:

*Given the data value of a Node, delete the first occurrence of that data in the list.

*Given the position of a node, delete the node present at the given position in the list.

*Given a pointer to the node to be deleted, delete the node.

Let us look at each one of these situations and their solutions with complete explanations:

1)**Deleting the first occurrence of a given Data Value**: Deleting a node by its value can be done by traversing the list till the node just before the node with the value as the given key. Once the node just before the node to be deleted is found. Update its next pointer to point to the next of its next node.

That is:

*Find previous node of the node to be deleted.

*Change the next of previous node.

*Free memory for the node to be deleted.

*Below is the implementation of this approach:*

*c++:*

void deleteNode(struct Node **head_ref, int key) { // Store head node struct Node* temp = *head_ref, *prev; // If head node itself holds the key to be deleted if (temp != NULL && temp->data == key) { *head_ref = temp->next; // Changed head free(temp); // free old head return; } // Search for the key to be deleted, keep track of the // previous node as we need to change 'prev->next' 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(temp); // Free memory }

```
void deleteNode(int key)
{
// Store head node
Node temp = head, prev = null;
// If head node itself holds the key to be deleted
if (temp != null && temp.data == key)
{
head = temp.next; // Changed head
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change temp.next
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;
}
```

**time complexity**of this operation in worst case is O(N) where N is the number of nodes in the Linked List.

**2)Deleting a node at a given position:**If the node to be deleted is the root node, we can simply delete it by updating the head pointer to point to the next of the root node. To delete a node present somewhere in between, we must have the pointer to the node previous to the node to be deleted. So if the position is not zero, run a loop position-1 times and get the pointer to the previous node and follow the method discussed in the first situation above to delete the node.

```
void deleteNode(struct Node **head_ref, int position)
{
// If linked list is empty
if (*head_ref == NULL)
return;
// Store head node
struct Node* temp = *head_ref;
// If head needs to be removed
if (position == 0)
{
*head_ref = temp->next; // Change head
free(temp); // free old head
return;
}
// Find previous node of the node to be deleted
for (int i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;
// If position is more than number of ndoes
if (temp == NULL || temp->next == NULL)
return;
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
struct Node *next = temp->next->next;
// Unlink the node from linked list
free(temp->next); // Free memory
temp->next = next; // Unlink the deleted node from list
}
```

void deleteNode(int position) { // If linked list is empty if (head == null) return; // Store head node Node temp = head; // If head needs to be removed if (position == 0) { head = temp.next; // Change head return; } // Find previous node of the node to be deleted for (int i=0; temp!=null && i<position-1; i++) temp = temp.next; // If position is more than number of ndoes if (temp == null || temp.next == null) return; // Node temp->next is the node to be deleted // Store pointer to the next of node to be deleted Node next = temp.next.next; temp.next = next; // Unlink the deleted node from list }

**time complexity**of this operation in worst case is O(N) where N is the number of nodes in the Linked List.

**Deleting a node whose pointer is given:**In this case a pointer is given which is pointing to a particular node in the linked list and task is to delete that particular node.

// Find next node using next pointer

struct Node *temp = node_ptr->next;

// Copy data of next node to this node

node_ptr->data = temp->data;

// Unlink next node

node_ptr->next = temp->next;

// Delete next node

free(temp);