Ahem. In yesterday's post about iterating over a circularly linked list, I made a mistake. The construction I exhibited, because it completely skips any test at the start of the loop, will crash if the list is empty and hence its head pointer is NULL.
Fortunately, this is fixable by putting an additional test in the switch statement:
switch ((elephant = head) == NULL)
while (elephant = elephant->next, elephant != head)
case 0:
Then if the head pointer is NULL, the switch's input value will be 1, so it won't execute anything in its body at all.
However, I now also realise that there's a better answer in the first place. One commenter yesterday observed (and I had also thought myself) that the problem would be easy if only you could declare an extra flag variable and use it to suppress the first loop test. You can't, under the constraints of C90 syntax, because there's nowhere to put the declaration that doesn't cause further syntactic problems. But actually, I just realised, you don't need an extra variable at all –NULL. So you can just do this:
for (elephant = NULL;
elephant ? elephant != head : (elephant = head) != NULL;
elephant = elephant->next)
So if elephant is NULL on entry to the loop test clause, that's the signal that it's the very first iteration, and we reassign elephant to the loop head pointer (and terminate if even that is NULL). Otherwise, it's a non-head.
This is a cleaner solution than the switch-based one, because it doesn't interfere with case statements inside the user-
OK. Yesterday, I was too busy boggling at this kind of stuff still being done in C rather than C++ to look at the nitty gritty. Now that I see in more detail what you're up to…
What precise structure for a cyclic list did you have in mind? When I implement a cyclic list, I tend to include the head as well as all the elements in the cycle. This may involve some careful casting, but it tends to make other things easier:
typedef struct Link_str { struct Link_str *next; } Link; for (elephant = head->next; elephant!=head; elephant = elephant->next) { ... }In practice, my cyclic lists are invariably doubly-linked. In that circumstance, including the head in the cycle is especially valuable: it avoids a special case when unlinking the first or last element from the list.
headis not a node but just a pointer.I don't think your approach would even have occurred to me, and it certainly wasn't the version used by the actual list of elephants I encountered in the incident that gave rise to this entire thought process. The whole point of them using a cyclic list was that they wanted to be able to go round and round the list very efficiently, so they made advancing to the next (real) element a trivial operation requiring no test. But if a dummy list-head node appears at some point in the list, that advantage is lost, because now advancing to the next element looks something like
elephant = elephant->next; if (elephant == head) elephant = elephant->next;which is no more convenient than doing the obvious thing with a linear listelephant = elephant->next; if (!elephant) elephant = head;The data structure you're looking at seems much more specialised and peculiar; I'm left wondering what its purpose is, and what operations it's expected to permit, with what complexity order. Particularly, any kind of insertion or removal is fiddly, but if the structure is essentially static, why not just use contiguous memory with modular arithmetic?
Well, not any more, is it? :)
Alternatively, perhaps "errata" has come to act as a mass noun when referring to corrections which are measured in effectively continuous units like paragraphs, rather than traditional lists? :)