list - 语言实现如何表示一个空列表？

Question

单链表中的每个节点都是一些数据和指向下一项的指针（如果它是列表的尾部，则为空指针）。

我所知道的具有本机列表类型的每种语言都支持“空”列表，通常带有一些文字语法。

这将如何在机器的内存中表示？

我可以想到几个方法：

• 在具有运行时类型信息（即类型/值对）的语言中，它可以是具有空值项的“列表”类型
• 列表节点中数据项的空指针（但这仅适用于“指针”类型，而不是直接嵌入节点数据结构中的值）
• 一个特殊的符号值

这在语言之间是否存在很大差异，还是有标准的方法来做到这一点？

Answer 1

这取决于实施。

我想一个非常标准的单链表实现看起来像这样：

object List
  Node head

object Node
  Type data
  Node next

对于一个空列表，List.head将只是一个空指针。

或者，一个空列表可以是一个空指针类型List（尽管在某些语言中，这两者之间的区别并不重要）。

您也可以完全摆脱List并将列表定义为 a Node，然后一个空列表可以是：

• 空指针类型Node（同样不适用于某些语言）
• ANode两者都data为next空（如果可能的话，可能无法与具有一个空元素的列表区分开来）

某些语言可能没有空指针的概念，但您应该能够将其替换为特殊对象。