Delete a node with given key

In the given linked list, delete a node with given key. (delete the first occurrence)

Example

Time complexity : O (n)

Algorithm

a. Find the node to be deleted by traversing in the array, store previous of the node.

b. If node to be deleted is head then change head pointer to next of head and delete head node.

c. Change next of previous node to next of node to be deleted.

d. Free memory of the node to be deleted. free(node).

Algorithm working

 

C++ Program

#include <bits/stdc++.h>

using namespace std;

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

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

void DeleteNode(struct LLNode **head_ref, int key)
{
    // Store head node
    struct LLNode* temp = *head_ref, *prev;
 
    //If head is the node to be deleted
    if (temp != NULL && temp->data == key)
    {
        // Changed head
        *head_ref = temp->next;
        //delete
        free(temp);               
        return;
    }
 
    //seacrch for node to be deleted
    while (temp != NULL && temp->data != key)
    {
        prev = temp;
        temp = temp->next;
    }
    // If key was not present in linked list
    if (temp == NULL)
    {
        cout<<"Invalid input!"<<endl;
        return;
    }
    // Unlink the node from linked list
    prev->next = temp->next;
    // Free memory
    free(temp);  
}
 
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"Input linked list is: ";
    display(&head);
    int k;
    cout<<"Enter key to be deleted:  ";
    cin>>k;

    DeleteNode(&head, k);
    
    cout<<"list after deltetion of "<<k<<" is: ";
    display(&head);

    return 0;
}
Try It

 


Next > < Prev
Scroll to Top