阅读:0       作者:严长生

头结点和头指针在链表中的作用

对于任意一个链表来说,其构成部分无疑是:头指针头结点存放数据的结点这 3 类,如下图所示:

图 1 完整的链表结构

头指针

头指针是指向链表中一个结点所在存储位置的指针。如果链表中有头结点,则头指针指向头结点;若链表中没有头结点,则头指针指向链表中第一个数据结点(也叫首元结点)。

由于使用链表存储的数据,其真实的物理存储地址并没有相互紧挨着(数组的存储空间是紧挨着的),而是由系统随机分配。所以为了能够方便地找到链表中存储的数据,为链表创建头指针就显得至为重要。

链表有头指针,当我们需要使用链表中的数据时,我们可以使用遍历查找等方法,从头指针指向的结点开始,依次搜索,直到找到需要的数据;反之,若没有头指针,则链表中的数据根本无法使用,也就失去了存储数据的意义。

在计算机中,数据的存储是为了更方便地使用,一切不以使用为目向计算机中存储的数据都是垃圾数据。

头结点

头结点,位于链表的表头,即链表中第一个结点,其一般不存储任何数据,特殊情况可存储表示链表信息(表的长度等)的数据。

头结点的存在,其本身没有任何作用,就是一个空结点,但是在对链表的某些操作中,链表有无头结点,可以直接影响编程实现的难易程度。

例如,若链表无头结点,则对于在链表中第一个数据结点之前插入一个新结点,或者对链表中第一个数据结点做删除操作,都必须要当做特殊情况,进行特殊考虑;而若链表中设有头结点,以上两种特殊情况都可被视为普通情况,不需要特殊考虑,降低了问题实现的难度。

链表有头结点,也不一定都是有利的。例如解决约瑟夫环问题,若链表有头结点,在一定程度上会阻碍算法的实现。

所以,对于一个链表来说,设置头指针是必要且必须的,但有没有头结点,则需要根据实际问题特殊分析。