User3472
User3472

Reputation: 13

Alternative "null" value

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:

Upvotes: 1

Views: 112

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 223737

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.

Upvotes: 1

Related Questions