我正在努力实现我自己的双向链表。我决定在列表末尾使用哨兵节点，它将存储指向列表中最后一个节点的指针，最后一个节点将存储指向哨兵节点的指针。这是一个好方法还是应该以不同的方式使用哨兵节点？我的代码：
template <class T>
class MyList
{
public:
MyList() : m_first(nullptr), m_last(nullptr), m_sentinel(new Node()) {}
~MyList()
{
delete m_sentinel;
}
void push_back(const T & data);
void pop_back();
void push_front(const T & data);
void pop_front();
class iterator;
iterator begin()
{
if(m_first == nullptr) return iterator(m_sentinel);
return iterator(m_first);
}
iterator end()
{
return iterator(m_sentinel);
}
private:
struct Node;
Node * m_first;
Node * m_last;
Node * m_sentinel;
};
template <class T>
struct MyList<T>::Node
{
Node() : m_data(nullptr), m_next(nullptr), m_prev(nullptr) {}
Node(T * data, Node * next, Node * prev) : m_data(data), m_next(next), m_prev(prev) {}
~Node() { delete m_data; delete m_prev; }
T * m_data;
Node * m_next;
Node * m_prev;
};
这是一种使用哨兵节点的方法，但问问自己：是什么让最后一个节点在双向链表中与众不同？双向链表具有对称性;向前和向后看起来相同，模化一些命名差异。将哨兵节点放在最后一个节点之后会破坏这种对称性，除非您还在第一个节点之前放置了一个哨兵节点。
因此，让我们在第一个节点之前放置另一个哨兵节点。但是等等——为什么我们需要两个哨兵节点？最后一个之后的哨兵对其"上一个"指针有要求，而第一个哨兵对它的"下一个"指针有要求。这些要求并不矛盾;它们可以通过单个哨兵节点来满足。如果使用单个哨兵节点，则会得到一个循环的双向链表，哨兵节点同时标记起点和终点。
是时候把事情提升到另一个层次了。指向第一个和最后一个节点的指针的目的是什么？更重要的是，m_first比m_sentinel->m_next有什么好处？好吧，后者确实有额外的间接级别。如果我们处理这个问题，MyList只需要跟踪哨兵节点。嗯......
template <class T>
class MyList
{
public:
MyList() : m_sentinel() { m_sentinel.m_next = m_sentinel.m_prev = &m_sentinel; }
~MyList() { /* Empty for now, but see the text after the code. */ }
/* Public API omitted */
private:
struct Node {
/* Definition omitted in this illustration. */
/* Needing the definition here instead of later in the file is one drawback. */
};
Node * first() { return m_sentinel.m_next; }
Node * last() { return m_sentinel.m_prev; }
Node m_sentinel; // <-- not a pointer!
};
此版本的MyList具有与您的相同大小(它由三个指针组成)，但更好地利用 sentinel 节点来简化向列表添加节点和从列表中删除节点的过程。我会注意到，有助于这项工作的一个细节是，您的节点存储指向数据的指针，而不是将数据直接存储在节点中。因此，像往常一样，选择使用哪种实现归结为分析优缺点。
如果你真的走这条路，你会在如何管理内存方面遇到一个奇怪的问题。您已让每个节点负责删除其他节点。这对于长列表可能会有问题，因为您可能会耗尽堆栈空间(~Node()退出前对前一个节点的调用~Node()，因此您的调用堆栈随节点数线性增长)。它也是非惯用语，因为节点不负责创建其他节点。根据经验，创建节点的对象应负责确保节点被销毁。也就是说，没有同一级别的相应new，就没有delete。将销毁节点的责任转移到可以迭代处置节点的~MyList()，而不是递归处置。