null - 假设的非空语言 - 如何实现链接列表？

Question

假设您正在使用一种null根本不存在的编程语言进行编写。它要么使用空对象，要么抛出 aObjectNonexistentException或类似的东西。

现在你想实现一个链表。但：

• 您不能指向null结束列表。

• 如果指向一个空对象来表示列表的末尾，它将用另一个空对象初始化自己的指针。这将无限期地进行，直到内存已满。

你怎么做？null假设的编程语言必须支持哪些功能才能在不以任何形式使用的情况下使链表成为可能？

Answer 1

一种解决方案可能是使用与 Maybe 类型等效的东西。它的值要么是 Just x，在这种情况下，x 是列表中的下一个节点，要么是 Nothing。Maybe monad 在 Haskell 中得到了最好的展示。

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

Answer 2

您可以使用的一种方法是引入一个虚拟单元，其下一个指针指向自身。我们可以称之为 Nil 的那个虚拟单元不需要任何空指针。然后，每个链表都可以使用指向 Nil 的指针而不是指向 null 的指针来表示链表结束。

您的问题似乎表明这不起作用，因为在创建 Nil 单元格时，下一个指针将默认指向一个新单元格，该单元格将无限指向一个新单元格。我不确定这一定是真的，因为你可以想象编程语言会给你一些初始化指针的方法，而不是自动为它创建一个新对象。

希望这可以帮助！

Answer 3

一种解决方案是让列表末尾对象指向自身。当然，这需要语言支持这种能力，但这样的事情并不罕见。

如果该语言具有面向对象的功能，那么您可以定义一个抽象类型或接口以用作列表项，其实现要么指向列表中的下一个项目，要么不指向列表中的下一个项目。

abstract class ListItem {}
class ListItemNormal : ListItem { ListItem next; }
class ListItemEnd : ListItem { }

某些语言具有从属类型，其中一个字段的值可以确定另一个字段是否存在。在这种情况下，可以使用单独的布尔变量模拟空值。