链表不带头可能造成内存泄露

链表是否带头，指的是是否带有一个空节点作为链表的头部，该节点不存储其他信息。

对于是否带头的判断依据，几乎所有的结论都聚焦在“操作区别”上，但是其实是否带头涉及到一个内存泄露的问题。

经典题目“反转单链表”想必大家都做过，如果是不带头节点的链表，反转过后就发生了内存泄露。

现在使用不带头节点的链表， 假设链表如下图所示：

在这里插入图片描述

head是一个main中的栈对象，而非指针，实际调用了4次new，因此析构时应当回收四个指针对象。

下图是翻转过后的。

在这里插入图片描述

注意看tmp本身的地址0x615ca0，是head对象的最后一个对象，而tmp最后一个对象的地址0x7fffffffeab0，是head本身在栈分配的内存地址。

现在，请问：如何回收内存？ 你会发现，回收内存变得困难，因为翻转过程是将head的节点取下，然后挂在新链表上，而head对象本身已经不持有任何节点了，如下图。

在这里插入图片描述

当析构head对象的时候，什么也不会做。

而tmp本身是一个指针，如果单纯析构它，会导致后续的节点泄露。 如果遍历析构它，在尾节点的时候会试图析构0x7ffffffeab0，这个对象是一个栈对象，不允许free。

假如我们在main中初始化的head时候采用new 指针的形式呢？ 如下图：

在这里插入图片描述

此时head本身也是一个堆对象。 翻转过后如下图，

在这里插入图片描述

这时候不会发生free栈对象的情况，但是需要我们手动析构反转过后的链表，但是这个操作是非常容易遗漏的（因为很难察觉head的持有的指针对象已经被偷走了）。

因此最简单的办法，就是写一个带头的链表。翻转前后都挂在这个虚拟头结点上，析构也只需要通过这个头结点进行析构即可，不会发生析构转移的情况（上述head的节点全都被tmp偷走，导致最终析构任务交给了tmp，这就可以认为是析构转移的情况）。

此外，头结点不一定非的是“链表节点”结构，可以是一个guard：负责管理、保护、析构整个链表数据的对象，他持有链表节点，还保存着链表的其他信息，比如size，还可以通过重载它的[]操作符模拟数组的形式来操作链表。 此时的头结点，是一个广义的header，类似ObjectHead，存储元素信息，这个可以扩展到任意数据结构上。

小结一下带头节点的好处：

• 方便析构，避免内存泄露
• 方便记录链表的其他信息
• crud的操作会更简单