企业官网建设流程全解析

链表是数据结构中最基础、最重要的线性结构之一。与数组不同，链表的节点在物理内存中不必连续存放，而是通过指针将逻辑上相邻的元素串联起来，因此插入和删除操作无需搬移大量数据，时间复杂度为 O(1)（定位到位置后）。

本文以不带头节点的单链表为载体，用 C 语言完整实现初始化、增删查改、打印、清空与销毁等全套操作，并附上每个函数的设计思路与易错点分析。

所谓"不带头节点"，就是链表的head指针直接指向第一个有效数据节点。相比带头节点的版本，不带头节点的链表在操作首元节点时需要额外判断"是否有前驱"，代码中会出现更多分支处理，但这也是理解链表指针操作的绝佳练习。

一、数据结构定义

​ // List.h #pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int ElemType; // 节点结构体 typedef struct ListNode { ElemType data; struct ListNode* next; } ListNode; // 链表管理结构体 typedef struct LinkList { ListNode* head; // 头指针（直接指向第一个有效节点） size_t cursize; // 当前元素个数 } LinkList; ​

这里用LinkList结构体统一管理头指针和元素个数，GetSize可以做到 O(1) 返回。

二、初始化与辅助函数

1. 创建节点

​ ListNode* BuyNode(ElemType val) { ListNode* p = (ListNode*)malloc(sizeof(ListNode)); if (p == NULL) { printf("申请内存失败！\n"); return NULL; } p->data = val; p->next = NULL; return p; } ​

每个新节点都通过malloc从堆上申请，申请后必须判空，否则在内存不足时会引发未定义行为。

2. 初始化链表

​ void InitLinkList(LinkList* pList) { assert(pList != NULL); pList->head = NULL; pList->cursize = 0; } ​

不带头节点的链表初始化非常简单：头指针置空，元素个数归零即可。

3. 判空

​ bool IsEmpty(const LinkList* pList) { assert(pList != NULL); return 0 == pList->cursize; } ​

三、查找操作

3. 按位置查找节点

​ ListNode* FindPos(const LinkList* pList, int pos) { assert(pList != NULL); if (pos < 1 || pos > pList->cursize || IsEmpty(pList)) return NULL; int i = 1; ListNode* p = pList->head; while (i < pos) { p = p->next; i++; } return p; } ​

pos从 1 开始计数，返回第pos个有效节点的地址。注意边界校验，防止越界访问。当pos == 1时，循环不执行，直接返回head，逻辑自然统一。

11. 按值查找

​ ListNode* FindValue(LinkList* pList, ElemType val) { assert(pList != NULL); if (IsEmpty(pList)) return NULL; ListNode* p = pList->head; while (p != NULL) { if (val == p->data) return p; p = p->next; } return NULL; } ​

按值查找需要遍历整个链表，时间复杂度 O(n)。

四、插入操作

4. 尾插

​ bool Push_Back(LinkList* pList, ElemType val) { assert(pList != NULL); ListNode* newNode = BuyNode(val); if (newNode == NULL) return false; if (IsEmpty(pList)) { // 链表为空，尾插即头插 newNode->next = pList->head; pList->head = newNode; pList->cursize++; return true; } // 链表非空，找到最后一个节点 ListNode* p = pList->head; while (p->next != NULL) { p = p->next; } newNode->next = p->next; p->next = newNode; pList->cursize++; return true; } ​

不带头节点的尾插需要分两种情况：空表时相当于头插，非空时遍历到尾部挂接。时间复杂度 O(n)。

5. 头插

​ bool Push_Front(LinkList* pList, ElemType val) { assert(pList != NULL); ListNode* newNode = BuyNode(val); if (newNode == NULL) return false; newNode->next = pList->head; pList->head = newNode; pList->cursize++; return true; } ​

头插无需区分空表与非空表，时间复杂度 O(1)。注意两步赋值的顺序：必须先让新节点指向原首元节点，再更新head指针，否则原链表会丢失。

7. 按位置插入

​ bool Push_Pos(LinkList* pList, int pos, ElemType val) { assert(pList != NULL); if (pos < 1 || pos > pList->cursize + 1) return false; ListNode* newNode = BuyNode(val); if (newNode == NULL) return false; if (pos == 1) { // pos==1 相当于头插 newNode->next = pList->head; pList->head = newNode; pList->cursize++; return true; } // pos!=1，找到前驱节点 ListNode* p = pList->head; int i = 1; while (i < pos - 1) { p = p->next; i++; } newNode->next = p->next; p->next = newNode; pList->cursize++; return true; } ​

核心思路：pos == 1时走头插分支，其余位置找到前驱后执行经典的"三步指针重连"。

五、删除操作

8. 尾删

​ bool Pop_Back(LinkList* pList) { assert(pList != NULL); if (IsEmpty(pList)) return false; if (pList->cursize == 1) { // 只有一个元素，无前驱，尾删即头删 ListNode* q = pList->head; pList->head = q->next; free(q); q = NULL; pList->cursize--; return true; } // 多个元素，找到尾节点的前驱 ListNode* p = pList->head; while (p->next->next != NULL) { p = p->next; } ListNode* q = p->next; p->next = q->next; free(q); q = NULL; pList->cursize--; return true; } ​

不带头节点的尾删同样需要分情况：只有一个元素时相当于头删，多个元素时遍历找到倒数第二个节点。时间复杂度 O(n)。

9. 头删

​ bool Pop_Front(LinkList* pList) { assert(pList != NULL); if (IsEmpty(pList)) return false; ListNode* p = pList->head; pList->head = p->next; free(p); p = NULL; pList->cursize--; return true; } ​

直接保存首元节点地址，将head指向下一个节点后释放。时间复杂度 O(1)。

10. 按位置删除

​ bool Pop_Index(LinkList* pList, int index) { assert(pList != NULL); if (index < 1 || index >= pList->cursize + 1) return false; if (IsEmpty(pList)) return false; if (index == 1) { // index==1 相当于头删 Pop_Front(pList); return true; } // index!=1，找到前驱删除 int i = 1; ListNode* p = pList->head; while (i < index - 1) { p = p->next; i++; } ListNode* q = p->next; p->next = q->next; free(q); q = NULL; pList->cursize--; return true; } ​

12 & 13. 按值删除（单次 & 多次）

​ // 删除第一个匹配值 bool Removeval(LinkList* pList, ElemType val) { assert(pList != NULL); if (IsEmpty(pList)) return false; if (pList->head->data == val) { // 首元节点就是要删除的值 ListNode* n = pList->head; pList->head = n->next; free(n); n = NULL; pList->cursize--; return true; } ListNode* p = pList->head; while (p->next != NULL) { if (p->next->data == val) { ListNode* q = p->next; p->next = q->next; free(q); q = NULL; pList->cursize--; return true; } p = p->next; } return false; } // 删除所有匹配值 bool MoreRemoveval(LinkList* pList, ElemType val) { assert(pList != NULL); if (IsEmpty(pList)) return false; bool flag = false; // 处理头部连续的目标值 while (pList->head != NULL && pList->head->data == val) { ListNode* n = pList->head; pList->head = n->next; free(n); n = NULL; pList->cursize--; flag = true; } // 处理剩余部分 ListNode* p = pList->head; while (p != NULL && p->next != NULL) { if (p->next->data == val) { ListNode* q = p->next; p->next = q->next; free(q); q = NULL; pList->cursize--; flag = true; // 删除后 p 不动，继续检查新移过来的节点 } else { p = p->next; } } return flag; } ​

MoreRemoveval是这段代码中最值得细品的部分：

• 先用while循环处理头部连续的目标值，因为头部节点没有前驱，无法用统一的"找前驱"逻辑处理；
• 删除节点后p不动，因为原p->next->next已经前移了一位，需要留在原地继续检查，否则连续相同值会漏删。

六、打印、清空与销毁

6. 打印链表

​ void Print_List(const LinkList* pList) { assert(pList != NULL); if (IsEmpty(pList)) { printf("链表中,没有元素！\n"); return; } ListNode* p = pList->head; printf("链表中所有元素为："); for (; p != NULL; p = p->next) { printf("%d ", p->data); } printf("\n"); } ​

不带头节点的链表直接从head开始遍历即可，无需跳过哨兵节点。

14. 清空链表

​ void ClearList(LinkList* pList) { assert(pList != NULL); pList->cursize = 0; } ​

⚠️注意：这里的ClearList只将元素个数归零，并未释放节点内存。严格来说这会造成内存泄漏。建议改造为遍历释放所有节点，或者将清空逻辑合并到销毁函数中。

15. 销毁链表

​ void DestroyList(LinkList* pList) { assert(pList != NULL); pList->cursize = 0; pList->head = NULL; } ​

⚠️注意：这里的DestroyList同样未释放节点内存，只是将指针置空。正确的做法应该是遍历链表逐个free节点，参考带头节点版本中的DestoryList实现：

void DestroyList(LinkList* pList) { assert(pList != NULL); while (pList->head != NULL) { ListNode* p = pList->head; pList->head = p->next; free(p); } pList->head = NULL; pList->cursize = 0; } ​

七、带头节点 vs 不带头节点