[background discussion on why he wants to have a search function
that finds "the item before the desired item":]
... if I want to delete elemene with list->Name == 'test' and I
search for list->next->Name I can return the significant element (the one
just before 'test') and then use something like:
position = list->next; // to get the element I want to actually delete
free(position);
otherwise I would have a problem, as there is no pointer to the previous
element. My question was more if the logic of accessing and deleting items
is an [good|bad|acceptable] one then asking you guys to compile and test
this, sorry if this came thru wrong
.
As I think Chuck noted, you can indeed do this, although there are
various corner cases to watch out for.
There is, however, a "more C-like" way to handle the problem. That
is, there is a way to do this in C that is forbidden in quite a few
other languages. (If there is something you can do in C and assembly,
but not in [say] Pascal, I often call that "quite C-like"
.)
Suppose we have a linked-list data structure:
struct list {
struct list *next;
... actual data here ...
};
and a pointer to the head of (i.e., first entry in) the list, which
is initially NULL when the list is empty:
struct list *head = NULL;
Now, in C, we can write the "find entry in list" function so that
it returns a pointer to the <pointer that points to the entry>
(enclosed in <angle brackets> as the pointer points to that item).
Assume for the moment that the item is guaranteed to be in the list,
and consider the following code:
struct list **searchfor(key_type key) {
struct list **pp, *cur;
for (pp = &head; (cur = *pp) != NULL; pp = &cur->next) {
if (SAME_ITEM(key, cur))
break;
}
return pp;
}
Given the "item will be in the list" assumption, one of the SAME_ITEM
tests will succeed and the loop will stop via the "break". We then
return "pp", the value of the pointer through which we found "cur",
which is the matching item.
If the matching item is the head of the list, pp == &head. Otherwise
pp is the address of some list-item's "next" field. To remove the
found item, we need only write:
struct list **pp, *item;
pp = searchfor(key);
item = *pp;
*pp = item->next;
Now "item" is the found item, and *pp -- which is either "head"
itself, or the "next" element of the list entry that points to
"item" -- has been changed to point to item->next. In other words,
if we found the first item in the list, we have just modified "head"
itself, otherwise we have removed some mid-list item, or even the
last item in the list (by having item->next==NULL).
All of this hinges on the "item guaranteed to be in list" condition.
What if the item is *not* in the list?
In that case, no SAME_ITEM test will succeed, and eventually the
loop will stop on the test in the "for" itself, i.e., when cur
becomes NULL. In this case, "pp" is still valid, and is a pointer
to a "struct list *", but *pp is NULL. The searchfor() function
will return this pointer value, whatever it is.
Thus, the test for "was the item found" is:
pp = searchfor(key);
item = *pp;
if (item == NULL) /* it was not found */
...
Again, it is possible that pp == &head, in which case the list is
empty. If the list is *not* empty, however, pp points to the "next"
pointer of the last item in the list. If we now desire to add a
new item to the end of the list, we merely need to do this:
/* newitem->next = NULL; -- if not already set */
*pp = newitem;
To make searchfor() more general, it is better to modify it so that
"head" is not a "global variable" (whatever "global variable" means
to you, the reader) in searchfor(). Note that the only thing
searchfor() does with "head" is take its address. If searchfor()
simply requires the *caller* to take the address, the function
can then work on any list-head:
struct list **searchfor(struct list **phead, key_type key) {
struct list **pp, *cur;
for (pp = phead; (cur = *pp) != NULL; pp = &cur->next) {
if (SAME_ITEM(key, cur))
break;
}
return pp;
}
/* and then later: */
pp = searchfor(&head, key);
In practice, however, linked-list walking is so trivial that doing
this sort of fancy "search, but return a pointer to the pointer
that points to the item" thing is rarely worthwhile. You can just
do the loop in-line wherever needed (e.g., for deletion), and do
the more obvious loop in-line where practical (e.g., for insertion).
If your list is sorted, it might be OK to use this scheme -- but
maintaining sorted lists is not something one should do all that
often either (the time complexity is O(n^2); if the lists are short,
the extra code does not pay off, and if the lists are long, you
are probably better off with a balanced tree or hash table or some
such).
