双向链表节点迁移技术问询：将希腊神节点从all_gods链表移至greek_gods链表及代码疑问

Let’s break down your three questions one by one and fix the issues in your code:

1. Is the Link class destructor correct? #

No, it’s definitely not. Your current destructor recursively deletes prev and succ nodes, which triggers a chain reaction: deleting one node will delete its neighbors, which in turn delete their neighbors, and so on. This leads to double-free errors and segmentation faults because nodes get deleted multiple times (once by their own destructor, once by adjacent nodes).

The destructor should only clean up the node itself, not the entire linked list. The responsibility of deleting the full list should be handled externally. Fix it to:

~Link() {}
// Or use the default destructor: ~Link() = default;

2. Should we delete the q pointer in the for loop? #

Absolutely not. You’re trying to move q to the greek_gods list, not destroy it. Deleting q frees its memory immediately, making it impossible to reuse, and your broken destructor will also attempt to delete nodes still in all_gods, corrupting the list and causing segmentation faults.

Remove the delete q; line entirely—you’ll manage these nodes via the greek_gods list later.

3. Why does p fail to get the next node after inserting q into greek_gods? #

The problem is your loop iteration logic: when you erase p from all_gods, you’re modifying the list structure but still trying to use p->next() on a node that’s no longer part of the list. This leads to invalid memory access or lost pointers.

To fix this, save the next node before modifying the current one. Additionally, your insert function crashes when greek_gods is empty (since you can’t call insert on a nullptr).

Fixed Full Code #

Here’s the revised code with all issues resolved:

#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;

struct God {
    God(const string &n, const string &m) : name{n}, mythology{m} {}
    string name;
    string mythology;
};

class Link {
public:
    Link(const string &n, const string &m, Link *p = nullptr, Link *s = nullptr) : god{n, m}, prev{p}, succ{s} { }
    Link *insert(Link *n); // Insert n before this object
    Link *erase(); // Remove this object from list
    Link *find(const string &s); // Find s in list
    Link *next() const { return succ; }
    Link *previous() const { return prev; }
    // Fixed destructor: no recursive deletion
    ~Link() {}

    God god;
private:
    Link *prev;
    Link *succ;
};

Link *Link::insert(Link *n) // Insert n before this object; return n
{
    if (n == nullptr) return this;
    n->succ = this;
    n->prev = prev;
    if (prev != nullptr) {
        prev->succ = n;
    }
    prev = n;
    cout << "3.insert " << n << ' ' << n->god.name << "\n\n";
    return n;
}

Link *Link::erase() // Remove *this from list; return successor
{
    if (succ != nullptr) {
        succ->prev = prev;
    }
    if (prev != nullptr) {
        prev->succ = succ;
    }
    // Reset pointers to mark node as detached from any list
    prev = nullptr;
    succ = nullptr;
    cout << "2.erased " << this << ' ' << this->god.name << "\n\n";
    return succ;
}

Link *Link::find(const string &s) // Find s starting from this node
{
    Link *p = this;
    while (p) {
        if (p->god.name == s) return p;
        p = p->succ;
    }
    return nullptr;
}

void print_all(Link *p) {
    while (p) {
        cout << ' ' << p << ' ' << p->god.name << ", " << p->god.mythology;
        p = p->next();
        if (p) cout << "\n";
    }
}

// Helper to safely delete an entire linked list without recursion
void delete_list(Link *head) {
    while (head != nullptr) {
        Link *next_node = head->next();
        delete head;
        head = next_node;
    }
}

int main() try {
    Link *all_gods = new Link{"Four", "Greek"};
    all_gods = all_gods->insert(new Link{"Three", "Greek"});
    all_gods = all_gods->insert(new Link{"Two", "Norse"});
    all_gods = all_gods->insert(new Link{"One", "Greek"});

    cout << "all_gods:\n";
    print_all(all_gods);
    cout << "\n\n";

    Link *greek_gods = nullptr;
    Link *p = all_gods;
    while (p != nullptr) {
        Link *next_node = p->next(); // Save next node before modifying current
        if (p->god.mythology == "Greek") {
            cout << "1.found " << p << ' ' << p->god.name << '\n';
            Link *q = p; // No need to call find—p is already the target node
            // Update all_gods head if we're erasing the first node
            if (q == all_gods) {
                all_gods = next_node;
            }
            q->erase();
            // Insert q into greek_gods (handle empty list case)
            if (greek_gods == nullptr) {
                greek_gods = q;
            } else {
                greek_gods = greek_gods->insert(q);
            }
        }
        p = next_node; // Use saved node to continue iteration
    }

    cout << "all_gods:\n";
    print_all(all_gods);
    cout << "\n";

    cout << "greek_gods:\n";
    print_all(greek_gods);
    cout << "\n";

    // Safely delete entire lists
    delete_list(all_gods);
    delete_list(greek_gods);
} catch (exception &e) {
    cerr << "exception: " << e.what() << '\n';
    return 1;
} catch (...) {
    cerr << "exception\n";
    return 2;
}

Key Fixes Explained: #

• Destructor: Removed recursive deletion to avoid double-free errors and chain deletions.
• Loop Logic: Saved the next node before modifying the current one, ensuring we never lose our place in the list after erasing a node.
• Insert Handling: Added a check for empty greek_gods to avoid dereferencing a null pointer.
• Erase Logic: Reset the erased node’s prev and succ to mark it as detached from any list.
• Safe List Deletion: Added delete_list helper to properly delete every node in a list without recursion or memory leaks.

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