Deletion of node from linked list

Question

I am trying to code for deletion of a node with k as data of linked list. The below program is running fine, but it is not giving desired output if we have to delete the head node. For example, if the linked list is 98->6->1 and I have to delete 98, then the output which the program is showing is 0->6->1. Except for the deletion of the head node, it is working correctly for all other cases. Below is the c++ code for the same.

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


class Node
{
    public :
           int data;
           Node* next;
   };

Node * insert(Node* head, int data) {
  Node* new_node= new Node();
  new_node->data = data;
  new_node->next = head;
  head = new_node;
  return head;
 }

  void deleteNode(Node *head, int key)
  {
     Node *temp = head;
     Node *prev = NULL;
     if(temp!=NULL && temp->data==key){
     head = temp->next;
     delete temp;
   }
    else{
        while(temp!=NULL && temp->data!=key){
          prev = temp;
          temp = temp->next;
    }
    if(temp == NULL){
        return;
    }
    prev->next = temp->next;
    delete temp;
   }
   }


    void display(Node * head) {

    while(head != NULL)
   {
    cout<<head->data<<" ";
    head = head->next;
   }
  }

   int main() {
   Node * head = NULL;

   head = insert(head, 1);

   head=insert(head,6);
   head=insert(head,98);
   deleteNode(head,98);
   display(head);

   return 0;
  }

See [how to delete head in a linked list in c?](https://stackoverflow.com/q/59922001/3422102) (PS, since this is C++, you can pass head as a reference and make that work) — David C. Rankin, Jul 19 '21 at 15:32
More handy reading: [How do I properly delete nodes of linked list in C++](https://stackoverflow.com/questions/22121257/how-do-i-properly-delete-nodes-of-linked-list-in-c) Pay special attention to the pointer-to-pointer trick in the community addition. — user4581301, Jul 19 '21 at 15:34
Whatever resource you're using to learn C++ I would say it's not very good. You don't use the power of C++ by using more classes and member functions. You also have a couple of bad habits, one which is considered really bad ([that header file inclusion](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)). — Some programmer dude, Jul 19 '21 at 15:34
I thing that you are creating a circular list with this Node * insert(Node* head, int data) { Node* new_node= new Node(); new_node->data = data; new_node->next = head; head = new_node; return head; } — Nederxus, Jul 19 '21 at 15:38
By using `#include `, you have included every single header, instead of just having `#include `. — PaulMcKenzie, Jul 19 '21 at 16:00
@Someprogrammerdude Thank you for pointing my mistake. Apart from header file inclusion kindly mention my mistake if any, that would be really helpful.TIA — PETULLA MISHRA, Jul 19 '21 at 17:33
By the way, please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Wyck, Jul 19 '21 at 17:53

score 3 · Answer 1 · answered Jul 19 '21 at 15:33

In deleteNode(), you are passing in the head node by value, so any modification made to it is not reflected back to the caller. You need to either return the new head, like you do with Insert(), or else you need to pass in the head by reference:

void deleteNode(Node* &head, int key)

score 0 · Accepted Answer · answered Jul 19 '21 at 17:40

The mistake in your code is that the head you are passing to deleteNode function is by value so the changes made to the head function is not displayed. The head in your function is not the same head in your main function it is just the copy of that head, so to apply the same change being applied to the head in deletenode function to the original head, you have to pass the address of the head(or pass by reference).

Editing in your code- I have applied changes in deleteNode function first five lines and the third last line when you are passing value by reference deleteNode(&head,98);

Edited code-

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


class Node
{
    public :
           int data;
           Node* next;
   };

Node * insert(Node* head, int data) {
  Node* new_node= new Node();
  new_node->data = data;
  new_node->next = head;
  head = new_node;
  return head;
 }

  void deleteNode(Node **head, int key)
  {
     Node *temp = *head;
     Node *prev = NULL;
     if(temp!=NULL && temp->data==key){
     *head = temp->next;
     temp->next = NULL;
     delete temp;
   }
    else{
        while(temp!=NULL && temp->data!=key){
          prev = temp;
          temp = temp->next;
    }
    if(temp == NULL){
        return;
    }
    prev->next = temp->next;
   // temp->next = NULL;
    delete temp;
   }
   }


    void display(Node * head) {

    while(head != NULL)
   {
    cout<<head->data<<" ";
    head = head->next;
   }
  }

   int main() {
   Node * head = NULL;

   head = insert(head, 1);

   head=insert(head,6);
   head=insert(head,98);
   deleteNode(&head,98);
   display(head);

   return 0;
  }

Now if you run the above code the output you will get after deleting node of value 98 will be 6->1. Hope you will find it helpful.

[Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Jul 20 '21 at 15:49
And you're not really passing by reference in the `deleteNode` function, you're passing a pointer which is the old C-way to *emulate* pass by reference. C++ have native references. You also don't need to repeat unmodified code. And just browsing the code it's hard to see when and where you have modified it. — Some programmer dude, Jul 20 '21 at 15:51
there i want to say you can also do it by call by reference. I am a new to this site i will take care about it next time — Abhinav 1036, Jul 20 '21 at 16:40

Deletion of node from linked list

2 Answers2