Search code examples
nulllinked-listlanguage-agnosticprogramming-languagesnon-nullable

Hypothetical Non-Null Language - How would a Linked List be implemented?


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?


Solution

  • 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.

    http://learnyouahaskell.com/a-fistful-of-monads