【C语言数据结构】带头节点与不带头节点的单链表头插法对比

前言

• 近期在学习STM32代码框架的过程中，老师使用链表来注册设备，发现使用了不带头节点的单链表，注册时使用头插法。
• 之前在本专题整理学习过带头节点的单链表，因此本文整理对比一下两种方式的头插法区别，具体实现在次，重点在于用以理解两种思路，以及链表在嵌入式编码中的典型应用。
  

---

---

1.带头节点的链表

• 此部分在链接: 【C语言数据结构】01.单链表中已经详细总结过，此出将最重要的几部分代码整理出来，如下：

typedef struct Node//定义数据结构，包含数据域域next域
{
    int data;//data域
    struct Node* next;//指针域，指向了同样类型的下一个
}Node;

Node* initList()//初始化头节点
{
    Node* list=(Node*)malloc(sizeof(Node));//开辟空间，新建节点
    list->data=0;//链表默认个数为0
    list->next=NULL;//链表为空，故头节点next域为空
    return list;
}

void headINSERT(Node* list,int data)//头插法
{
    Node* node = (Node*)malloc(sizeof(Node));//开辟空间，新建节点
    node->data = data;//data给到新建节点的数据域
    node->next = list->next;//新建节点的next指向的是原先链表的第一个节点，也就是头节点指向的节点
    list->next = node;//头节点指向新建节点
    list->data++;//插入后链表元素加一
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.带头节点的链表

/* 为GPIO按键构造一个InputDevice */
static InputDevice g_tKeyDevice = {
	"gpio_key",
	NULL,
	GPIOKeyInit,
	NULL,
};

/*
 * 函数名称： AddInputDeviceGPIOKey
 * 功能描述： 注册GPIO按键设备
*/
void AddInputDeviceGPIOKey(void)
{
	InputDeviceRegister(&g_tKeyDevice);
}

/*
 * 函数名称： InputDeviceRegister
 * 功能描述： 注册一个输入设备
 * 输入参数： ptInputDevice-输入设备
 */
void InputDeviceRegister(PInputDevice ptInputDevice)
{
	ptInputDevice->pNext = g_ptInputDevices;//g_ptInputDevices为原链表的第一个节点，第一次注册时为空为空
	g_ptInputDevices = ptInputDevice;//将头节点指针指向最新的第一个节点，完成注册
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.对比总结

• 通过上述代码可看出，第二种方式少了头节点。
• 在使用链表时，第一种方式初始化需要对头节点内容进行初始赋值，包括data域数量为0和next域值指向为空。
• 而第二种方式初始化时不需要赋值，即头节点指针直接为空，需要用时直接注册插入即可，省去了头节点，代码上更加高效便捷。
• 一般而言头节点没有存在的必要时（遍历找最后一个Null也可以实现）完全可以使用第二种方式来实现链表注册。
• 同时，注册设备这也是链表在嵌入式实战中的一个典型应用，需要牢记。