|
|
|
带头结点的单链表和不带头结点的单链表的区别主要体现在其结构和算法操作上。
|
|
|
|
在结构上，带头结点的单链表不管链表是否为空，均含有一个头结点；而不带头结点的单链表不含头结点。
|
|
|
|
在操作上，带头结点的单链表的初始化为申请一个头结点，且在任何结点位置进行的操作算法一致；而不带头结点的单链表让头指针为空，同时其他操作要特别注意空表和第一个结点的处理。下面列举带头结点的单链表插入操作和不带头结点的单链表插入操作的区别。
|
|
|
|
|
|
|
|
1）带头结点的单链表插入函数insert（Slink *head, int i, ElemType x）
|
|
|
|
带头结点的单链表插入函数的设计思想是：创建一个data域值为x的新结点*p，然后插入到head所指向的单链表的第i个结点之前。为保证插入正确有效，必须查找到指向第i个结点的前一个结点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n)。
|
|
|
|
2）不带头结点的单链表插入函数insert（int i, ElemType x）
|
|
|
|
不带头结点的单链表插入函数的设计思想是：创建一个data域值为x的新结点*p，然后插入到单链表的第i个结点之前。由于链表不带头结点，所以当i=1时插入操作的算法实现，与i>1时是有差别的，必须单独处理。为保证插入正确有效，必须查找到指向第i个结点的前一个结点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n)。
|
|
|
|
可见，带头结点的单链表插入操作和不带头结点的单链表插入操作在算法实现上有很大区别，主要体现在初始化、能否插入成功的判别及插入时的操作上，在带头结点的单链表上插入在任何位置上都是相同的，而在不带头结点单链表的第一个结点和其他结点前插入操作是不同的。
|
|
|
|
对于带头结点的单链表和不带头结点的单链表在其他操作上的区别可类似得到。
|
|
|
