Write an algorithm to delete a node with given item in linked list

Linked List | Set 3 (Deleting a node)

We have discussed Linked List Introduction and Linked List Insertion in previous posts on a singly linked list.
Let us formulate the problem statement to understand the deletion process. Given a ‘key’, delete the first occurrence of this key in the linked list.

Table of Contents Show

Linked List | Set 3 (Deleting a node)
Delete a Linked List node at a given position
Deleting a node in linked list
Deletion in singly linked list at beginning
Linked List Operations: Traverse, Insert and Delete
Things to Remember about Linked List
7.10: Linked List Node Delete

Iterative Method:
To delete a node from the linked list, we need to do the following steps.
1) Find the previous node of the node to be deleted.
2) Change the next of the previous node.
3) Free memory for the node to be deleted.

Delete a Linked List node at a given position

Given a singly linked list and a position, delete a linked list node at the given position.

Example:

Input: position = 1, Linked List = 8->2->3->1->7 Output: Linked List = 8->3->1->7 Input: position = 0, Linked List = 8->2->3->1->7 Output: Linked List = 2->3->1->7

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

If the node to be deleted is the root, simply delete it. To delete a middle node, we must have a pointer to the node previous to the node to be deleted. So if positions are not zero, we run a loop position-1 times and get a pointer to the previous node.

Below is the implementation of the above idea.

C++

// A complete working C++ program to delete
// a node in a linked list at a given position
#include <iostream>

using namespace std;
// A linked list node

class Node {

public:

int data;

Node* next;
};
// Given a reference (pointer to pointer) to
// the head of a list and an int inserts a
// new node on the front of the list.

void push(Node** head_ref, int new_data)
{

Node* new_node = new Node();

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;
}
// Given a reference (pointer to pointer) to
// the head of a list and a position, deletes
// the node at the given position

void deleteNode(Node** head_ref, int position)
{

// If linked list is empty

if (*head_ref == NULL)

return;

// Store head node

Node* temp = *head_ref;

// If head needs to be removed

if (position == 0) {

// Change head

*head_ref = temp->next;

// Free old head

free(temp);

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 nodes

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;

// Unlink the node from linked list

free(temp->next); // Free memory

// Unlink the deleted node from list

temp->next = next;
}
// This function prints contents of linked
// list starting from the given node

void printList(Node* node)
{

while (node != NULL) {

cout << node->data << " ";

node = node->next;

}
}
// Driver code

int main()
{

// Start with the empty list

Node* head = NULL;

push(&head, 7);

push(&head, 1);

push(&head, 3);

push(&head, 2);

push(&head, 8);

cout << "Created Linked List: ";

printList(head);

deleteNode(&head, 4);

cout << "\nLinked List after Deletion at position 4: ";

printList(head);

return 0;
}
// This code is contributed by premsai2030

// A complete working C program to delete a node in a linked
// list at a given position
#include <stdio.h>
#include <stdlib.h>
// A linked list node

struct Node {

int data;

struct Node* next;
};
/* Given a reference (pointer to pointer) to the head of a

list and an int inserts a new node on the front of the

list. */

void push(struct Node** head_ref, int new_data)
{

struct Node* new_node

= (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;
}
/* Given a reference (pointer to pointer) to the head of a

list and a position, deletes the node at the given

position */

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 nodes

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
}
// This function prints contents of linked list starting
// from the given node

void printList(struct Node* node)
{

while (node != NULL) {

printf(" %d ", node->data);

node = node->next;

}
}
/* Driver program to test above functions*/

int main()
{

/* Start with the empty list */

struct Node* head = NULL;

push(&head, 7);

push(&head, 1);

push(&head, 3);

push(&head, 2);

push(&head, 8);

puts("Created Linked List: ");

printList(head);

deleteNode(&head, 4);

puts("\nLinked List after Deletion at position 4: ");

printList(head);

return 0;
}

Java

// A complete working Java program to delete a node in a
// linked list at a given position

class LinkedList {

Node head; // head of list

/* Linked list Node*/

class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

}

/* Inserts a new Node at front of the list. */

public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/* Given a reference (pointer to pointer) to the head of

a list

and a position, deletes the node at the given

position */

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 nodes

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

}

/* This function prints contents of linked list starting

from the given node */

public void printList()

{

Node tnode = head;

while (tnode != null) {

System.out.print(tnode.data + " ");

tnode = tnode.next;

}

}

/* Driver program to test above functions. Ideally this

function should be in a separate user class. It is

kept here to keep code compact */

public static void main(String[] args)

{

/* Start with the empty list */

LinkedList llist = new LinkedList();

llist.push(7);

llist.push(1);

llist.push(3);

llist.push(2);

llist.push(8);

System.out.println("\nCreated Linked list is: ");

llist.printList();

llist.deleteNode(4); // Delete node at position 4

System.out.println(

"\nLinked List after Deletion at position 4: ");

llist.printList();

}
}

Python3

# Python program to delete a node in a linked list
# at a given position
# Node class

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

# Constructor to initialize head

def __init__(self):

self.head = None

# Function to insert a new node at the beginning

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

# Given a reference to the head of a list

# and a position, delete the node at a given position

#This delete function code is contributed by Arabin Islam

def deleteNode(self, position):

if self.head is None:

return

if position == 0:

self.head = self.head.next

return self.head

index = 0

current = self.head

prev = self.head

temp = self.head

while current is not None:

if index == position:

temp = current.next

break

prev = current

current = current.next

index += 1

prev.next = temp

return prev

# Utility function to print the linked LinkedList

def printList(self):

temp = self.head

while(temp):

print (" %d " % (temp.data),end=" ")

temp = temp.next
# Driver program to test above function

llist = LinkedList()

llist.push(7)

llist.push(1)

llist.push(3)

llist.push(2)

llist.push(8)

print ("Created Linked List: ")
llist.printList()

llist.deleteNode(4)

print ("\nLinked List after Deletion at position 4: ")
llist.printList()
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// A complete working C# program to delete
// a node in a linked list at a given position

using System;

class GFG {

// Head of list

Node head;

// Linked list Node

public class Node {

public int data;

public Node next;

public Node(int d)

{

data = d;

next = null;

}

}

// Inserts a new Node at front of the list.

public void Push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

// Given a reference (pointer to pointer)

// to the head of a list and a position,

// deletes the node at the given position

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) {

// Change head

head = temp.next;

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 nodes

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;

// Unlink the deleted node from list

temp.next = next;

}

// This function prints contents of

// linked list starting from the

// given node

public void printList()

{

Node tnode = head;

while (tnode != null) {

Console.Write(tnode.data + " ");

tnode = tnode.next;

}

}

// Driver code

public static void Main(String[] args)

{

// Start with the empty list

GFG llist = new GFG();

llist.Push(7);

llist.Push(1);

llist.Push(3);

llist.Push(2);

llist.Push(8);

Console.WriteLine("\nCreated Linked list is: ");

llist.printList();

// Delete node at position 4

llist.deleteNode(4);

Console.WriteLine("\nLinked List after "

+ "Deletion at position 4: ");

llist.printList();

}
}
// This code is contributed by Rajput-Ji

Javascript

<script>
// A complete working javascript program to 
// delete a node in a linked list at a 
// given position
// head of list

var head;
/* Linked list Node */
class Node 
{

constructor(val)

{

this.data = val;

this.next = null;

}
}
/* Inserts a new Node at front of the list. */

function push(new_data)
{


/*

* 1 & 2: Allocate the Node & Put in the data

*/

var new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;
}
/*

* Given a reference (pointer to pointer) to the

* head of a list and a position,

* deletes the node at the given position

*/

function deleteNode(position)
{


// If linked list is empty

if (head == null)

return;


// Store head node

var temp = head;


// If head needs to be removed

if (position == 0)

{


// Change head

head = temp.next;

return;

}


// Find previous node of the node to be deleted

for(i = 0; temp != null && i < position - 1; i++)

temp = temp.next;


// If position is more than number of nodes

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

var next = temp.next.next;


// Unlink the deleted node from list

temp.next = next;
}
/*
* This function prints contents of linked 
* list starting from the given node
*/

function printList()
{

var tnode = head;

while (tnode != null)

{

document.write(tnode.data + " ");

tnode = tnode.next;

}
}
/*
* Driver program to test above functions.
* Ideally this function should be in a
* separate user class. It is kept here 
* to keep code compact
*/
/* Start with the empty list */
push(7);
push(1);
push(3);
push(2);
push(8);

document.write("Created Linked list is: <br/>");
printList();
// Delete node at position 4
deleteNode(4); 

document.write("<br/>Linked List after " +

"Deletion at position 4: <br/>");
printList();
// This code is contributed by todaysgaurav
</script>

Output:

Created Linked List: 8 2 3 1 7 Linked List after Deletion at position 4: 8 2 3 1

Thanks to Hemanth Kumar for suggesting initial solution. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Article Tags :

Linked List

Samsung

Practice Tags :

Samsung

Linked List

Read Full Article

Deleting a node in linked list

Delete a given node from the linked list.

Deletion in singly linked list at beginning

Deleting a node from the beginning of the list is the simplest operation of all. It just need a few adjustments in the node pointers. Since the first node of the list is to be deleted, therefore, we just need to make the head, point to the next of the head. This will be done by using the following statements.

Now, free the pointer ptr which was pointing to the head node of the list. This will be done by using the following statement.

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

Traversal - access each element of the linked list
Insertion - adds a new element to the linked list
Deletion - removes the existing elements
Search - find a node in the linked list
Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

struct node { int data; struct node *next; };