Delete an object from a list

My list item:

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

I wish to implement the following API:

bool removeN开发者_开发知识库ode(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?

No. You would have to traverse from the beginning of the list to find the previous node, which is pretty inefficient. This is the problem with singly-linked lists. If you need this to be fast, use a doubly-linked list (each node has a next and a previous pointer).

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);

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).