从列表中删除对象

发布于 2024-11-07 06:26:52 字数 264 浏览 0 评论 0原文

我的列表项：

typdef struct sNode
{
   struct sNode* next;
   myData data;
} tNode;

我希望实现以下 API：

bool removeNode(tNode* node)
{
... // need to fix list and free node
}

问题是我没有要修改的前一个元素。有什么魔法可以解决吗？

原文

My list item:

typdef struct sNode
{
   struct sNode* next;
   myData data;
} tNode;

I wish to implement the following API:

bool removeNode(tNode* node)
{
... // need to fix list and free node
}

The problem is that I do not have the previous element to modify.
Is there some kind of magic to solve it?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

七秒鱼° 2024-11-14 06:26:52

不可以。您必须从列表的开头遍历才能找到前一个节点，这是相当低效的。这就是单链表的问题。如果您需要速度更快，请使用双向链表（每个节点都有一个下一个和一个上一个指针）。

回复收藏 0 原文

放肆 2024-11-14 06:26:52

你使用的是单链表，如果你想从链表中删除一个节点，你应该从头开始遍历链表。因此，您需要将 API 更改为如下所示：

bool removeNode(tNode * head, tNode* node);

You are using a single linked list, if you want to remove a node from the list, you should traverse the list from head. So, you need to change your API to something like this:

bool removeNode(tNode * head, tNode* node);

回复收藏 0 原文

萌能量女王 2024-11-14 06:26:52

是的（几乎）——您可以将 node->next 的内容复制到 node 中，然后删除 node->next 。

在伪代码中：

sNode* next = node->next; // see below for an important special case
node->data = next->data;
node->next = next->next;
free(next);

我说“几乎”的原因是，如果 node 没有后继者，这将不起作用。在这种情况下，您必须从头开始遍历列表。

此外，您还必须考虑复制数据的额外成本。

如果你经常通过指针删除节点，你应该考虑一下单链表是否是正确的数据结构。例如，双向链表不存在此问题（但确实具有每个节点一个额外指针的额外开销）。

Yes (almost) -- you could copy the contents of node->next into node and then delete node->next instead.

In pseudocode:

sNode* next = node->next; // see below for an important special case
node->data = next->data;
node->next = next->next;
free(next);

The reason I say "almost" is that this doesn't work if node has no successor. In this case you have to traverse the list from the beginning.

Additionally, you have to consider the extra cost of copying data.

If you often delete nodes by pointer, you should think about whether a singly-linked list is the right data structure. For example, a doubly-linked list does not have this problem (but does have the additional overhead of one extra pointer per node).

回复收藏 0 原文

~没有更多了~