提问人：Miroslav Cetojevic 提问时间：3/5/2015 更新时间：3/6/2015 访问量：109
假设的非 Null 语言 - 如何实现链表？
Hypothetical Non-Null Language - How would a Linked List be implemented?
问：
假设你正在用一种根本不存在的编程语言编写。它要么使用空对象，要么抛出一个或类似的东西。nullObjectNonexistentException
现在，您要实现链表。但：
您不能指向结束列表。
null如果指向一个空对象来表示列表的末尾，它将使用另一个空对象初始化自己的指针。这将无限期地持续下去，直到内存已满。
你是怎么做到的？这种假设的编程语言必须支持哪些功能才能在不以任何形式使用的情况下使链表成为可能？null
答：
2赞
zcleghern
3/6/2015
#1
一种解决方案可能是使用与 Maybe 类型等效的东西。它的值要么是 Just x，在本例中是列表中的下一个节点，要么为 Nothing。也许单子在哈斯克尔中得到了最好的证明。
http://learnyouahaskell.com/a-fistful-of-monads
评论
2赞
3/6/2015
你甚至不需要“单子”部分。只需具有两个值子类型就足够了。NoneSome(x)
0赞
zcleghern
3/6/2015
好吧，monadic 部分允许您像任何其他 Maybe 类型一样整齐统一地对列表进行操作，但您是对的。完全没有必要。
0赞
vmorph
3/6/2015
我真的对 monads 一无所知，或者 ，但我假设您不需要做任何相当于 null 检查的事情来避免程序崩溃？NoneSome
0赞
zcleghern
3/6/2015
不，你不会。例如，Maybe 有两个可能的值：Just x 或 Nothing。如果语言支持代数数据类型/模式匹配，则很容易检查变量具有哪个值。现在，如果你是模式匹配，并且没有包含所有可能性的大小写，你的程序就会崩溃。但是，您通常可以将模式设置为包罗万象（很像 switch 语句的默认值）。
2赞
templatetypedef
3/6/2015
#2
您可以使用的一种方法是引入一个虚拟单元格，其下一个指针指向自身。这个虚拟单元格，我们可以称之为 Nil，不需要任何 null 指针。然后，每个链表都可以使用指向 Nil 的指针而不是指向 null 的指针来表示列表结束。
您的问题似乎表明这是行不通的，因为在创建 Nil 单元格时，下一个指针将默认指向一个新单元格，这将无限指向一个新单元格。我不确定这是否一定是真的，因为您可以想象编程语言会为您提供某种初始化指针的方法，而不是自动为其创建新对象。
希望这有帮助！
2赞
Jeffrey L Whitledge
3/6/2015
#3
一种解决方案是让列表末尾的对象指向自身。当然，这需要语言来支持这种能力，但这样的事情并不罕见。
如果该语言具有面向对象的功能，则可以定义要用作列表项的抽象类型或接口，其实现要么指向列表中的下一项，要么指向列表中的下一项。
abstract class ListItem {}
class ListItemNormal : ListItem { ListItem next; }
class ListItemEnd : ListItem { }
某些语言具有依赖类型，其中一个字段的值可以确定另一个字段是否存在。在这种情况下，可以使用单独的布尔变量模拟 null 值。
上一个：实现糖语法
评论