链接列表中的头节点

Question

我在理解链表数据结构中第一个节点或所谓的头部的性质时遇到了问题.链表由节点组成,每个节点包含一些数据和指向列表中另一个节点的链接.但是第一个节点是包含数据的节点还是到第二个节点的链接？或者它只包含一个节点的链接(没有数据)？我认为链表中的第一个节点既有数据又有到另一个节点的链接,但在一本介绍性书中,解释说head是一个节点,但是一个链接可以带你到第一个节点.同时head是节点类型的变量.为什么会这样？(我在Java工作,如果这很重要).谢谢.

Answer 1

这些被称为"虚拟"头节点,它们允许您编写适用于空列表和非空列表的通用代码.

通常,如果要Node在列表末尾插入a ,则需要两种情况.如果 head为null,表示列表为空,则设置head为new Node.如果head不为null,next则按指针直到你有最后一个Node,并将next指针设置为new Node.

但是,如果使用虚拟标头,head则永远不会为空.它将是一个Node空next指针,你可以指向你的新指针,Node如果列表确实包含节点,你将如何指向它.

Answer 2

您可以通过任何一种方式实现它。不过，没有数据而只有链接的第一个节点将是一个非常奇怪的实现。