传递链表而不在C++内存泄漏的情况下

Question

在很多情况下，我们需要大幅修改链表，因此我们有时会创建另一个链表并将其传递给旧链表。例如

struct node {       //let's say we have a linked list storing integers
int data;
node* next;
};

假设我们已经有一个存储整数 1,2,3 的链表。

node* head; //suppose we already store 1,2,3 in this linked list
node* new_head ; //suppose we make a temporary linked list storing 4,5,6,7
head = new_head; //modifying the original linked list

我的问题如果我在
分配之前删除 head(旧的链表(，那么整个程序将崩溃。 相反，如果我不删除它，那么就会有内存泄漏。
因此，我正在寻找一种在没有内存泄漏的情况下修改链表的方法。

我的尝试
我试图制作一个类似于strcpy的辅助函数来完成我的工作。

void passing_node(node*& head1, node* head2){   //copy head2 and paste to head1 
node* ptr1 = head1;
for (node* ptr2 = head; ptr2 != nullptr; ptr2 = ptr2->next)
{
if (ptr1 == nullptr){
ptr1 = new node;
}
ptr1->data = ptr2->data;
ptr1 = ptr1->next;
}
}
// note that we assume that the linked list head2 is always longer than head1.

但是，我仍然在程序中崩溃，我想不出任何其他方法来修改它。任何帮助将不胜感激。

Answer 1

避免内存泄漏的更简单方法是避免原始拥有指针。

您可以使用std::unique_ptr(或重写您自己的版本(：

struct node {
int data = 0;
std::unique_ptr<node> next;
};

您可以移动节点。

您无法再复制节点(可能存在双重释放问题(。

所以deep_copy可能看起来像：

std::unique_ptr<Node> deep_copy(const Node* node)
{
if (node == nullptr) return nullptr;
auto res = std::make_unique<Node>();
res->data = node->data;
res->next = deep_copy(node->next.get());
return res;
}

Answer 2

我建议预先分配链表，以便在一次调用中轻松删除每个节点。然后，节点将仅引用此预分配内存中的某个位置。例如：

struct Node
{
int   value;
Node* next;
};

struct LinkedList
{
Node* elements;
Node* first;
Node* last;
Node* free_list;
LinkedList(size_t size)
{
first     = nullptr;
last      = nullptr;
elements  = new Node[size]{0};
free_list = elements;
for (size_t i = 0; i < size-1; ++i)
free_list[i].next = &free_list[i+1];
free_list[count-1].next = nullptr;
}
~LinkedList()
{
delete[] elements;
}
void Add(int value)
{
if (free_list == nullptr)
// Reallocate or raise error.
// Take node from free_list and update free_list to
// point to the next node in its list.
// Update last node to the new node.
// Update the first node if it's the first to be added.
}
void Free(Node* node)
{
// Search for the node and update the previous and
// next's pointers.
// Update first or last if the node is either of them.
// Add the node to the last place in the free_list
}
};

从这里开始，您将有许多添加或删除节点的策略。只要确保只将节点添加到分配的elements阵列，就永远不会有任何内存泄漏。在添加之前，您必须检查阵列是否具有再添加一个节点的能力。如果没有，则必须引发错误，或重新分配新的 LinkedList，复制所有值，然后删除旧值。

当数组变得碎片化时，它会变得更加复杂。您可以使用"可用列表"来跟踪已删除的节点。基本上，所有被删除节点的链接列表。

请注意，我的代码不完整。基本方法是创建某种分配器，您可以从中分配批量，使用其中的段，然后批量删除。