一篇文章弄懂数据结构中的头结点与头指针

在学习数据结构链表部分时我们和头结点以及头指针可谓冤家路窄。很多时候对这两个概念的混淆会使我们构造链表或者做数据结构题目时非常难受。这里我对这两个概念做了小小的总结。

首先我们定义一个链表结点的结构体：

有头指针无头结点的链表 有头指针有头结点的链表 在链表中，头结点是一个不存放数据的结点，放在链表的最前面，作用是辅助进行链表的操作。我们要注意：头结点的本质是结点，是要占用内存的。 而头指针的本质是指针，指针实际上就是地址，所以头指针只是存放第一个结点的地址。这里的第一个结点可能是存放数据的第一个结点，也可能是头结点。我们可以看到在一个链表中，可以没有头结点，但一定得有头指针。 有些比较严谨的朋友可能会质疑：为什么一定要有头指针呢？

大家可以想一下：假如你现在是一个老师，正在带着一群小朋友去岳麓山春游。来去的路上，为了防止大家走丢，在给小朋友们排好队后，你让每一个小朋友都记住后面那一个小朋友是谁。这样的话只要你知道第一个小朋友的位置就可以管好所有小朋友了（理论上是这样）。其实，头指针就好比第一个同学的位置。如果没有头指针，也就是说老师不知道第一个小朋友的位置(这老师该有多浪)，那她怎么能找到后面的小朋友呢？ 从这个例子中我们可以看到头指针的重要性。头指针就是这样保存着第一个结点的地址，从而往后寻访后面的结点。所以头指针对于一个链表是必不可少的。

头结点是一个没有数据的空结点，你可以要这个结点（头结点），也可以不要。当然，存在即合理，计算机科学家们在链表中加了一个头结点，就必然有作用。 实际上，相较而言，有头结点的链表出现bug可能性更小。并且有了头结点后，对链表第一个存数据的结点进行插入和删除时，与其它部位结点保持一致。这样写程序会方便不少（大佬请屏蔽我这句话）。

如删除中间元素a2的操作： a1->next=a1->next->next；

对一个无头结点的链表： 当删除a1时 head=head->next； （head代表头指针） 形式与删a2不类似

对一个有头结点的链表： 当删除a1时 head->next=head->next->next； 形式与删a2类似

对链表第一个存数据的结点的插入操作不再举例。 在构造链表时，建议使用头结点。

下面我们来看有头结点和无头结点时链表的构造方法示例 有头指针有头结点的链表构造方法示例：

有头指针无头结点的链表构造方法示例：