双向链表新增节点时旧节点被覆盖的原因及解决方法

问题描述 #

实现双向链表时，前两个节点添加正常，但第三个节点添加后第二个节点被覆盖，输出如下：

List status now: 7,
List status now: 7, 4,
List status now: 7, 2,

相关代码如下：

Node结构体 #

struct Node {
public:
    int Daten;

    Node* Next = nullptr;
    Node* Last = nullptr;

    Node() {
    }

    Node(int Daten) {
        this->Daten = Daten;
    }
};

LList类 #

class LList {
public:
    Node head;
    Node* NodePtr = &head;

    void AddNode(int Key) {
        if (NodePtr != &head) {
            Node newnode(Key);
            NodePtr = &head;
            NodePtr->Next = &newnode;
            newnode.Last = NodePtr;
            NodePtr = NodePtr->Next;
        }
        else {
            head.Daten = Key;
            NodePtr = nullptr;
        }
    }


    void printList() {
        std::cout << "List status now: ";
        Node* Localcopy = &head;
        while (Localcopy != nullptr) {
            std::cout << Localcopy->Daten << ", ";
            Localcopy = Localcopy->Next;
        }
        std::cout << std::endl;
    }

};

主函数 #

int main() {
    LList mytree;
    mytree.AddNode(7);
    mytree.printList();
    mytree.AddNode(4);
    mytree.printList();
    mytree.AddNode(2);
    mytree.printList();

    return 0;
}

问题原因 #

1. 栈对象生命周期失效：AddNode的if分支中，Node newnode(Key)是栈上的局部对象，函数执行完毕后该对象会被销毁，内存被回收。第二次添加节点时，head->Next指向的是已经失效的栈内存；第三次调用AddNode时，新的newnode会复用这块被释放的内存，导致看起来第二个节点被覆盖。
2. 节点追加逻辑完全错误：每次添加新节点时，代码强制将NodePtr重置为&head，然后把head->Next指向新节点——这不是在链表尾部追加，而是直接替换head的下一个节点，自然会覆盖之前的节点。

忽略的错误点 #

• 混淆栈内存与堆内存的生命周期，用栈局部对象作为链表节点，导致野指针和内存复用问题。
• AddNode函数逻辑错误，没有遍历到链表尾部追加节点，而是直接修改head的Next指针。
• 没有维护尾指针，也没有正确遍历链表找到尾部的逻辑。

修复方案 #

推荐方案：使用堆内存创建节点 #

通过new在堆上创建节点，确保节点生命周期不受函数调用影响，同时维护头、尾指针实现尾部快速追加：

class LList {
public:
    Node* head = nullptr;
    Node* tail = nullptr;

    void AddNode(int Key) {
        Node* newnode = new Node(Key);
        if (head == nullptr) {
            // 空链表时，头、尾都指向新节点
            head = newnode;
            tail = newnode;
        } else {
            // 尾部追加节点，更新双向指针
            tail->Next = newnode;
            newnode->Last = tail;
            tail = newnode; // 更新尾指针到新节点
        }
    }

    void printList() {
        std::cout << "List status now: ";
        Node* Localcopy = head;
        while (Localcopy != nullptr) {
            std::cout << Localcopy->Daten << ", ";
            Localcopy = Localcopy->Next;
        }
        std::cout << std::endl;
    }

    // 析构函数释放堆内存，避免泄漏
    ~LList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->Next;
            delete current;
            current = next;
        }
    }
};

备选方案：使用栈对象（不推荐） #

若坚持使用栈对象，需确保节点生命周期覆盖链表的整个使用周期，比如在外部创建节点后传入：

// 修改AddNode函数
void AddNode(Node* newnode) {
    if (head == nullptr) {
        head = newnode;
        tail = newnode;
    } else {
        tail->Next = newnode;
        newnode->Last = tail;
        tail = newnode;
    }
}

// 主函数中使用
int main() {
    LList mytree;
    Node n1(7), n2(4), n3(2);
    mytree.AddNode(&n1);
    mytree.printList();
    mytree.AddNode(&n2);
    mytree.printList();
    mytree.AddNode(&n3);
    mytree.printList();

    return 0;
}

修复后效果 #

运行主函数会得到预期输出：

List status now: 7,
List status now: 7, 4,
List status now: 7, 4, 2,

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