链表是否带头,指的是是否带有一个空节点作为链表的头部,该节点不存储其他信息。
对于是否带头的判断依据,几乎所有的结论都聚焦在“操作区别”上,但是其实是否带头涉及到一个内存泄露
的问题。
经典题目“反转单链表”想必大家都做过,如果是不带头节点的链表,反转过后就发生了内存泄露。
现在使用不带头节点的链表, 假设链表如下图所示:
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,存储元素信息,这个可以扩展到任意数据结构上。
小结一下带头节点的好处: