尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

单链表从入门到实战：概念、结构与 C 语言接口实现全解析

发布时间：2026/11/1 1:55:35 尧图网站建设
单链表从入门到实战：概念、结构与 C 语言接口实现全解析

目录

  • 1. 链表的定义
    • 1.1 什么是链表
    • 1.2 什么是节点
    • 1.3 节点的结构体代码
    • 1.4 节点和链表的关系
  • 2. 链表的性质
  • 3. 链表的优势
  • 4. 链表的打印
  • 5. 单链表
    • 5.1 申请节点
    • 5.2 链表尾插
    • 5.3 链表头插
    • 5.4 链表头删
    • 5.5 链表尾删
    • 5.6 在指定位置前插入
    • 5.7 在指定位置后插入
    • 5.8 指定位置删除
    • 5.9 查找元素
    • 5.10 打印元素
    • 5.11 销毁链表
  • 6. 总结

1.1 什么是链表

链表是一种在物理存储上节点分散、不连续的存储数据的结构，其逻辑顺序由链表中的指针依次链接而成。与数组需要一整块连续内存不同，链表的每个节点可以散落在内存的任意位置，节点之间靠指针建立联系。
既然如此，那么什么是节点呢？

1.2 什么是节点

节点的构成：数据区域 + 指针区域。数据区域用来存放实际的数据，指针区域用来存放下一个节点的地址。

如上图所示，上半部分是数据区域，用于存放节点数据（例如数据 1）；下半部分存放地址（例如地址 0x0012FFA0）。两者共同构成了一个节点。

1.3 节点的结构体代码

假设当前保存的节点数据是整型：

typedefintSLTDataType;typedefstructSListNode{SLTDataType data;// 节点数据structSListNode*next;// 保存下一个节点的地址}SLTNode;

1.4 节点和链表的关系

节点是组成链表的基本单元，链表则是节点通过指针串联起来的整体。

二者的关系就如同火车与车厢：车厢相当于节点，车厢组成了火车，而节点组成了链表。

需要特别注意的是：第一个节点中存放的是第二个节点的地址，第二个节点指向第三个节点的地址，以此类推，最后一个节点存放的是空指针。

2. 链表的性质

  1. 链式结构在逻辑上是连续的，在物理上不一定连续。
  2. 节点一般是从堆上申请的。
  3. 从堆上申请来的空间按照一定策略分配，每次申请的空间可能连续，也可能不连续。

3. 链表的优势

  1. 动态分配内存：不需要预先确定大小，按需分配节点，不容易造成空间浪费。
  2. 任意位置插入、删除效率高。
  3. 内存不要求连续：节点分散在堆内存中，无需寻找一整块连续的大空间。

4. 链表的打印

voidSLTPrint(SLTNode*phead){SLTNode*pcur=phead;while(pcur){printf("%d",pcur->data);pcur=pcur->next;}printf("\n");}

解释：

  • SLT：Single Linked List，单链表
  • node：节点
  • SLTPrint：打印单链表的接口函数
  • phead：头指针，保存链表第一个节点的地址
  • SLTNode：单链表节点的类型名
  • pcur：当前指针

5. 单链表

单链表只能从头节点向尾部单向遍历，无法直接反向访问前驱节点。也正因为如此，单链表的结构简单、实现方便，是学习链表时最先接触的一种形式；后续的双向链表、循环链表都是在它的基础上扩展而来的。

5.1 申请节点

SLTNode*SLBuyNode(SLTDataType x){SLTNode*node=(SLTNode*)malloc(sizeof(SLTNode));node->data=x;node->next=NULL;returnnode;}

5.2 链表尾插

voidpushback(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*node=SLBuyNode(x);//申请新节点if(*pphead==NULL)//如果链表为空{*pphead=node;return;}//链表不为空，寻找尾节点，并在其后插入新节点SLTNode*pcur=*pphead;while(pcur->next!=NULL){pcur=pcur->next;}pcur->next=node;}

5.3 链表头插

voidSLPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*node=SLBuyNode(x);//创建新节点node->next=*pphead;//新节点指向原来第一个节点*pphead=node;//新节点变为头指针}

5.4 链表头删

voidSLPopFront(SLTNode**pphead){assert(pphead);assert(*pphead);//如果链表为空，就没有节点可以删SLTNode*del=*pphead;//将第一个节点保存在del中*pphead=del->next;//将第二个节点作为首节点//释放头节点，并置为空指针free(del);del=NULL;}

5.5 链表尾删

voidSLPopBack(SLTNode**pphead){assert(pphead);assert(*pphead);if((*pphead)->next==NULL)//链表只有一个节点的情况{free(*pphead);*pphead=NULL;return;}SLTNode*prev=NULL;SLTNode*ptail=*pphead;//初始条件：prev为空指针，ptail在头节点while(ptail->next!=NULL){prev=ptail;ptail=ptail->next;}prev->next=ptail->next;//使prev下一节点为空free(ptail);ptail=NULL;}

5.6 在指定位置前插入

voidSLInsert(SLNode**pphead,SLNode*pos,SLDataType x){assert(pos);assert(pphead);if(pos==*pphead){SLPushFront(pphead,x);}else{SLNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}SLNode*newnode=SLBuyNode(x);newnode->next=pos;prev->next=newnode;}}

5.7 在指定位置后插入

//使用这个函数要搭配SLFind这个函数voidSLInsertAfter(SLNode*pos,SLDataType x){assert(pos);SLNode*newnode=BuySLNode(x);newnode->next=pos->next;pos->next=newnode;}

5.8 指定位置删除

voidSLErase(SLTNode**pphead,SLTNode*pos){assert(pos);//确保删除的节点是有效的assert(pphead);if(*pphead==pos){SLPopFront(pphead);}else{SLTNode*prev=*pphead;while(prev->next!=pos)//寻找该位置的前一个节点{prev=prev->next;}prev->next=pos->next;//进行删除操作free(pos);//释放节点内存}}

5.9 查找元素

SLTNode*SLFind(SLTNode*phead,SLTDataType x){SLTNode*cur=phead;//创建遍历指针，从头节点开始遍历while(cur){if(cur->data==x){returncur;}cur=cur->next;}returnNULL;//循环走完都没找到x，返回空指针，表示查找失败}

5.10 打印元素

voidSLPrint(SLNode*phead){SLNode*head=phead;//新建临时遍历指针head，将头指针赋值给它while(head){printf("%d->",head->data);//打印head里面存的数据head=head->next;}printf("NULL\n");//循环结束后打印NULL}

5.11 销毁链表

voidSLDestroy(SLNode**pphead){assert(pphead);assert(*pphead);SLNode*cur=*pphead;while(cur!=NULL){SLNode*next=cur->next;//保存下一个节点的位置free(cur);//释放当前节点cur=next;//移动到下一个节点}*pphead=NULL;}

6. 总结

本文从最基础的概念出发，完整梳理了单链表的知识体系，可以归纳为以下几个要点：

  1. 概念层面：链表是一种物理存储上不连续、逻辑上连续的数据结构，由一个个节点通过指针串联而成。节点由数据区域和指针区域两部分组成，前者存放实际数据，后者存放下一个节点的地址。

  2. 性质与优势：链式结构逻辑连续、物理不一定连续，节点通常从堆上申请；相比数组，链表支持动态分配内存、任意位置插入删除效率高，且不要求内存连续。

  3. 接口实现：围绕单链表，我们依次实现了申请节点、尾插、头插、头删、尾删、指定位置前插入、指定位置后插入、指定位置删除、查找元素、打印元素以及销毁链表等核心操作。这些接口基本覆盖了单链表的日常使用场景。

  4. 实现要点：涉及头指针修改的操作（如头插、头删、尾插空链表）需要传入二级指针SLNode**pphead；删除节点后要及时free并置空，避免野指针；遍历时注意边界条件，尤其是空链表和只有一个节点的情形。

单链表是学习更复杂链式结构的基础，掌握它的增删查改逻辑后，再学习双向链表、循环链表乃至栈和队列的链式实现，都会更加得心应手。建议读者亲手把上述代码敲一遍，并尝试补充测试用例，加深对指针操作的理解。

网站建设 视觉设计 SEO优化
返回列表