1
$\begingroup$

In a typical singly linked list, the final node is identified by setting its .next pointer to NULL: If node.next == NULL, then node is the final node.

I'm considering an alternative test in which the final node's .next pointer refers back to itself instead: If node.next == node, then node is the final node.

What would be the implications of using this to indicate the end of a linked list instead of using NULL? would there be any advantages or potential drawbacks to this approach in practice?

$\endgroup$

1 Answer 1

0
$\begingroup$

Generally, it doesn't really matter which value you use as a sentinel value – the only requirement is that your sentinel value cannot be a valid value, otherwise, how would you know it's the sentinel value?

So, whether your sentinel value is NULL, 'foobar', or the node itself does not matter from a semantics point of view: all of them allow you to implement a working and correct linked list.

However, there are some drawbacks I can see.

For one, your sentinel value is not a constant, it is variable and dynamic: it changes depending on which node is the tail node. Which means, checking for the sentinel value has to be dynamic as well, you can't simply check against THE sentinel value because there is no THE sentinel value – there are, in fact, infinitely many possible sentinel values.

So, when you are iterating over the list, you have to be careful and manage which node you are comparing the sentinel value against. Whereas with a constant sentinel value, you can just compare against that constant value.

The second drawback I see is related to the restriction I mentioned above: the sentinel value cannot be a valid value. It is relatively easy to extend the concept of a linked list to a circular linked list. However, in your case that is not possible because in a circular linked list of length 1, the successor of a node is the node itself. So, your linked list cannot easily be extended to a circular linked list.

There is also a change in the behavior in the case of a programming error. For example, if you overrun the end of the linked list due to a missing check or a fencepost error:

  • With NULL as the sentinel value, in the best case, your program crashes with a NullReferenceException, in the worst case, your program exhibits undefined behavior, accesses uninitialized memory, or violates some memory boundary. (You didn't specify the language, there will be a huge difference between, say, nil in Lisp, null in Java, or NULL in C.)
  • With a carefully crafted sentinel value, you can arrange it so your program always crashes with a helpful error message.
  • With your scheme, the program runs into an infinite loop.
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.