链接列表的首节点和起始节点之间有什么区别？

链表中的头节点是否有任何信息，还是只指向链表的第一个节点？
我们可以定义一个头节点作为链表的起始节点吗？
头节点只指向第一个节点吗？链表由节点组成，每个节点包含一些数据和到列表中另一个节点的链接。但是，第一个节点是包含数据和第二个节点链接的节点吗？或者它只包含一个链接（并且没有数据）到一个节点？我认为链表中的第一个节点既包含数据又包含指向另一个节点的链接，但在一本介绍性书籍中，解释了头部是一个节点，但它是一个链接，可让您访问第一个节点。同时head是节点类型的变量。这是为什么？链接列表的首节点和起始节点之间有什么区别？

来源

2012-02-01 ola

这完全取决于链表的实现。 – 2012-02-01 21:26:36

-1

传统上，头节点是链表的第一个节点，但从“类型”的角度来看，它与任何其他节点没有区别。它包含数据以及指向下一个节点（链表的第二个节点，如果存在）的指针。

来源

2012-02-01 21:32:07 Sid

这个答案不一定是正确的。有很多方法来实现一个列表，其中这个例子只有一个。 – 2012-02-01 21:55:51

@Carl - 我没有声称这是唯一的方法。我只是说这是公约。 – Sid 2012-02-01 21:57:00

你有什么基础说明这个实现是约定？ – 2012-02-01 21:59:10

这取决于实施。甲head变量通常是一个节点指针其指向所述第一节点在列表中，如在此一节点列表：

 +--------+ 
head -> | node 1 | -> NULL 
     +--------+

然而，我看到的实现，其中“空”（双链接）列表由两个节点组成，因此插入和删除代码不必担心试图在头部之前或尾部之后插入或删除头部/尾部的边缘情况。

由于要插入的每个位置（以及允许删除的每个节点）都有一个prev和next节点，因此代码将得到简化。

 +-------+ +------+ +-------+ 
head -> | dummy | -> | node | -> | dummy | -> NULL 
NULL <- | node | <- | 1 | <- | node | <- tail 
     +-------+ +------+ +-------+

而不是大量的检查头部或尾部，插入和删除的有：

def insertBefore (node, newnode): 
    newnode.next = node 
    newnode.prev = node.prev 
    node.prev.next = newnode 
    node.prev = newnode 

def deleteNode (node): 
    node.prev.next = node.next 
    node.next.prev = node.prev 
    free node

稍微复杂的列表遍历因为你曾在curr = head.next开始，而不是curr = head，并完成时curr == last而不是curr == NULL，但有些人认为这是一个有效的权衡，以两个未使用的节点为代价。

来源

2012-02-01 21:31:45 paxdiablo

看起来我们非常令人信服地争辩对方:) – Sid 2012-02-01 21:33:45

@Sid：基本上这是因为问题很糟糕。 – ildjarn 2012-02-01 21:37:48

你可以做到这一点，至少三种不同的方式

存储指向列表对象
有一个空的数据成员一个“头”节点内的节点
有一个特殊的“头“没有数据成员的节点

这些都有一些折衷，有利于某些操作或优化使用的空间。

拥有与其他节点相同类型的头对象可以简化一些链接操作。有一个没有数据有效载荷的头节点可以节省内存。将指针存储在列表对象中可能会为空列表保存一个动态分配，但会使得难以实现swap。

没有一个绝对是最适合所有用途的。

来源

2012-02-01 21:35:12

链接列表的首节点和起始节点之间有什么区别？

回答

相关问题