logo标签列表

链表中的头节点

javalinked-listhead
10

我不理解链表数据结构中第一个节点的本质，也就是所谓的头节点。链表由节点组成，每个节点包含一些数据和指向列表中另一个节点的链接。但是，第一个节点是否是一个包含数据和指向第二个节点的链接的节点？还是只包含到另一个节点的链接（没有数据）的节点？我认为，链表中的第一个节点既包含数据又包含指向另一个节点的链接，但在一本入门书中，它被解释为头是一个节点，但是链接可以让您到达第一个节点。同时，头是节点类型的变量。为什么会是这样呢？（如果这有影响，我正在使用Java）。谢谢。

7个回答
9
这些被称为“虚拟”头节点，它们允许您编写适用于空列表和非空列表的通用代码。
通常，如果您想在列表末尾插入一个Node，则需要两种情况。如果head为空，表示列表为空，则将head设置为新的Node。如果head不为空，则跟随next指针直到最后一个Node，并将next指针设置为新的Node。
然而，如果您使用虚拟头，则head永远不会为空。它将是一个带有空next指针的Node，您可以将其指向您的新Node，就像列表包含节点时一样。
2

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

1

可以将Node看作是一个对象，它有一个变量"data"来保存值，另一个变量"next"指向另一个Node对象以建立链接。请参见下面的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。

在我们的情况下，头节点是链表起始的节点之一。

希望这能解释清楚：）

谢谢 Punith

在 ListNode one = new ListNode(1); 中的数字 1 或者 ListNode two = new ListNode(2); 中的数字 2 括号里代表什么？它有什么作用？ - Sam
@Sam，看一下ListNode(int data)的构造函数参数。它接收数据并将其分配给对象的数据变量。 - Punith Raj
0

你可以用任何一种方式来实现它。但只有一个没有数据，只有链接的第一个节点会是一种非常奇怪的实现方式。

不一定。使用“哨兵”零节点可以简化在链表上执行的许多操作-例如，许多操作不再需要显式检查空列表。 - Anon.
好的，你说得对，但我想这取决于你要解决的问题。我个人从未必须使用带有空第一个节点的链表。 - Falmarri
该实现是针对JDK6中的LinkedList。 - Anna
0

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

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

根据我的书，这个单独的指针具有与其他节点相同的数据类型。因此，它本身不是一个节点，但确实具有与节点相同的类型，这正确吗？ - user42155
这取决于您使用的编程语言。在Java之类的语言中，指向第一个节点的指针最可能必须是节点。而在C或C++之类的语言中，您可以拥有一个真正的指针。 - Falmarri
0
如果这是C ++，你可能更容易理解，但头节点只是一个引用，您可以使用它来获得对整个列表的初始访问。 它引用列表中包含其数据项及下一个节点引用的第一个“完整”节点。 如果这是C ++，节点实际上只是指向数据结构的“指针”，这只是编译器的内存地址。 如果您没有指向链接列表的头节点，则它将在“以太”中丢失，再也无法访问 - 同时仍占用内存空间。
由于Java在幕后为您处理这些问题，因此实际上不必担心指针。 但是，这可能是您困惑的原因。 由于隐藏了如此多的细节，如果没有相关概念的先前知识，您将不得不接受语法规则而不知道背后的原因。
在概念上，数组是一种列表类型，就像链接列表也是一种列表类型一样。数组按顺序放置在内存中，而链接列表则不是。数组的成员只引用其数据项，但由于成员放置在内存中的位置，您可以通过将整数值乘以该数据项数据类型的大小加到整个数组的引用上来访问它们。这与链接列表不同之处在于，链接列表没有按顺序放置，因此必须使用更复杂的数据结构来构建列表 - 即“节点”。
但是，由于链接列表没有按任何顺序放置在内存中，编译器不必为其设置一块数据块，因此它可以具有您希望它具有的任何长度，而无需每次更改其长度时都重新创建一个新的列表。这与数组不同，因为数组的长度是静态的。此外，数组是通过其第一个成员引用的，即（对于名为“a”的数组）这将是“a [0]”或等效的“a”，如果这是C的话。然而，链接列表不是这样工作的，这就是为什么你需要一个“标题”或“虚拟”节点来引用整个列表的原因。
关于头节点的另一件事是，在对链表执行各种操作时，您还可以创建一个类似于“头节点”的结构节点，以帮助在列表上执行操作。
0
将头节点添加到链表中是一个好的做法，因为当插入或删除第一个节点时，您不再需要专门处理方法，可以像处理其他节点一样处理它们。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接