单链表是一种线性表数据结构但它不像数组那样在内存中连续存储而是由一系列节点组成每个节点通过指针引用连接到下一个节点形成链式结构。1. 单链表的核心结构每个节点包含两个部分数据域存储结点的实际数据如数字、字符串等等。指针域存储指向下一个节点的引用地址最后一个节点的指针域空表示链表结束。单链表还有一个头节点Head用于指向单链表的第一个有效节点2. 直观理解可以把单链表想象成一串珍珠每颗珍珠 一个节点包含珍珠本身的颜色 / 大小 连接下一颗珍珠的线。线 指针域指向另一颗珍珠。第一颗珍珠的线头 头节点。最后一颗珍珠没有线 指针域为null。3. 代码示例以下是单链表的基础实现包含节点定义、链表初始化、添加节点、遍历链表//数据结构等于结构定义结构操作 //链表是由一串节点串联在一起的链表的每个节点存储两个信息 //第一个信息数据 第二个信息下一个节点的地址 //内存内部就是信息存储在我们的内存空间中 //程序内部就是通过什么样的信息然后去操作相关的结构 //操作链表依靠的是程序内部的信息 //有头链表的头节点叫做虚拟头节点 #include stdio.h #include stdlib.h #include time.h //#define DL 3 // 定义数字显示宽度为3个字符 //#define DIGIT_LEN(n) % #n d // 拼接格式化字符串的宏 //结构定义 typedef struct Node { int data; // 节点存储的数据整数 struct Node* next; // 指向下一个节点的指针 } Node; // 给结构体起别名Node简化后续使用 //结构操作 //初始化 Node* getNewNode(int val) {//创建新节点 Node* p (Node*)malloc(sizeof(Node));//分配内存申请一块和Node大小相同的内存空间 p-data val;//初始化节点数据把传入的val赋值给data p-next NULL;//初始化指针新节点默认不指向任何节点next为NULL return p;//返回新节点的地址 } ////链表结构的插入操作,无头链表 //Node* insert(Node* head, int pos, int val) { // // 情况1插入到链表头部pos0 // if (pos 0) { // Node* p getNewNode(val); // 创建新节点 // p-next head; // 新节点的next指向原来的头节点 // return p; // 新节点成为新的头节点 // } // // 情况2插入到链表中间/尾部pos0 // Node* p head; // 从头部开始遍历 // // 找到插入位置的前一个节点循环结束后p就是前一个节点 // for (int i 1; i pos - 1; i) p p-next; // Node* node getNewNode(val); // 创建新节点 // node-next p-next; // 新节点的next指向p原来的下一个节点 // p-next node; // p的next指向新节点完成插入 // return head; // 头节点不变返回原头节点 //} //有头链表 Node* insert(Node* head, int pos, int val) { //创建虚拟头节点 待插入节点 Node new_head, * p new_head, * node getNewNode(val); //虚拟头节点的next指向原链表的头节点把原链表“挂”到虚拟头后 new_head.next head; //遍历到插入位置的前一个节点p最终停在目标前驱节点 for (int i 0; i pos; i)p p-next; //插入新节点经典的“先连后断” node-next p-next; // 新节点的next指向p原来的下一个节点 p-next node; // p的next指向新节点 //返回新链表的头节点虚拟头的next可能是原头/新节点 return new_head.next; } //销毁链表 void clear(Node* head) { if (head NULL)return; for (Node* p head, *q; p; p q) {//循环遍历链表中的每一个节点 q p-next; free(p); } return; } //输出链表 void output_linklist(Node* head, int flag 0) { // 计算链表长度和之前一致 int n 0; for (Node* p head; p; p p-next) n 1; // 打印位置索引用宏DIGIT_LEN(DL)替代硬编码的%3d for (int i 0; i n; i) { printf(%3d, i); printf( ); } printf(\n); // 打印节点值同样用宏格式化 for (Node* p head; p; p p-next) { printf(%3d, p-data); printf(-); } printf(\n); // flag0默认场景插入后输出多打印两行空行 // flag1查找场景不额外换行避免格式乱 if (flag 0)printf(\n\n); return; } int find(Node* head, int val) { Node* p head; // 从链表头开始遍历 int n 0; // 记录当前节点的位置索引 while (p) { // 遍历到链表尾部pNULL停止 // 找到目标值 if (p-data val) { // 打印链表flag1不额外换行 output_linklist(head, 1); // 计算需要打印多少个空格让^和|精准指向目标节点 // DL2每个位置占DL数字宽度2空格个字符 int len n * 5 2; for (int i 0; i len; i)printf( ); printf(^\n); // 指向目标节点的顶部 for (int i 0; i len; i)printf( ); printf(|\n); // 指向目标节点的竖线 return 1; // 找到返回1 } n 1; // 位置索引1 p p-next;// 遍历下一个节点 } return 0; // 没找到返回0 } int main() { srand(time(0)); // 设置随机数种子让每次运行的随机数不同 #define MAX_OP 7 // 定义常量插入操作的次数7次 Node* head NULL; // 初始化链表头节点为NULL空链表 // 循环7次每次随机插入一个值 for (int i 0; i MAX_OP; i) { // 随机生成插入位置0 ~ i因为第i次插入时链表已有i个节点 int pos rand() % (i 1); // 随机生成插入的值0 ~ 99 int val rand() % 100; // 打印本次插入的信息 printf(insert %d at %d to linklist\n, val, pos); // 执行插入操作更新头节点 head insert(head, pos, val); // 打印插入后的链表 output_linklist(head); } int val; while (scanf_s(%d, val)) { if (!find(head, val)) { printf(not found\n); } } clear(head); // 销毁链表释放内存 return 0; // 程序正常结束 }4. 单链表的核心特点优点内存灵活节点可以分散存储在内存中无需连续空间充分利用内存。插入 / 删除高效如果已知要操作的节点位置只需修改指针时间复杂度 O(1)无需像数组那样移动元素。缺点访问效率低无法随机访问如直接找第 5 个节点必须从头部开始遍历时间复杂度 O(n)。额外空间开销每个节点需要额外存储指针域增加了内存消耗。5. 单链表的常见操作除了示例中的append尾插和traverse遍历还有头插在链表头部添加节点修改头节点指针。指定位置插入 / 删除先遍历到目标位置的前一个节点再修改指针。查找节点遍历链表对比数据域找到目标节点。总结单链表由节点组成每个节点包含数据域和指针域通过指针连接成链式结构最后一个节点指针为null。核心优势是插入 / 删除高效O(1)、内存灵活核心劣势是无法随机访问访问效率为O(n)。与数组互补数组适合频繁读取、少量修改单链表适合频繁插入 / 删除、少量读取。