链表是数据结构中最基础、最重要的线性结构之一。与数组不同链表的节点在物理内存中不必连续存放而是通过指针将逻辑上相邻的元素串联起来因此插入和删除操作无需搬移大量数据时间复杂度为 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) { // pos1 相当于头插 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) { // index1 相当于头删 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 不带头节点对比项带头节点不带头节点初始化需malloc一个哨兵节点head NULL即可头插/头删无需特殊判断逻辑统一需单独处理首元节点尾插/尾删仍需遍历但无需判断空表空表时需特殊处理代码复杂度更简洁分支更少分支更多需频繁判断前驱内存开销多一个节点无额外开销 
长河君 · 2026/10/19 2:13:13 · 阅读 1.2k 数据结构：不带头节点的链表
链表是数据结构中最基础、最重要的线性结构之一。与数组不同链表的节点在物理内存中不必连续存放而是通过指针将逻辑上相邻的元素串联起来因此插入和删除操作无需搬移大量数据时间复杂度为 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) { // pos1 相当于头插 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) { // index1 相当于头删 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 不带头节点对比项带头节点不带头节点初始化需malloc一个哨兵节点head NULL即可头插/头删无需特殊判断逻辑统一需单独处理首元节点尾插/尾删仍需遍历但无需判断空表空表时需特殊处理代码复杂度更简洁分支更少分支更多需频繁判断前驱内存开销多一个节点无额外开销