java 链表中的头节点

Head node in linked lists

提问by user42155

I have problems with understanding what is the nature of the first node, or the so called head, in a linked list data structure. A linked list consists of nodes, and each node contains some data and a link to another node in the list. But is the very first node a node which contains data and a link to the second node? Or is it contain only a link (and no data) to a node? I thought that the very first node in a linked list has both data and a link to another node, but in one introductory book it is explained that the head is a node but a link that gets you to the first node. At the same time head is a variable of the type of the node. Why is it like this? (I am working in Java, if that matters). Thanks you.

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

回答by ACoolie

These are called "dummy" header nodes, and they allow you to write general code that works for empty and non-empty lists.

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

Regularly, if you want to insert a Nodeat the end of your list, you need two cases. If headis null, indicating the list is empty, then you would set headto the new Node. If headis not null, then you follow the nextpointers until you have the last Node, and set the nextpointer to the new Node.

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

However, if you use a dummy header, headwill never be null. It will be a Nodewith a null nextpointer, which you can point to your new Node, just how you would if the list did contain nodes.

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

回答by svKris

A @falmarri answered, you can implement it either way. Head node is similar to any other node in a Singly Linked list. It is just a starting node with which we can traverse the rest of the linked list. We can implement head as either a node or as a pointer.

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

回答by Punith Raj

Think of it like a Node is a object which has a variable "data" to hold the value and another variable "next" which points to another Node object to make a link. see the below java class.

把它想象成一个 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;
}
}

and this is how i would link it.

这就是我将它链接起来的方式。

//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);

But note we need to know the head node for any further manipulation like adding a ListNode at end, beginning or at a random place in the List.

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

a Head Node is one in our case from where the list chain has started.

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

Hope it clears :)

希望它清除:)

Thanks Punith

感谢普尼斯

回答by Michael M. Adkins

If this was in C++, it might be easier for you to understand, but a header node is more just a reference that you use to gain the initial access to the entire list. It references the first "complete" node in the list which contains its data item within the list's data set and a reference to the next node. If this was C++, a node would really be just a "pointer" to a data structure, which is just memory address for the compiler. If you didn't have a header node that pointed to your linked-list, then it would be lost in the "ether" never to be accessed again - while still taking up space in memory.

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

Since Java takes care of this for you behind the scenes, you don't actually have to worry about pointers. But, that could be the reason behind your confusion. Since, so much detail is hidden, without any prior knowledge behind the concepts you would have to just accept the syntax rules without knowing the reasons behind them.

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

In concept, arrays are a type of list, just like linked-lists are also a type of list. Arrays are placed in sequential order in memory whereas linked lists are not. An array's member only references its data item but since the members are placed where they are in memory, you can just access them by adding an integer value multiplied by the size of that data item's data type to the reference for the entire array. This differs from linked-lists by the fact that linked lists aren't placed in sequential order and thus a more complex data structure must be used to make up the list - i.e. a "node".

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

But, since the linked list isn't placed in any kind of order in memory, the compiler doesn't have to set aside a chunk of data for it and thus is why it can have any length you want it to without having to recreate a new one every time you change its length. This differs from an array since arrays' lengths are static. Additionally, an array is referenced by its first member, that is (for an array named "a") this would be "a[0]" or the equivalent "a" if this were C. However, a linked list doesn't work like this and is why you have a "header" or "dummy" node to reference the entire thing.

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

Another thing about the header node is that when performing various operations on a linked-list, you can also create a node that's similar in structure to your "head node" to help in performing your operation on the list.

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

回答by Falmarri

You can implement it either way. A first node that has no data and just a link would be a pretty weird implementation though.

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

回答by Jonathan Wood

A head node is normally like any other node except that it comes logically at the start of the list, and no other nodes point to it (unless you have a doubly-linked list).

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

Since no other node points to it, and you also need an easy way to find the start of the list, it is common to store a separate pointer to a node that points to the head node. This pointer is not a node-itself, just a pointer to one.

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