Suppose you are writing in a programming language where null
simply doesn't exist. It either uses empty objects or throws a ObjectNonexistentException
or something similar.
Now you want to implement a linked list. But:
You can't point to null
to end the list.
If you point to an empty object to denote the end of the list, it will initialize its own pointer with another empty object. This will go on indefinitely until memory is full.
How do you go about it? What features would that hypothetical programming language have to support to make a linked list possible without using null
in any form?
One solution could be using something that is equivalent to the Maybe type. It has either the value Just x, where x in this case is the next node in the list, or Nothing. The Maybe monad is best demonstrated in Haskell.