Linked List Deleting Node

Last Updated on March 10, 2022 by Ria Pathak

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list and a value X. We have to delete the first occurrence of a node with the data X from the linked list.

Note: Although there can be multiples nodes with value X in the linked list, but we have to only delete the first node with value X from the linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Suppose the given linked list is: 1 → 1 → 0 → 2 → 2 and the value to be deleted is 0.

Now, according to the problem statement, we have to delete the first occurrence of the node containing the value 0.
So, the linked list after deleting 0 will be 1 → 1 → 2 → 2.

Suppose the list is:.

and the value to be deleted is 2

Now, in this case, we can see that there are two nodes with data 2 in the linked list. According to the problem statement, we only need to delete the first occurrence of the node with value 2 from the linked list.
Our output linked list after deletion will be

Some more examples

Sample Input 1: 1 → 2 → 3 →4, Value to be deleted (X) = 2
Sample Output 1: 1 → 3 → 4

Sample Input 2: 1 → 1 → 2 →2, Value to be deleted (X) = 1
Sample Output 2: 1 → 2 → 2

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how can you approach this problem.

If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach (Iterative)

Let us first think about what we should do to delete a node from a linked list.

Let us take an example. 1 → 2 → 3 → 4. Now, to delete 2 from the list, what should we do?

What if we make 1 point to 3 instead of 2 ? Yes. That’s the essence.

To delete a node P from a linked list, we have to traverse to its previous node and make it point to the P‘s next node.

Let’s see the algorithm.

Algorithm

Create a pointer temp and make it point to the head of the list and also create a pointer prev and point it to NULL.
If the head contains the value X, make head = temp → next, and then delete temp.
Else, we will traverse the list with temp and store temp in pointer prev before incrementing it.
- The loop will run till temp → data! = X.
- As soon as temp → data = X, the loop will break.
As we were storing temp in prev before incrementing it, so prev now points to the previous node of the node which we want to delete.
Now, we will simply do prev -> next = temp -> next, as discussed in the approach.
Finally, delete temp.
In this way, the first occurrence of a node with value X will be deleted. If the list is traversed and the value is not found, we will simply return.

Dry Run

Code Implementation

#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 key, deletes the first occurrence of key in
   linked list */
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
}
 
// 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 code
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    push(&head, 7);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);
 
    puts("Created Linked List: ");
    printList(head);
    deleteNode(&head, 1);
    puts("\nLinked List after Deletion of 1: ");
    printList(head);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/* Node structure of linked list node */
class Node{
public:
    int data;
    Node* next;
};

/* Using this function we will insert a new node at head of linked 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;
}

/* Using this function we will be deleting the first occurance of a node with value = key from the linked list */
void deleteValue(Node** head_ref, int key)
{
    
    Node* temp = *head_ref;
    Node* prev = NULL;

    if (temp != NULL && temp->data == key)
    {
        *head_ref = temp->next; 
        delete temp;         
        return;
    }

    else
    {
    while (temp != NULL && temp->data != key)
    {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL)
        return;

    prev->next = temp->next;

    delete temp;
    }
}

/* Using this function we will be printing the content of linked list */
void print(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}

int main()
{
    Node* head = NULL;
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    puts("Created Linked List: ");
    print(head);
    
    int X = 2;
    deleteValue(&head, X);
    cout<<"\nLinked List after Deletion of first occurance of node with value "<<X<<": "<<endl;
    
    print(head);
    
    return 0;
}

public class LinkedList {
    Node head; 

    /* Node structure of a linked list node */
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    
    /* Using this function we will be deleting the first occurance of a node with value = key from the linked list */
    void deleteValue(int key)
    {

        Node temp = head, prev = null;

        if (temp != null && temp.data == key) {
            head = temp.next;
            return;
        }

        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }

        if (temp == null)
            return;

        prev.next = temp.next;
    }
    
    /* Using this function we will insert a new node at head of linked list */
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }

    /* Using this function we will be printing the content of linked list */
    public void printList()
    {
        Node tnode = head;
        while (tnode != null) {
            System.out.print(tnode.data + " ");
            tnode = tnode.next;
        }
    }


    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();

        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);

        System.out.println("\nCreated Linked list is:");
        llist.printList();
        
        int X = 2;
        llist.deleteValue(X);

        System.out.println(
            "\nLinked List after Deletion of first occurance of node with value "+X+": ");
        llist.printList();
    }
}

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:

	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def deleteNode(self, key):
		
		temp = self.head

		if (temp is not None):
			if (temp.data == key):
				self.head = temp.next
				temp = None
				return

		while(temp is not None):
			if temp.data == key:
				break
			prev = temp
			temp = temp.next

		if(temp == None):
			return

		prev.next = temp.next

		temp = None


	def printList(self):
		temp = self.head
		while(temp):
			print (temp.data, end = " ")
			temp = temp.next


llist = LinkedList()
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print ("Created Linked List: ")
llist.printList()
llist.deleteNode(2)
print ("\nLinked List after Deletion of 2:")
llist.printList()

Output

Created Linked List:
1 2 3 4
Linked List after Deletion of first occurance of node with value 2:
1 3 4

Time Complexity: O(n), as list traversal is needed.
Space Complexity: O(1), as only temporary variables are being created.

Approach (Recursive)

As we have already discussed what we have to do to delete a node from a linked list, now here we will modify it a lit bit while implementing.

If we think carefully, the current node is accessed by the previous node’s next, which is passed by reference. Thus, we can say that altering the current node can alter the previous node’s next.
So, we will traverse the linked list with the help of recursion, and when the head’s data is equal to the value of node to be deleted(X), we will store the head in temp, do head = head → next and delete temp and then return as our task is completed.
By doing the above steps, the node will get deleted and as discussed above, when we will do head = head → next, it will make the previous → next point to head → next.

Let’s see the algorithm.

Algorithm

Base case – If the head is NULL, i.e., the node with value X is not present in the list, so we will print Element not present in the list and then we will return.
If the head → data = X, then store the head in a pointer temp, do head = head → next and delete temp and then return as our task is completed. This will change the required links too as discussed above.
Keep recurring with deleteValue( head – > next, X).

Dry Run

Code Implementation

#include 
#include 
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* Recursive Function to delete the entire linked list */
void deleteList(struct Node* head)
{
    if (head == NULL)
        return;
    deleteList(head->next);
    free(head);
}
 
/* Given a reference (pointer to pointer) to
   the head of a list and an int, push a new
   node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
/* Driver program to test count function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    /* Use push() to construct below list
    1->12->1->4->1 */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);
    printf("\n Deleting linked list");
    deleteList(head);
   
      // Since head now points to illgal address, we should set head = NULL:
      head = NULL;
    printf("\nLinked list deleted");
    return 0;
}

#include 
using namespace std;

struct node {
    int info;
    node* link = NULL;
    node() {}
    node(int a)
        : info(a)
    {
    }
};

/* Using this function we will be deleting the first occurance of the given valued node from the linked list */
void deleteValue(node*& head, int value)
{

    if (head == NULL) {
        cout << "Element not present in the list\n";
        return;
    }

    if (head->info == value) {
        node* temp = head;
        head = head->link; 
        delete (temp);
        return;
    }
    deleteValue(head->link, value);
}

/* Using this function we will push the node in the list */
void push(node*& head, int data)
{
    node* newNode = new node(data);
    newNode->link = head;
    head = newNode;
}

/* Using this function we will print the content of linked list */
void print(node* head)
{

    if (head == NULL and cout << endl)
        return;
    cout << head->info << ' ';
    print(head->link);
}

int main()
{
    node* head = NULL;
    push(head, 4);
    push(head, 3);
    push(head, 2);
    push(head, 1);
    
    puts("Created Linked List: ");
    print(head);

    int X = 2;
    deleteValue(head, X);

    cout<<"\nLinked List after Deletion of first occurance of node with value "<

class Node
{
    int info;
    Node link =null;
    Node(int info)
    {
        this.info=info;
    }
}

class DeletingNode 
{
    void push(Node head,int data)
    {
        Node newNode = new Node(data);
        newNode.link = head;
        head=newNode;
    }
    void print(Node head)
    {
        Node temp=head;
        while(temp!=null){
            System.out.print(temp.info+" ");
            temp=temp.link;
        }
    }

    void deleteValue(Node head,int value)
    {
        if(head==null || head.link==null)
        {
            System.out.println("Element not present in the list");
            return;
        }
        if(head.link.info==value)
        {
            Node x =head;
            x.link=head.link.link;
            return;
        }
        deleteValue(head.link, value);
    }
    public static void main(String[] args) 
    {
        Node head=null;
        DeletingNode ll=new DeletingNode();
        ll.push(head, 4);
        ll.push(head, 3);
        ll.push(head, 2);
        ll.push(head, 1);

        System.out.println("Created linked list :");
        ll.print(head);

        int x=2;
        ll.deleteValue(head, x);

        Node temp=head;
        System.out.println("Linked list after deletion of first occurance of node with value "+x);
        ll.print(temp);
    }
}

class Node:

    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:

    def __init__(self):
        self.head = None

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node


    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data, end = " ")
            temp = temp.next

def deleteNode(head, key):
        

        if head == None:
        
            print("Element not present in the list")
            return

        if head.data == key:
        
            temp = head
            head = head.next
            del temp
            return 

        deleteNode(head.next, key)




llist = LinkedList()
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print ("Created Linked List: ")
llist.printList()
deleteNode(llist.head, 2)
print ("\nLinked List after Deletion of 2:")
llist.printList()

Output

Created Linked List:
1 2 3 4

Linked List after Deletion of first occurance of node with value 2:
1 3 4

Time Complexity: O(n), as list traversal is needed.
[forminator_quiz id=”5290″]

So, in this article, we have tried our best to explain how to delete a node from a linked list. This is an important question when it comes to coding interviews.
If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Introduction

Problem Statement

Problem Statement Understanding

Some more examples

Approach (Iterative)

Algorithm

Dry Run

Code Implementation

Output

Approach (Recursive)

Algorithm

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply

Integrated Services Digital Network (ISDN)

VLAN ACL (VACL) in Computer Networks

Inter-VLAN Routing Using a Layer 3 Switch

Access and Trunk Ports in Computer Networks

Role-Based Access Control (RBAC) in Computer Networks

Display Processor in Computer Graphics

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Introduction

Problem Statement

Problem Statement Understanding

Some more examples

Approach (Iterative)

Algorithm

Dry Run

Code Implementation

Output

Approach (Recursive)

Algorithm

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply