具有双链表的前哨方法 [英] Sentinel approach with Doubly Linked List
问题描述
I am going through the doubly linked list in Java, I am reading about Sentinels in the doubly linked list from Book. Which states that
为避免某些特殊情况，在附近操作时双链列表的边界，它有助于在以下位置添加特殊节点列表的两端:列表开头的标头节点，以及列表末尾的预告片节点.这些虚拟"节点是已知的作为前哨(或后卫)，并且它们不存储主序列
In order to avoid some special cases when operating near the boundaries of a doubly-linked list, it helps to add special nodes at both ends of the list: a header node at the beginning of the list, and a trailer node at the end of the list. These "dummy" nodes are known as sentinels (or guards), and they do not store elements of the primary sequence
那些特殊情况是什么?为什么我们需要哨兵方法?是强制性的吗?如果我们对双链表使用普通方法(没有哨兵)，是否会节省这些额外节点的内存?当以循环方式制作双链表时，我们必须删除前哨吗?
What are those special cases? Why we need Sentinels approach? Is it compulsory? If we use the normal approach (without sentinels) for doubly linked list wouldnt that save the memory of these extra nodes? When making double linked list with circularly approach in that way we have to remove sentinels?
推荐答案
Wikipedia笔记简要提到了使用哨兵节点简化链接列表的实现.
The Wikipedia notes briefly mention using a sentinel node to simplify the implementation of linked lists.
前哨节点是位于列表前面的虚拟节点.
A sentinel node is a dummy node that goes at the front of a list.
在双向链接列表中，前哨节点指向列表的第一个和最后一个元素.我们不再需要为列表的开头和结尾保留单独的指针，就像我们必须处理单链接列表一样.
In a doubly-linked list, the sentinel node points to the first and last elements of the list. We no longer need to keep separate pointers for the head and tail of the list, like we had to do with singly-linked lists.
我们也不必担心更新头和尾指针，因为正如我们将看到的，如果我们在前哨节点之后插入，从而在列表的前面添加项目，或者在前哨节点之前插入，这会自动发生，因此将一个项目添加到列表中.
We also do not have to worry about updating the head and tail pointers, since as we shall see, this happens automatically if we insert after a sentinel node, hence prepending an item to the list, or insert before a sentinel node, hence appending an item to the list.
我们可以消除用于单链列表的容器对象，因为哨兵节点可以跟踪列表中的第一个和最后一个元素.如果这样做，则将向用户返回指向前哨节点的指针.
We could eliminate the container object that we used for singly linked lists, since the sentinel node can keep track of both the first and last elements in the list. If we did so, then we would return a pointer to the sentinel node to the user.
但是，通常使用容器对象设计数据结构，该容器对象会介导数据结构的用户与数据结构的实现之间的通信，因此我们将保留容器对象.
However, data structures are generally designed with a container object that mediates the communication between the user of the data structure and the implementation of the data structure, so we will retain the container object.
@ 6502在>前哨节点的答案是否比NULL有好处?非常有帮助.
An answer by @6502 on How does a sentinel node offer benefits over NULL? is very helpful.
以下是在双向链接的节点列表中删除节点的代码，其中使用NULL标记列表的末尾，并且使用第一个和最后两个指针保存第一个和最后一个节点的地址:
The following is the code for node deletion in a doubly-linked list of nodes where NULL is used to mark the end of the list and where two pointers first and last are used to hold the address of first and last node:
// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
else first = n->next;
if (n->next) n->next->prev = n->prev;
else last = n->prev;
，这是相同的代码，相反，这里有一个特殊的虚拟节点来标记列表的末尾，并且列表中第一个节点的地址存储在特殊节点的下一个字段中，而最后一个节点位于该列表存储在特殊虚拟节点的prev字段中:
and this is the same code where instead there is a special dummy node to mark the end of the list and where the address of first node in the list is stored in the next field of the special node and where the last node in the list is stored in the prev field of the special dummy node:
// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;
对于节点插入，也存在相同的简化形式.例如，在节点x之前插入节点n(具有x == NULL或x ==& dummy表示在最后位置插入)，代码应为:
The same kind of simplification is also present for node insertion; for example to insert node n before node x (having x == NULL or x == &dummy meaning insertion in last position) the code would be:
// Using NULL and pointers for first and last
n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
else first = n;
if (n->next) n->next->prev = n;
else last = n;
和
// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;
如您所见，对于双链表，所有特殊情况和所有条件都删除了虚拟节点方法.
As you can see the dummy node approach removed for a doubly-linked list all special cases and all conditionals.
这篇关于具有双链表的前哨方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
