链表删除功能的单指针 // 是可能的

Question

目前，我正在研究链表结构。

当我搜索时，链表删除功能使用"双指针"。
在下面的代码中，通过删除函数中的双指针成功删除节点。

#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
class LinkedList
{
private:
node* head;
node* tail;
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
}
void add_node(int n)
{
node* temp = new node;
temp->data = n;
temp->next = nullptr;
if(head == nullptr)
{
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = tail->next;
}
}
node* gethead()
{
return head;
}
void display(node * head)
{
if(head == nullptr)
{
cout << "nullptr : No data" << endl;
return;
}
else
{
node* temp;
temp = head;
while(temp != nullptr)
{               
cout << temp->data << endl;
temp = temp->next;
}
}        
}
void del(node* head, int value)
{       
if(!head)
{
return;
}
else
{
node** nd = &head;
while(*nd && (*nd)->data != value)
nd = &(*nd)->next;
if(*nd)
{
node* temp = *nd;
*nd = (*nd)->next;
delete temp;
}
else
{
cout << "No matching data in the node" <<endl;
}           
}   
}
};
int main()
{
LinkedList la;
la.add_node(10);
la.add_node(20);
la.add_node(30);
la.add_node(40);
la.add_node(50);
la.display(la.gethead()); //10 20 30 40 50 
la.del(la.gethead(), 40);
la.display(la.gethead()); //10 20 30 50
return 0;
}

我只想知道为什么下面的代码不起作用。
我试图通过不使用双指针来简化代码。

#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
class LinkedList
{
private:
node* head;
node* tail;
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
}
void add_node(int n)
{
node* temp = new node;
temp->data = n;
temp->next = nullptr;
if(head == nullptr)
{
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = tail->next;
}
}
node* gethead()
{
return head;
}
void display(node * head)
{
if(head == nullptr)
{
cout << "nullptr : No data" << endl;
return;
}
else
{
node* temp;
temp = head;
while(temp != nullptr)
{               
cout << temp->data << endl;
temp = temp->next;
}
}        
}
void del(node* head, int value)
{       
if(!head)
{
return;
}
else
{
node* pp = head;
while((pp)->data != value)
pp = pp->next;
if(pp)
{
node* temp = pp;  
pp = pp->next;
delete temp;
}
else
{
cout << "No matching data in the node" <<endl;
}    
}   
}
};
int main()
{
LinkedList la;
la.add_node(10);
la.add_node(20);
la.add_node(30);
la.add_node(40);
la.add_node(50);
la.display(la.gethead()); //10 20 30 40 50 
la.del(la.gethead(), 40);
la.display(la.gethead()); //10 20 30 50
return 0;
}

您能否给我一些建议，为什么上面的代码不像第一个代码那样删除节点？
我认为第二个代码必须工作，因为它通过使用指针(保存节点的地址(删除节点。

提前谢谢。

Answer 1

首先，术语是"指针到指针"而不是"双指针"。双指针是指向类型double的变量的指针。

你应该真正意识到指针只是你记忆中的地址。 当你复制指针(即：node* pp = head;(时，你把头指向的地址放在pp中。 什么意思？PP 和 Head 都指向同一个地址。

但是，同样重要的是要记住，pp 和 head 是变量，因此也写在内存中。这么说 - pp 和 head 也有地址，但由于 pp 和 head 是不同的变量，它们有不同的地址。

因此，当您尝试修改头部的内容时，问题就来了。

第一次出现时：

node** nd = &head;
while(*nd && (*nd)->data != value)
nd = &(*nd)->next;

您根本不会修改 head(或*nd(的内容。因此，您可以将该版本与 pp 一起使用。

您的问题出在这段代码中：

pp = pp->next;

在这里，pp 是原始链表项地址的副本，由于它只是一个副本，因此pp = pp->next实际上什么都不做。在这种情况下，您确实应该编写*nd = *nd->next，因为这样会更改原始值而不是您创建的副本。

注意：即使您将在第二个示例中将变量pp更改为指针到指针，您的代码仍然无法删除列表中的第一个元素，因为它是作为常规指针传递到头部的，因此只有您的第一个版本是有效的。