【首元结点、头指针和头节点的概念】
- 首元结点是指链表中存储第一个数据元素的结点。
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针所指结点为链表的头结点；若链表不设头结点，则头指针所指结点为该链表的首元结点；无论链表是否为空，头指针均不为空；头指针是链表的必要元素。
- 头结点是在首元结点之前附设的一个结点，是为了操作的统一和方便而设立的，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
【链表增加头结点的作用】
- 便于首元结点的处理：增加头结点后，首元结点的地址保存在头结点的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，插入在表头或者删除第一个结点时无需特殊处理。
- 便于空表和非空表的统一处理：当链表没有头结点，其头指针应该指向首元结点；则当链表的长度为0（空表）时，头指针也为空。当链表有头结点时，无论链表是否为空，头指针都是指向头结点的非空指针。如图所示的非空单链表，头指针指向头结点；若为空表，则头结点的指针域为空。
创建头结点，其指针域指向空。
【算法代码】
LinkedList LinkedListInit()
{
LinkedListNode* header = (LinkedListNode*)malloc(sizeof(LinkedListNode));
if (nullptr == header)
{
cout << "创建链表头失败" << endl;
return nullptr;
}
header->data = 0;
header->next = nullptr;
return header;
}单链表的创建
单链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。从空表的初始状态开始，依次建立各元素的结点，并逐个插入链表。根据结点插入位置的不同，链表的创建方法可以分为头插法和尾插法。
【头插法】
头插法是指每次申请一个新结点，读入相应的数据元素值，然后将新结点从链表的头部之后逐个插入。如图所示，每次将s所指结点插在最前端：
如图所示为线性表(a, b, c, d, e)采用头插法的创建过程。因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、c、b、a, 输入顺序和线性表中的逻辑顺序是相反的。
【算法代码】
LinkedList LinkedListCreateByHeader(LinkedList slist, ElemType elem)
{
if (nullptr == slist)
{
cout << "链表未初始化" << endl;
return nullptr;
}
else
{
LinkedListNode* header = slist;
LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
if (nullptr == node)
{
cout << "创建结点失败" << endl;
return nullptr;
}
else
{
node->data = elem;
node->next = header->next;
header->next = node;
return header;
}
}
}
釆用头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为，设单链表长为n，则总的时间复杂度为。
【尾插法】
头插法建立单链表的算法虽然简单，但生成的链表中结点的次序与输入数据的顺序相反。尾插法是通过将新结点逐个插入到链表的尾部来创建链表。同头插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能插入到链表尾部，必须增加一个尾指针r, 使其始终指向当前链表的尾结点，如图所示：
