9

我无法理解链表数据结构中第一个节点或所谓的头的性质是什么。链表由节点组成，每个节点包含一些数据和到链表中另一个节点的链接。但是第一个节点是包含数据和到第二个节点的链接的节点吗？还是它只包含到节点的链接（没有数据）？我认为链表中的第一个节点既有数据又有到另一个节点的链接，但在一本介绍性书中解释说，头是一个节点，但它是一个链接，可以让你到达第一个节点。同时head是节点类型的变量。为什么会这样？（如果这很重要，我正在使用 Java）。谢谢。

4

7 回答 7

8

这些称为“虚拟”标头节点，它们允许您编写适用于空列表和非空列表的通用代码。

通常，如果要Node在列表末尾插入 a，则需要两种情况。如果 head为 null，表示列表为空，则您将设置head为 new Node。如果head不为空，则跟随next指针直到获得最后一个Node，并将next指针设置为新的Node。

但是，如果您使用虚拟标头，head则永远不会为空。它将是一个Node带有空next指针的 a，您可以指向您的 new Node，就像列表确实包含节点时一样。

于 2010-12-20T01:34:11.370 回答
2

@falmarri 回答，你可以用任何一种方式实现它。头节点类似于单链表中的任何其他节点。它只是一个起始节点，我们可以用它遍历链表的其余部分。我们可以将 head 实现为节点或指针。

于 2013-09-15T08:25:24.890 回答
1

把它想象成一个节点是一个对象，它有一个变量“数据”来保存值，另一个变量“下一个”指向另一个节点对象来建立链接。请参阅下面的 java 类。

public class ListNode {
private int data;
private ListNode next = null;

public ListNode() {
    // TODO Auto-generated constructor stub
}
//constructor for creating a listNode
public ListNode(int data){
    this.data = data;
}
/*below are setters and getters  */
public void setData(int data){
    this.data = data;
}
public int getData(){
    return this.data;
}
public void setNext(ListNode next){
    this.next = next;
}
public ListNode getNext(){
    return this.next;
}
}

这就是我将如何链接它。

//create 3 list node objects
    ListNode one = new ListNode(1);
    ListNode two = new ListNode(2);
    ListNode three = new ListNode(3);

    one.setNext(two);
    two.setNext(three);

但请注意，我们需要知道头节点以进行任何进一步的操作，例如在列表的末尾、开头或随机位置添加 ListNode。

在我们的例子中，头节点是列表链开始的地方。

希望它清除:)

谢谢普尼斯

于 2012-12-11T18:52:25.330 回答
0

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

于 2010-12-20T01:20:47.243 回答
0

头节点通常与任何其他节点一样，只是它在逻辑上位于列表的开头，并且没有其他节点指向它（除非您有一个双向链表）。

由于没有其他节点指向它，并且您还需要一种简单的方法来查找列表的开头，因此通常存储指向指向头节点的节点的单独指针。这个指针不是一个节点本身，只是一个指向一个的指针。

于 2010-12-20T01:23:46.453 回答
0

如果这是在 C++ 中，您可能会更容易理解，但标头节点更多地只是您用来获得对整个列表的初始访问权限的参考。它引用列表中的第一个“完整”节点，该节点包含列表数据集中的数据项以及对下一个节点的引用。如果这是 C++，一个节点实际上只是一个指向数据结构的“指针”，它只是编译器的内存地址。如果您没有指向您的链表的标头节点，那么它将在“以太”中丢失，再也不会被访问 - 同时仍占用内存空间。

由于 Java 在幕后为您解决了这个问题，因此您实际上不必担心指针。但是，这可能是您感到困惑的原因。由于隐藏了如此多的细节，如果没有任何概念背后的先验知识，您将不得不接受语法规则而不知道它们背后的原因。

从概念上讲，数组是一种列表，就像链表也是一种列表一样。数组在内存中按顺序放置，而链表则不是。数组的成员仅引用其数据项，但由于成员被放置在内存中的位置，因此您可以通过将整数值乘以该数据项的数据类型的大小添加到整个数组的引用来访问它们。这与链表的不同之处在于链表不是按顺序放置的，因此必须使用更复杂的数据结构来组成列表 - 即“节点”。

但是，由于链表在内存中没有按任何顺序放置，编译器不必为它留出一大块数据，因此它可以具有您想要的任何长度而无需重新创建每次你改变它的长度时都会有一个新的。这与数组不同，因为数组的长度是静态的。此外，数组由其第一个成员引用，即（对于名为“a”的数组）这将是“a[0]”或等效的“a”，如果这是 C。但是，链表不会像这样工作，这就是为什么你有一个“标题”或“虚拟”节点来引用整个事情。

关于头节点的另一件事是，在对链表执行各种操作时，您还可以创建一个与“头节点”结构相似的节点，以帮助您对链表执行操作。

于 2010-12-20T02:18:03.307 回答
0

将头节点添加到链表是很好的，因为您在插入或删除第一个节点时不再需要专门化您的方法，您可以像处理其他节点一样处理它们。

于 2021-09-10T02:40:33.007 回答