It seems common to have the tail pointer at the end of a linked list be null (0).

What if I want to have two possible different "tails"?

My use case is a big integer representation that supports two's complement: I want to have a tail corresponding to "the rest of this number is zeros" and "the rest of this number is ones", where I can tell them apart just by performing a pointer equality.

It seems like this should be common enough to have standard practice, but it's hard to think of exactly what to search for. It seems somewhat arbitrary that we only get one "forbidden" pointer value (that will give a useful-ish error when accidentally dereferenced).

Options seem to include:

• Use some arbitrary second value (like 1, or 0xdeadbeef). This seems evil. For one thing, I guess it needs to be aligned? Also, I will have obscure bugs if malloc happens to allocate a real linked list cell at the same address. Is there some region of memory malloc is guaranteed not to use?
• Call malloc with a dummy non-zero size. This seems more sensible, but ideally I would have the pointer value be const, rather than requiring initialisation.
• Take the address of something arbitrary, like a function defined in the file. This seems very evil, but does seem to lack any practical disadvantages (assuming it would work).

CodePudding user response：

Given some ListItem type and a desired to have a ListItem * value that serves as a sentinel (also see sentinel node), we can simply define a ListItem object to serve that purpose:

ListItem SentinelObject;
ListItem * const SentinelValue = &SentinelObject;

This could also be made static if they will be used only in one translation unit.

The named object could be eliminated by using a compound literal:

ListItem * const SentinelValue = & (ListItem) {0};

(The initializer may need adjustment if 0 is not a suitable initailizer for the first member of ListItem.)

Alternately, wasting space could be avoided by overlapping the unused ListItem object with some other object:

union { SomeUsefulType SomeUsefulThing; ListItem SentinelObject; } MyUnion;
ListItem * const SentinelValue = &MyUnion.SentinelObject;

While this gives SomeUsefulThing and SentinelObject the same address, that is unlikely to be a problem given they have different types.