C++链表头部添加节点异常问题及解决方案咨询

我正在实现一个C++链表，目前除了头部添加节点功能外，其余功能均正常。

节点与链表结构 #

节点结构定义：

struct MyNode
{
   string s;
   int i;
   MyNode* pointer;
};

链表类的私有成员结构：

private:
   MyNode first;
   int count;

public:
  // 已实现的其他方法

两种失败的实现及问题 #

第一种实现 #

void Add(Node* node, int index)
{
   if (index == 1)
   {
      node->pointer = &first;
      first = *node;
   }
}

该实现会导致新的first节点指针指向自身，原有其余节点全部丢失。原因是：先将传入节点的pointer指向类成员first的固定地址，随后把first赋值为传入节点的副本，此时新first的pointer依然指向自身地址，链表彻底断裂。

第二种实现 #

void Add(Node* node, int index)
{
   if (index == 1)
   {
      Node n2 = first;
      first = *node;
      first.pointer = &n2;
   }
}

该实现初期看似正常，但离开if代码块后，原应为第二个节点的字符串数据丢失（整数数据未丢失是未定义行为）。原因是：n2是局部变量，代码块执行完毕后会被销毁，first.pointer成为悬垂指针，指向已释放的内存。std::string内部管理堆内存，析构时会释放这部分内存，导致字符串数据丢失；int是值类型，内存释放后可能暂未被覆盖，所以看似正常，但属于危险的未定义行为。

提问 #

能否在不修改现有链表结构（修改会导致已实现的其他方法失效）的前提下，编写正确的头部添加节点方法？

最小可复现代码 #

#include <string>
using namespace std;

struct Person
{
    string forename{};
    string surname{};
    int age{};
    Person* pointer{};
};

class linked_list
{
private:
    Person first;
    int count = 0;

    Person* GetPointer(int index)
    {
        Person* current = &first;
        Person* next = first.pointer;
        if (index == 1) return &first;
        for (int i = 1; (i < index) && (next->pointer != NULL); i++)
        {
            current = next;
            next = next->pointer;
        }
        return current;
    }

public:
    linked_list()
    {
        first.forename = "dummy";
        first.surname = "dummy";
        first.age = 0;
    }
    void Add(Person* p, int index)
    {
        if ((index < 1) || (index > count + 1))
        {
            throw 0;
        }
        else if (index == 1)
        {
            Person p2 = first;
            first = *p;
            first.pointer = &p2;
            /*p->pointer = &first;
            first = *p;*/
        }
        else if (index == count + 1)
        {
            p->pointer = NULL;
            Person* p2 = GetPointer(index);
            p2->pointer->pointer = p;
        }
        else
        {
            p->pointer = GetPointer(index);
            Person* p2 = GetPointer(index - 1);
            p2->pointer = p;
        }
        count++;
    }
};

int main()
{
    linked_list l;
    Person p;
    p.age = 35;
    p.forename = "John";
    p.surname = "Smith";
    l.Add(&p, 1);
}

解决方案 #

可以通过动态分配内存保存原节点的方式解决问题，无需修改现有链表结构：

修改Add方法中index == 1的分支代码：

else if (index == 1)
{
    // 动态分配内存，复制原first节点的内容
    Person* oldFirst = new Person(first);
    // 将新节点内容复制到first
    first = *p;
    // 让新first指向保存原节点的动态内存
    first.pointer = oldFirst;
}

原理说明 #

1. 使用new Person(first)动态分配内存创建原first节点的副本，该对象不会随代码块结束而销毁，内存地址始终有效。
2. 将传入节点的内容复制到类成员first，使其成为新的头节点。
3. 让新头节点的pointer指向动态分配的原节点副本，保证链表的连续性。

这样既不会出现指针指向自身的问题，也不会产生悬垂指针，字符串和整数数据都能正常保留。

注意：后续需要在链表销毁或删除节点时，用delete释放这些动态分配的内存，避免内存泄漏。

内容的提问来源于stack exchange，提问作者Matěj Vondráček