【数据结构探秘】手把手用单链表实现增删查改：一篇面向 C 程序员的实战指南

一.引言

       在编程世界，链表是数据结构中非常基础且灵活的线性结构。相比数组，链表在插入和删除操作上能以更低的代价（不需要整体移动元素）完成操作，因此在很多场景下更有优势。想象一下有一列火车，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放⼀把下⼀节车厢的钥匙。这就是链表的核心思想：通过指针，将零散的数据节点串联起来，形成一条链。

        本文就用C语言来实现一个最基础也最重要的链表结构——单链表，并通过代码详细解析如何实现链表的增、删、查、改等基本操作。

二.链表的基本结构

      一个完整的链表由一系列节点（Node）组成，每个节点包含数据域和指针域。与数组（连续内存存储）不同，链表的节点在内存中无需连续分布，而是通过指针形成逻辑上的顺序连接，如同用线串起的珍珠，具备极高的动态性。

typedef int SLDatatype;
typedef struct SListNode
{SLDatatype data;struct SListNode* next;
}SListNode;

       这里我们使用typedef将结构体重命名为SListNode，方便后续使用。SLDatatype被定义为int，但你可以根据需要修改为任何其他数据类型，如char或自定义的结构体。

三.链表的核心操作实现

       接下来，我们基于这个基本结构，一步步实现链表的各种操作。

3.1 节点的创建

       要往链表中添加数据，首先要创建一个新的节点。为了封装这个过程，我们编写了一个静态函数 SListNodeBuy。它负责向堆区申请内存，并初始化节点的数据域和指针域。

static SListNode* SListNodeBuy(SLDatatype x)
{SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));if (newcode == NULL){perror("malloc newcode");exit(1);}newcode->data = x;newcode->next = NULL;return newcode;
}

       这里使用了 malloc 函数动态分配内存。如果内存分配失败，程序会打印错误信息并退出，这是一种良好的编程习惯，能让程序更加健壮。

3.2 尾部插入（SLPushBack）

       在链表末尾插入新节点是常见的操作。只存在两种情况，要么原链表为空，新节点就是头节点；要么原链表不为空，此时需要找到链表的最后一个节点（找尾），然后将新节点连接到它的后面。

void SLPushBack(SListNode** pphead, SLDatatype x)
{assert(pphead);	//指向链表第一个元素的指针的地址肯定不能为NULLSListNode* newcode = SListNodeBuy(x);if (*pphead == NULL)	//如果是空，直接让头指针指向newcode{*pphead = newcode;}else		//如果不是空，则需要找尾{SListNode* ptail = *pphead;while (ptail->next)	//当跳出循环的时候，ptail一定指向最后一个链表的元素{ptail = ptail->next;}ptail->next = newcode;}
}

       这里暗藏一个关键设计：指针的指针。在后续操作中，我们会频繁看到SListNode** pphead的参数形式，这是因为单链表的头指针可能在操作中被修改（如头插、头删），必须通过二级指针才能真正改变实参指针的指向 —— 这是理解链表操作的一个突破口。

3.3 头部插入（SLPushFront）

       在链表头部插入则简单得多，我们只需要让新节点的 next 指向当前的头节点，然后将头指针指向这个新节点即可。

void SLPushFront(SListNode** pphead, SLDatatype x)
{assert(pphead);SListNode* newcode = SListNodeBuy(x);newcode->next = *pphead;*pphead = newcode;
}

同样地，这里也使用了二级指针 pphead 来确保对链表头部的修改能够被保留。

3.4 尾部删除（SLPopBack）

       删除尾部节点是比插入更复杂的操作，因为我们需要找到倒数第二个节点，才能断开与最后一个节点的连接。

void SLPopBack(SListNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* prev = *pphead;SListNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}

这个函数考虑了两种情况：

• 链表只有一个节点：直接释放该节点，并将头指针设为 NULL。

• 链表有多个节点：使用两个指针 prev 和 ptail 进行遍历。ptail 负责向前移动，prev 始终保持在 ptail 的前一个位置。当 ptail 到达末尾时，prev 刚好指向倒数第二个节点，我们就可以通过 prev->next = NULL 来切断连接，并释放 ptail 指向的节点。

3.5 头部删除（SLPopFront）

       删除头部节点则非常直接。我们只需要用一个临时指针 del 保存头节点，然后让头指针指向下一个节点，最后释放 del 所指向的内存。

void SLPopFront(SListNode** pphead)
{assert(pphead && *pphead);SListNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

3.6 打印链表（SLPrint）

       为了方便测试和查看结果，我们还需要一个打印函数来遍历并输出链表中的所有数据。

void SLPrint(SListNode* phead)
{SListNode* pcur = phead;while(pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

这个函数只涉及遍历，不需要修改链表结构，因此只需要传递一级指针。

四.单链表的进阶操作实现

4.1 查找（SLFind）

       在链表中查找某个特定值，是实现其他高级操作的前提。SLFind函数通过遍历链表，逐一比对节点数据，如果找到匹配项，则返回该节点的指针；如果遍历完整个链表都没有找到，则返回NULL。

SListNode* SLFind(SListNode* phead, SLDatatype val)
{SListNode* pcur = phead;while (pcur){if (pcur->data == val){return pcur;}pcur = pcur->next;}return NULL;
}

4.2 在指定位置之前插入（SLFrontInsert）

       在指定位置pos之前插入新节点，我们需要找到pos的前一个节点。我们通过遍历链表，让prev指针始终停在pos的前面。然后，我们进行连接操作：newcode的next指向pos，prev的next指向newcode。需要注意的是，如果pos就是头节点，那么这个操作就退化为头插，我们可以直接复用SLPushFront函数。

void SLFrontInsert(SListNode** pphead, SListNode* pos, SLDatatype x)
{assert(pphead && *pphead);assert(pos);SListNode* prev = *pphead;if (prev == pos){SLPushFront(pphead, x);}else{SListNode* newcode = SListNodeBuy(x);while (prev->next != pos){prev = prev->next;}newcode->next = pos;prev->next = newcode;}
}

4.3 在指定位置之后插入数据（SLBackInsert）

       在指定位置pos之后插入数据是相对简单的操作。我们只需要让新节点的next指向pos的下一个节点，然后将pos的next指向新节点即可。这个操作不需要遍历整个链表，因此非常高效。

void SLBackInsert1(SListNode* pos, SLDatatype x)
{assert(pos);SListNode* newcode = SListNodeBuy(x);newcode->next = pos->next;pos->next = newcode;
}

        这里特别需要强调的是连接的顺序，一共有两种，我们画图来表示：

显然，第二种代码是不合适的。如果先让pos与newcode连接，那就无法再通过链表找到pos->next这个节点了，自然是错误的。

4.4 删除指定位置（SLDelete）

       删除指定位置pos的节点，同样需要找到pos的前一个节点prev。我们通过遍历找到prev后，将prev的next直接指向pos的next，然后释放pos所占用的内存。如果pos是头节点，那这个操作就是头删，我们可以直接复用SLPopFront函数。

void SLDelete(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);SListNode* prev = *pphead;if (prev == pos){SLPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

4.5 删除指定位置之后的数据（SLDeleteAfter）

       这个函数用于删除指定节点pos的下一个节点。这是一个非常高效的操作，因为它不需要遍历链表来找到目标节点的前一个节点。我们只需用一个临时指针保存pos的下一个节点，然后将pos的next指向下下个节点，最后释放临时指针所指向的内存。

void SLDeleteAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

       但是这里需要注意的是，除了pos不能是个空指针，pos->next显然也不能为空。我们要删除pos之后的数据，如果pos->next是空，那我们还删除什么呢？

4.6 销毁链表（SLDestroy）

       当链表不再使用时，我们必须释放其占用的所有内存，以避免内存泄漏。SLDestroy函数通过遍历链表，逐一释放每一个节点，直到链表为空。最后，将头指针设为NULL，彻底完成销毁。

void SLDestroy(SListNode** pphead)
{assert(pphead && *pphead);SListNode* pcur = *pphead;SListNode* del = *pphead;while (pcur){pcur = pcur->next;free(del);del = pcur;}*pphead = NULL;
}

五.结语

        本篇文章实现了单链表从基础到进阶的全部核心功能。从最基本的节点创建、增删，到灵活的查找、指定位置插入与删除，再到最终的链表销毁。

       单链表是所有动态数据结构的基石，深入理解它的原理和实现方式，将为未来学习更复杂的数据结构（如双向链表、树、图）打下坚实的基础。

       如果你在实现过程中遇到了任何问题，或者对其他数据结构有自己的见解，都欢迎在评论区留言。让我们一起交流，共同进步！