单链表尾部为空时列表为空

Question

似乎人们总是说，如果单链表的头部是空的，那么这个列表就是空的，但是检查尾部是否也是有效的呢？假设我确定一个列表有一个尾部，我可以检查尾部是否为空，以确定它是否为空吗？

Answer 1

在单链表的最简单实现中，您保留对"node“结构的引用，该结构既包含值又包含对尾部的引用。

如果列表至少包含一个元素，则引用指向头部。

Answer 2

对于单链表，我假设您保留指向'head‘节点和'tail’节点的指针或引用。

情况1-只有在至少有两个节点时才会设置“tail”。

列表中的1个节点:设置了'head‘，但'tail’为空。

列表中的2+节点：'head‘和'tail’都设置为不同的节点。

列表中的0个节点：'head‘和'tail’都为空。

列表中的1个节点：'head‘和'tail’都设置为同一个节点。

列表中的尾节点：'head‘和’2+‘都被设置为不同的节点。

如果您希望单个节点表示某些特殊的数据，例如死胡同或异常值，则情况1是有意义的。在这里，您可以选择检查列表的尾部是否存在，以确定空列表是否会失败。

案例2更容易编码，需要的决策也更少。头部始终是第一个节点，尾部始终是最后一个节点，即使它们是同一个节点。在这里，您选择检查尾巴的存在是非常有意义的。

如果您想要检查尾部，只需确保检查您的库的规范，或者根据案例2的规范构建您自己的列表。