C++双向链表类问题：反向打印丢元素及删除函数实现指导

问题描述 #

我在C++中实现了基于Node类的双向链表，但当前链表反向打印（从大到小）时缺失部分元素，正向打印结果正常。同时需要一份与insert函数逻辑类似的remove函数实现指导。

现有代码 #

Node.h #

class Node {
public:
    explicit Node(int data = 0, Node *nextPtr = nullptr, Node *beforePtr = nullptr);
    int getData() const;
    void setData(int data);
    Node *getNextPtr() const;
    void setNextPtr(Node *nextPtr);
    Node *getBeforePtr() const;
    void setBeforePtr(Node *beforePtr);
    void print() const;

private:
    int data;
    Node *nextPtr;
    Node *beforePtr;
};

Node.cpp #

#include <iostream>
using namespace std;

Node::Node(int data, Node *nextPtr, Node *beforePtr) : data(data), nextPtr(nextPtr), beforePtr(beforePtr) {}

int Node::getData() const {
    return data;
}

void Node::setData(int data) {
    Node::data = data;
}

Node *Node::getNextPtr() const {
    return nextPtr;
}

void Node::setNextPtr(Node *nextPtr) {
    Node::nextPtr = nextPtr;
}

Node *Node::getBeforePtr() const {
    return beforePtr;
}

void Node::setBeforePtr(Node *beforePtr) {
    Node::beforePtr = beforePtr;
}

void Node::print() const {
    cout << getData() << endl;
}

MyList.h #

class MyList {
public:
    MyList(Node *currentPrt = nullptr);
    void insert(int value);
    void print() const;
    // 新增remove函数声明
    void remove(int value);

private:
    Node *currentPrt;
};

MyList.cpp（原代码） #

#include <iostream>
#include "Node.h"
#include "MyList.h"
using namespace std;

MyList::MyList(Node *currentPrt) {}

void MyList::insert(int value) {
    if(currentPrt == nullptr){
        currentPrt = new Node;
        currentPrt->setData(value);
        currentPrt->setNextPtr(nullptr);
        currentPrt->setBeforePtr(nullptr);
    }
    else{
        if(value > currentPrt->getData()){
            while (currentPrt->getNextPtr() != nullptr && currentPrt->getNextPtr()->getData() < value){
                currentPrt = currentPrt->getNextPtr();
            }
            Node *newPtr = new Node(value);
            newPtr->setNextPtr(currentPrt->getNextPtr());
            currentPrt->setNextPtr(newPtr);
            newPtr->setBeforePtr(currentPrt);
        }
        else{
            while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
                currentPrt = currentPrt->getBeforePtr();
            }
            Node *newPtr = new Node(value);
            if (currentPrt->getBeforePtr() != nullptr){
                currentPrt = currentPrt->getBeforePtr();
                newPtr->setNextPtr(currentPrt->getNextPtr());
                currentPrt->setNextPtr(newPtr);
                newPtr->setBeforePtr(currentPrt);
            }
            else{
                currentPrt->setBeforePtr(newPtr);
                newPtr->setNextPtr(currentPrt);
            }
        }
    }
}

// 原反向打印函数
void MyList::print() const {
    Node *ptr;
    ptr = currentPrt;
    while(ptr->getNextPtr() != nullptr){
        ptr = ptr->getNextPtr();
    }
    for (ptr; ptr != nullptr; ptr = ptr->getBeforePtr()){
        cout << ptr->getData() << endl;
    }
}

// 原正向打印函数
/*
void MyList::print() const {
    Node *ptr;
    ptr = currentPrt;
    while(ptr->getBeforePtr() != nullptr){
        ptr = ptr->getBeforePtr();
    }
    for (ptr; ptr != nullptr; ptr = ptr->getNextPtr()){
        cout << ptr->getData() << endl;
    }
}
*/

测试代码 #

#include "MyList.h"

int main() {
    MyList test;
    test.insert(5);
    test.insert(3);
    test.insert(2);
    test.insert(1);
    test.insert(2);
    test.insert(7);
    test.insert(8);
    test.insert(6);
    test.print();
    return 0;
}

测试结果 #

• 正向打印输出（符合预期）：

  1
  2
  2
  3
  5
  6
  7
  8
  

• 反向打印输出（缺失元素）：

  8
  7
  5
  3
  2
  1
  

问题原因与修复方案 #

问题根源 #

反向打印缺失元素是因为insert函数未正确维护双向链表的反向链接：插入新节点时，仅更新了新节点与前后节点的单向链接，未更新新节点下一个节点的beforePtr，导致链表反向遍历出现断裂。

比如插入值6时，新节点被放在5和7之间，但7的beforePtr仍指向5而非6，反向遍历到7时会直接跳回5，跳过6；插入第二个2时也存在同样问题。

修复后的insert函数 #

void MyList::insert(int value) {
    if(currentPrt == nullptr){
        currentPrt = new Node;
        currentPrt->setData(value);
        currentPrt->setNextPtr(nullptr);
        currentPrt->setBeforePtr(nullptr);
    }
    else{
        if(value > currentPrt->getData()){
            while (currentPrt->getNextPtr() != nullptr && currentPrt->getNextPtr()->getData() < value){
                currentPrt = currentPrt->getNextPtr();
            }
            Node *newPtr = new Node(value);
            newPtr->setNextPtr(currentPrt->getNextPtr());
            newPtr->setBeforePtr(currentPrt);
            currentPrt->setNextPtr(newPtr);
            // 新增：更新新节点下一个节点的before指针
            if (newPtr->getNextPtr() != nullptr) {
                newPtr->getNextPtr()->setBeforePtr(newPtr);
            }
        }
        else{
            while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
                currentPrt = currentPrt->getBeforePtr();
            }
            Node *newPtr = new Node(value);
            if (currentPrt->getBeforePtr() != nullptr){
                currentPrt = currentPrt->getBeforePtr();
                newPtr->setNextPtr(currentPrt->getNextPtr());
                newPtr->setBeforePtr(currentPrt);
                currentPrt->setNextPtr(newPtr);
                // 新增：更新新节点下一个节点的before指针
                if (newPtr->getNextPtr() != nullptr) {
                    newPtr->getNextPtr()->setBeforePtr(newPtr);
                }
            }
            else{
                currentPrt->setBeforePtr(newPtr);
                newPtr->setNextPtr(currentPrt);
            }
        }
    }
}

修复后反向打印输出将变为：

8
7
6
5
3
2
2
1

remove函数实现指导（与insert逻辑一致） #

实现思路 #

1. 空链表直接返回；
2. 从currentPrt出发，根据值的大小正向/反向遍历，找到第一个匹配的节点；
3. 断开目标节点的双向链接，处理头部、中间、尾部三种删除场景；
4. 更新currentPrt（若删除的是当前指向的节点）；
5. 释放目标节点内存。

具体代码实现 #

void MyList::remove(int value) {
    if (currentPrt == nullptr) {
        return; // 空链表，无需操作
    }

    Node* target = currentPrt;
    // 找到第一个匹配的节点
    while (true) {
        if (target->getData() == value) {
            break;
        } else if (value > target->getData()) {
            if (target->getNextPtr() == nullptr) {
                return; // 遍历到尾部未找到
            }
            target = target->getNextPtr();
        } else {
            if (target->getBeforePtr() == nullptr) {
                return; // 遍历到头部未找到
            }
            target = target->getBeforePtr();
        }
    }

    // 处理双向链接断开
    if (target->getBeforePtr() != nullptr) {
        target->getBeforePtr()->setNextPtr(target->getNextPtr());
    }
    if (target->getNextPtr() != nullptr) {
        target->getNextPtr()->setBeforePtr(target->getBeforePtr());
    }

    // 更新currentPrt：如果删除的是currentPrt，指向其下一个节点（若存在），否则指向前一个
    if (target == currentPrt) {
        if (target->getNextPtr() != nullptr) {
            currentPrt = target->getNextPtr();
        } else {
            currentPrt = target->getBeforePtr();
        }
    }

    delete target; // 释放内存
}

说明 #

• 该函数删除第一个匹配value的节点；若要删除所有匹配节点，可将查找逻辑改为循环遍历整个链表；
• 处理了删除头部、中间、尾部节点的所有场景；
• 维护了currentPrt的有效性，避免后续操作出错。

内容的提问来源于stack exchange，提问作者Yusuf Halim