深刻理解：带头结点和不带头结点的区别使用头结点的优势

电玩女神 2024-04-17 23:40 35阅读 0赞

## 一、概念辨析 ##

线性表的插入删除需要移动大量的元素，因此引入链表（本文讨论单链表）的概念，链表元素之间通过“链”来链接，因此插入和删除时不需要大量的移动元素，而只需要改变“链”的关系即可。

头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。  
头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。  
\[注意\]无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。

## 二、引入头结点的优势 ##

刚刚提到，链表可以没有头结点，但是必须要有头指针，因为要用头指针来标识一个链表。设链表的头指针为pHead。除了头结点之外，还需要一个指向链表一般元素的指针pNode（因为pHead只能指向表头，不能指向其他元素，故需要另设指针）。

优势1：第1个位置的插入删除更加方便  
若使用头结点，则第1个位置的插入和删除都是对p—>next进行操作，而不用动p本身，而且减少了算法分支（即if else分支）具体的流程为：

插入操作如下  
p指向要插入结点的前驱结点，若要插入的结点为第1个位置，则其前驱结点就是头结点，此时p指向头结点。  
让新结点s的next指向p的next，即s—>next = p—>next;  
让p—>next指向s，即p—>next = s;  
删除操作如下  
p指向要删除结点的前驱结点，若要删除的结点为第1个位置，则其前驱结点就是头结点，此时p指向头结点。  
让临时指针q指向要删除的结点，即q = p—>next；  
让p的next指向要删除结点的下一个结点，即p—>next = q—>next；  
释放q的空间，即free(q);  
若没有头结点，在第1个位置插入或删除时，需要动头指针。

插入操作如下  
判断要插入的是否是第1个位置，若是需要特殊处理。  
若是第1个位置，让新结点s的next指向头指针PtrL。  
return s，此时s作为链表的头指针。此时的更新了链表的头指针。  
若不是第1个位置，首先找到要插入结点的前驱结点，让p指向这个前驱结点。  
让新结点s的next指向p的next，即s—>next = p—>next;  
让p—>next指向s，即p—>next = s;  
return PtrL，此时PtrL还是作为链表的头指针，没有被修改，但考虑到一致性需要这样写。  
删除操作如下  
判断要删除的是否是第1个位置，若是需要特殊处理。  
若是第1个位置，让s指向要删除的结点。首先判断PtrL是否为空，若是直接return NULL;若不为空，则将链表的头结点挪到下一个位置，即PtrL = PtrL—>next；  
free(s);然后return PtrL  
若不是第1个位置，首先找到要删除结点的前驱结点，让p指向这个前驱结点。  
让临时指针q指向要删除的结点，即q = p—>next；  
让p的next指向要删除结点的下一个结点，即p—>next = q—>next；  
释放q的空间，即free(q);  
return PtrL

## 优势2:统一空表和非空表的处理 ##

若使用头结点，无论表是否为空，头指针都指向头结点，也就是\*LNode类型，对于空表和非空表的操作是一致的。

若不使用头结点，当表非空时，头指针指向第1个结点的地址，即\*LNode类型，但是对于空表，头指针指向的是NULL，此时空表和非空表的操作是不一致的。