How to delete a specific value from a doubly linked list?-CodePudding

I was given a task with a DOUBLY linked list to delete a specific number from the list. My code is giving an Access Violation error. Even after multiple dry runs, I can't figure out what is wrong. The task basically is to create a search function which finds a specific number in the linked list, and a deletion function which deletes that specific link.

node* search(int val){
    node* cur=head;
    while(cur!=NULL){
        if(cur->data==val){
            cout<<"value found "<<val<<endl;
            return cur;
        }
        cur=cur->next;
    }
    cout<<"value not exist"<<endl;
    return NULL;
}

bool delspval(int val){
    node*temp=0;
    if(search(val)==NULL){
        return 0;
    }
    else{
        temp=search(val);
        temp->prev->next=temp->next;
        delete temp;
        temp=0;
        cout<<"specific value "<<val<<" deleted"<<endl;
        return 1;
    }
}

In the above given code, the line temp->prev->next=temp->next; is giving the error. I'm pretty much a beginner at linked lists, so any help would be appreciated.

minimal working code:

#include<iostream>
using namespace std;
class dll{
    struct node{
        int data;
        node *next,*prev;
    };
    node *head;
public:
    dll(){
        head=NULL;
    }
    void inatst(int val){
        node *temp=new node;
        temp->data=val;
        temp->next=head;
        head=temp;
    }
    node* search(int val){
        node* cur=head;
        while(cur!=NULL){
            if(cur->data==val){
                cout<<"value found "<<val<<endl;
                return cur;
            }
            cur=cur->next;
        }
        cout<<"value not exist"<<endl;
                    return NULL;
    }
    bool delspval(int val){
        node*temp=0;
        if(search(val)==NULL){
            return 0;
        }
        else{
            temp=search(val);
            temp->prev->next=temp->next;
            delete temp;
            temp=0;
            cout<<"specific value "<<val<<" deleted"<<endl;
            return 1;
                }
            }
    void display(){
        node*cur=head;
        while(cur!=NULL){
            cout<<cur->data<<" ";
            cur=cur->next;
        }
        cout<<endl;
    }
    ~dll(){
        while(head!=NULL){
            node*cur=head;
            head=cur->next;
            delete cur;
            cur=head;
        }
    }
};
void main(){
    dll l1;
    l1.inatst(1);
    l1.inatst(2);
    l1.inatst(3);
    l1.inatst(4);
    l1.inatst(5);
    l1.inatst(6);
    l1.display();
    l1.delspval(3);
    system("pause");
}

CodePudding user response：

For starters, the search() function is being called twice within the delspval() function:

if(search(val)==NULL){

and

temp=search(val);

that makes the delspval() function less efficient.

This statement:

temp->next->prev=temp->next;

does not make sense.

The delspval() function can be defined in the following way. I suppose that the class contains only one pointer to the head node. If the class contains also a pointer to the tail node, then the function below must be modified.

bool delspval( int val )
{
    node *temp = search( val );
    bool success = temp != nullptr;

    if ( success )
    {
        if ( temp->next != nullptr )
        {
            temp->next->prev = temp->prev;
        }
        // If the class has a pointer to the tail node
        //   then uncomment the else part  
        /*
        else
        {
            tail = temp->prev;
        }
        */

        if ( temp->prev != nullptr )
        {
            temp->prev->next = temp->next;
        }
        else
        {
            head = temp->next;
        }

        delete temp;
    }

    return success;
}

CodePudding user response：

You should absolutely not call search twice. You basically double the runtime.

But the solution if the value was found: If tmp->next is not null then it points to tmp, but it now needs to the item before tmp. And if tmp->prev is not then it points to tmp, but it needs to point to the item after tmp.

And finally, if tmp = head then head must be changed to the item after tmp.

Tmp = search()
If tmp == null then return
Prev = tmp->prev
Next = tmp->next
If prev ≠null then prev->next = next
If next ≠ null then next->prev = prev
If head = tmp then head = next. 
Delete tmp.