Java 链表中的虚拟节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22952882/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Dummy nodes in linked lists
提问by user3511965
Q: When are they used? (Homework question)
问：它们什么时候使用？（作业题）
1st and last node in the list
Sometimes used as 1st and last nodes in the list
Never used as 1st and last nodes in the list
列表中的第一个和最后一个节点
有时用作列表中的第一个和最后一个节点
从未用作列表中的第一个和最后一个节点
Wikipedia says,
维基百科说，
A sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. A sentinel node does not hold or reference any data managed by the data structure.
哨兵节点是一个专门指定的节点，与链表和树一起用作遍历路径终止符。哨兵节点不持有或引用由数据结构管理的任何数据。
I'm thinking B but I don't really know.
我在想B，但我真的不知道。
采纳答案by mok
Look, there is a significant difference between a "Dummy" node and a "Sentinel" node.
看，“虚拟”节点和“哨兵”节点之间存在显着差异。
Dummy nodes "Sometimes get used as first and last nodes in the list".
虚拟节点“有时用作列表中的第一个和最后一个节点”。
When you initiate a linked list a common approach is to create a dummy node, and interestingly it's the last node at the same time.
当你启动一个链表时，一个常见的方法是创建一个虚拟节点，有趣的是它同时也是最后一个节点。
Obviously not always first or last nodes of a LL are dummy records.
显然，LL 的第一个或最后一个节点并不总是虚拟记录。
Please note that you can use a dummy node without any data and a null pointer as a sentinel that shows the last node in the LL.
请注意，您可以使用一个没有任何数据的虚拟节点和一个空指针作为显示 LL 中最后一个节点的标记。
You may wonder is it possible to have a LL without any dummy node?
Answer: Yes. You can hold initialization of your LL until the insertion of the first data entry, and to that point just have null pointer as the LL, and after insertion(s) hold a pointer to the head node and always use a null pointer as "Next" node of the tail node.
你可能想知道是否有可能有一个没有任何虚拟节点的 LL？
回答：是的。您可以保持 LL 的初始化，直到插入第一个数据条目，并且到那时，只有空指针作为 LL，并且在插入后保持指向头节点的指针，并始终使用空指针作为“下一个” " 尾节点的节点。
I refer you to thispage for more insight.
我建议您访问此页面以获取更多见解。
回答by Tarkik Mittal
Yes, Answer is 2. Sometimes used as first and last nodes in the list.
是的，答案是 2。有时用作列表中的第一个和最后一个节点。
To answer this question you need to understand need and use of dummy node. I will explain this with the help a link list problem.
要回答这个问题，您需要了解虚拟节点的需求和使用。我将在链接列表问题的帮助下解释这一点。
Say you have Delete a node in a singly link list and only pointer to that node is given to you, How do you delete ?? Answer : If we have HEAD node we can simply traverse until we find that node and delete it, but this will not work if we have pointer of last node, because last node points to NULL. Here we need DUMMY node. which is a blank node that help us build new node of delete node later.
假设您在单链表中删除了一个节点，并且只给了您指向该节点的指针，您如何删除？答：如果我们有 HEAD 节点，我们可以简单地遍历直到找到该节点并删除它，但是如果我们有最后一个节点的指针，这将不起作用，因为最后一个节点指向 NULL。这里我们需要 DUMMY 节点。这是一个空白节点，可以帮助我们稍后构建删除节点的新节点。
In case of doubly link list this problem can be in either direction. Definition of dummy node : a dummy node at the front/end of the list that is there only to reduce the need for special-case code in the linked-list operations. It is an empty template to build new nodes later. problem here is we don't have any head node. We only have pointer to target node only.
在双链表的情况下，这个问题可能出现在任一方向。虚拟节点的定义：位于链表前端/尾部的虚拟节点，仅用于减少链表操作中对特殊情况代码的需求。它是一个空模板，用于稍后构建新节点。这里的问题是我们没有任何头节点。我们只有指向目标节点的指针。
Solution will be like this we will copy data from next node to node what to delete and delete next node.
解决方案将是这样我们将数据从下一个节点复制到要删除的节点并删除下一个节点。
struct node *temp = node_ptr->next;
node_ptr->data = temp->data;
node_ptr->next = temp->next;
free(temp);
but this will not work if we have pointer of last node, because last node points to NULL. Here we need DUMMY node. which is a blank node that help us build new node of delete node later.
但是如果我们有最后一个节点的指针，这将不起作用，因为最后一个节点指向 NULL。这里我们需要 DUMMY 节点。这是一个空白节点，可以帮助我们稍后构建删除节点的新节点。
In case of doubly link list this problem can be in either direction.
在双链表的情况下，这个问题可能出现在任一方向。
Definition of dummy node : a dummy node at the front/end of the list that is there only to reduce the need for special-case code in the linked-list operations. It is an empty template to build new nodes later.
虚拟节点的定义：位于链表前端/尾部的虚拟节点，仅用于减少链表操作中对特殊情况代码的需求。它是一个空模板，用于稍后构建新节点。
Reference : http://pages.cs.wisc.edu/~vernon/cs367/notes/4.LINKED-LIST.html
参考：http: //pages.cs.wisc.edu/~vernon/cs367/notes/4.LINKED-LIST.html
