双向链表删除特定值触发访问违规错误，寻求排查解决

问题分析 #

你的代码触发Access Violation错误，核心原因有以下几点：

• 插入函数未初始化prev指针：inatst函数中创建新节点时，只设置了data和next，但prev指针未赋值，导致所有节点的prev都是野指针。当访问temp->prev->next时，实际是在访问非法内存地址。
• 删除函数未处理边界情况：没有判断要删除的节点是头节点、尾节点，或者节点的prev/next为空的情况，直接访问temp->prev->next会在temp是头节点时（temp->prev为NULL）触发错误。
• 重复调用搜索函数：delspval中两次调用search，不仅降低效率，还可能在多线程场景下出现不一致问题。

修正后的完整代码 #

#include<iostream>
using namespace std;

class dll{
    struct node{
        int data;
        node *next,*prev;
    };
    node *head;
public:
    dll(){
        head=NULL;
    }

    // 修正插入函数：初始化prev指针，维护双向链表结构
    void inatst(int val){
        node *temp=new node;
        temp->data=val;
        temp->next=head;
        temp->prev=NULL; // 新节点作为头节点，前驱为空
        if(head != NULL){
            head->prev=temp; // 原头节点的前驱指向新节点
        }
        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 = search(val);
        if(temp == NULL){
            return false;
        }

        // 情况1：删除的是头节点
        if(temp->prev == NULL){
            head = temp->next;
            if(head != NULL){
                head->prev = NULL;
            }
        }
        // 情况2：删除的是中间节点或尾节点
        else{
            temp->prev->next = temp->next;
            // 若不是尾节点，更新后继节点的前驱
            if(temp->next != NULL){
                temp->next->prev = temp->prev;
            }
        }

        delete temp;
        cout<<"specific value "<<val<<" deleted"<<endl;
        return true;
    }

    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;
        }
    }
};

// 标准main函数格式
int 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);
    l1.display(); // 新增显示，验证删除结果
    system("pause");
    return 0;
}

关键修正点说明 #

• 插入函数：新增temp->prev=NULL初始化新节点的前驱指针，同时如果原链表不为空，将原头节点的prev指向新节点，保证双向链表的结构完整性。
• 删除函数：
  • 先判断是否为头节点，若是则更新head，并处理新头节点的prev。
  • 对于中间节点，同时更新前驱节点的next和后继节点的prev；若是尾节点（temp->next为NULL），则只更新前驱节点的next即可。
  • 只调用一次search函数，避免重复遍历链表。
• main函数：修正为标准的int main()并返回0，符合C++规范。

内容的提问来源于stack exchange，提问作者hadi khan