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

拼搏现实的明天。 2022-05-18 07:34 224阅读 0赞

# 一、概念辨析 #

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

*  头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。
 *  头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。

**\[注意\]无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。**

--------------------

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

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

### 优势1：第1个位置的插入删除更加方便 ###

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

##### 插入操作如下 #####

1.  p指向要插入结点的前驱结点，若要插入的结点为第1个位置，则其前驱结点就是头结点，此时p指向头结点。
2.  让新结点s的next指向p的next，即s—>next = p—>next;
3.  让p—>next指向s，即p—>next = s;

##### 删除操作如下 #####

1.  p指向要删除结点的前驱结点，若要删除的结点为第1个位置，则其前驱结点就是头结点，此时p指向头结点。
2.  让临时指针q指向要删除的结点，即q = p—>next；
3.  让p的next指向要删除结点的下一个结点，即p—>next = q—>next；
4.  释放q的空间，即free(q);

--------------------

若没有头结点，在第1个位置插入或删除时，需要动头指针。

##### 插入操作如下 #####

1.  判断要插入的是否是第1个位置，若是需要特殊处理。
2.  若是第1个位置，让新结点s的next指向头指针PtrL。
3.  return s，此时s作为链表的头指针。此时的更新了链表的头指针。
4.  若不是第1个位置，首先找到要插入结点的前驱结点，让p指向这个前驱结点。
5.  让新结点s的next指向p的next，即s—>next = p—>next;
6.  让p—>next指向s，即p—>next = s;
7.  return PtrL，此时PtrL还是作为链表的头指针，没有被修改，但考虑到一致性需要这样写。

##### 删除操作如下 #####

1.  判断要删除的是否是第1个位置，若是需要特殊处理。
2.  若是第1个位置，让s指向要删除的结点。首先判断PtrL是否为空，若是直接return NULL;若不为空，则将链表的头结点挪到下一个位置，即PtrL = PtrL—>next；
3.  free(s);然后return PtrL
4.  若不是第1个位置，首先找到要删除结点的前驱结点，让p指向这个前驱结点。
5.  让临时指针q指向要删除的结点，即q = p—>next；
6.  让p的next指向要删除结点的下一个结点，即p—>next = q—>next；
7.  释放q的空间，即free(q);
8.  return PtrL

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

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

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

--------------------