Question

问答题5．解释带头结点的单链表和不带头结点的单链表的区别。

Answer 1

1、所有的链表都要有个头指针first，带头结点的链表的头指针指向的是头结点，头结点的指针域指向首元结点，不带头结点的头指针直接指向首元结点。

2、在删除和插入操作中，无论删除和插入的位置如何，带头结点的链表不需要修改头指针的值，而不带头结点的有时候需要。在清空操作中，带头结点的保留头结点，而不带头结点的要销毁。

3、在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。

4、在操作上。带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。

扩展资料：

头结点的作用：

1、防止单链表是空的而设的.当链表为空的时候,带头结点的头指针就指向头结点.如果当链表为空的时候,头结点的指针域的数值为NULL.

2、是为了方便单链表的特殊操作,插入在表头或者删除第一个结点.这样就保持了单链表操作的统一性!

3、单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。

参考资料来源：百度百科--头结点