c++ - 双向链表 : Properly deleting an adding something in the middle of a list?

Question

Write the code fragment that appropriately deletes the node pointed to by p (data value 14) in the doubly linked list.

我想我知道如何做到这一点:

(1) 使右侧节点的previous元素指向左侧节点

(2) 使左边的节点next元素指向右边的节点

(3) 将p指向的节点元素设为NULL并删除。

但是我忘记了如何在代码中编写它(已经有一段时间了)。我在想它会是这样的(我假设 node 是一个结构，它包含一个 int 数据、node* next 和 node* previous):

node* x = p->next;
node* y = p->previous;
x->previous = y;
y->next = x;
p->previous = nullptr;
p->next = nullptr;
delete p;
x->previous = y;

---

写代码片段在14和16之间插入一个节点(同图):

node *x = p->next;
node y;
y->previous = x->previous;
y->next = p->next;
x->previous = y; 
p->next = y;

这样可以吗？

Answer 1

删码就差不多好了。但是，请注意一些事情:

1. 您使用的命名不一致(left 应该是 previous)。
2. 您无需将 p 的字段设置为 nullptr，无论如何您都将删除它。
3. 最后的 x->previous = y 将使这个“循环”不是你想要的!

这将是一个更好的近似值:

node *x = p->next;
node *y = p->previous;
x->previous = y;
y->next = x;
delete p;

但是，这有一个警告:如果列表是单例会怎样？也就是说，您只有 p?。请注意 p->next 和 p->previous 都将为 NULL，因此分配给 x y 会报错! (请注意，作为第一个或最后一个元素将导致相同的问题，只是在某些方面)。

代码的第二部分有点问题:

1. 首先请注意，您的代码无法编译:y 是一个变量，您正在通过 y-> 取消引用它。这是一个只能对指针进行的操作[1]。这个问题实际上更深刻，因为 y 被放置在堆栈中，一旦离开范围就会被删除，因此如果您要这样做，您将在链表中得到未定义的行为使用 &y 获取指针。
2. y->previous = x->previous;可以简化为y->previous = p
3. y->y->next = p->next;可以简化为y->next = x

通过这些更正，这将变成:

node *y = new node();
y->previous = p;
y->next = p->next;
p->next->previous = y;
p->next = y;

但是请注意，这又一次不能处理 p 指向列表末尾的情况! (p->next->previous = y 会发生什么？)，因此您应该更正它。另外，p 指向列表的开头而不是结尾有关系吗？你应该处理那个吗？

唯一的实际问题是动态内存的问题，其余的更正只是“可读性”更正。尽管“可读性”是个人喜好，但您应该始终尝试使代码尽可能清晰。

[1] 除非你真的在使用 operator->() 重载，我假设你没有。