当前位置： 首页 > ops >正文

《数据结构笔记三》：单链表（创建、插入、遍历、删除、释放内存等核心操作）

ops 2025/8/6 3:17:50

 不带头节点的单链表：（不带表头）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//定义一个链表节点结构体
typedef struct Node
{/* data */int   data;           //表示节点数据域struct Node *next;    //表示节点指针域
}Node;//链表类型 （头指针）
typedef Node  *LinkedList;void initList(LinkedList  *list)
{*list = NULL;
}//插入新节点  头插法
void insertAtHead(LinkedList *list  int value)
{Node *newnode  = (Node*) malloc (sizeof(Node)); //为新节点开辟堆内存空间if(!newnode)//判断是否存在新节点{perror("内存分配失败！");exit(EXIT_FAILURE);}newNode -> data = value;newNode -> next = *list;    //新节点指向原头节点*list = Newnode;           //头指针指向新节点 
}//遍历链表
void traverseList(LinkedList list)
{Node *current = list;printf("链表元素：")；while (current  !=  NULL){/* code */printf("%d ->",current -> data);current = currenr -> next;}printf("NULL\n");
}//删除节点
//删除第一个值为vulue的节点
void deleteNode(LinkedList *list , int value)
{if ( *list= NULL)  //判断是否为空链表{/* code */return ;}Node *current  = *list;Node *prev =  NULL;//查找待删除节点while (current != NULL && current->data != value){/* code */prev = current;current = current->next;}if(current = NULL)  return; //空值表示未查找到if (prev = NULL){*list = current->next;}else{prev->next = current->next;}free(current); //释放节点内存
}//释放内存
void freeList(Linkedlist *list)
{Node *current = *list;while (current != NULL){Node *temp = current;current = current->next;free(temp);    }*list = NULL; // 头指针置空
}int main() {// 测试不带表头链表LinkedList list1;initList(&list1);insertAtHead(&list1, 10);insertAtHead(&list1, 20);traverseList(list1); // 输出: 20 -> 10 -> NULLdeleteNode(&list1, 10);traverseList(list1); // 输出: 20 -> NULLfreeList(&list1);return 0;
}

 带头节点的单链表：（带表头）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//定义一个链表节点结构体
typedef struct Node {int data;struct Node *next;
} Node;// 链表类型（固定头节点）
typedef struct {Node *head;  // 头节点（不存储数据 NULL）
} LinkedList;//创建链表，初始化
void initList(LinkedList *list) {list->head = (Node *)malloc(sizeof(Node)); // 分配头节点if (!list->head) {perror("内存分配失败");exit(EXIT_FAILURE);}list->head->next = NULL; // 头节点的next初始化为NULL
}//插入节点（头插法）
void insertAtHead(LinkedList *list, int value) {Node *newNode = (Node *)malloc(sizeof(Node));if (!newNode) {perror("内存分配失败");exit(EXIT_FAILURE);}newNode->data = value;newNode->next = list->head->next; // 新节点指向原第一个节点list->head->next = newNode;       // 头节点指向新节点
}//遍历节点
void traverseList(LinkedList *list) {Node *current = list->head->next; // 跳过头节点printf("链表元素: ");while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}//删除节点
void deleteNode(LinkedList *list, int value) {Node *prev = list->head;Node *current = prev->next;while (current != NULL && current->data != value) {prev = current;current = current->next;}if (current != NULL) {prev->next = current->next;free(current);}
}//释放内存
void freeList(LinkedList *list) {Node *current = list->head->next;while (current != NULL) {Node *temp = current;current = current->next;free(temp);}free(list->head);     // 释放头节点list->head = NULL;
}int main()
{// 测试带表头链表LinkedList list2;initList(&list2);insertAtHead(&list2, 100);insertAtHead(&list2, 200);traverseList(&list2); // 输出: 200 -> 100 -> NULLdeleteNode(&list2, 200);traverseList(&list2); // 输出: 100 -> NULLfreeList(&list2);return 0;}

插入操作，除了头插法，还有：中间插入、任意一位置插入（索引插入），尾插法。 

1. 插入操作的分类

插入方式适用场景时间复杂度
头插法快速在链表头部插入O(1)
尾插法在链表尾部追加数据O(n)
中间插入在指定值或位置后插入O(n)（查找时间）
按索引插入类似数组操作，按位置插入O(n)

2. 带表头 vs 不带表头的差异

操作不带表头链表带表头链表
头插法需直接修改外部头指针操作头节点的 next，无需修改外部指针
尾插法需要处理空链表（头指针为NULL）直接从 head->next 开始遍历
按索引插入插入位置0需特殊处理头指针统一从头节点开始计算位置
错误处理需检查头指针是否为NULL头节点始终存在，无需额外判空

3. 边界条件处理

  • 空链表插入：

    • 不带表头：头指针为NULL时，尾插法直接赋值。

    • 带表头：头节点的 next 为NULL时，尾插法插入到 head->next。

  • 越界插入：

    • 按索引插入时，若 pos 超过链表长度，需提示错误并释放未使用的节点内存。

  • 重复值处理：

    • 中间插入时，若有多个相同值的节点，默认操作第一个匹配的节点。

4. 内存管理

  • 内存分配失败：统一检查 malloc 返回值，避免程序崩溃。

  • 未使用的节点：在插入失败时（如越界），需释放已分配的节点内存。

总结

  • 插入灵活性：单链表的插入操作灵活，但需注意指针修改顺序（先连接新节点，再断开旧链接）。

  • 代码鲁棒性：始终处理边界条件（如空链表、越界位置）和内存分配失败。

  • 性能权衡：头插法最快（O(1)），尾插法和中间插入需要遍历（O(n)）。

深度解析

1. 带表头 vs 不带表头

特性不带表头链表带表头链表
头指针指向第一个数据节点指向头节点（不存储数据）
插入/删除头节点需要特殊处理头指针统一操作，无需修改头指针
代码简洁性需要较多条件判断代码更统一，减少边界条件
内存占用节省一个头节点内存多一个头节点的内存占用
适用场景简单场景或内存敏感环境需要频繁操作头节点的情况

2. 关键操作分析

  • 插入操作：

    • 不带表头链表插入头节点时，必须修改外部头指针（需传递二级指针）。

    • 带表头链表插入头节点时，只需修改头节点的 next 指针，外部头指针不变。

  • 删除操作：

    • 不带表头链表删除头节点时，需更新头指针，否则会访问已释放的内存。

    • 带表头链表删除头节点时，只需处理头节点的 next 指针，无需关心外部指针。

  • 内存管理：

    • 释放链表时，带表头链表需额外释放头节点。

    • 不带表头链表需确保头指针被正确置空，避免野指针。

      总结

    • 不带表头链表：适合简单场景，但需处理头指针的特殊情况。

    • 带表头链表：代码更简洁，适合需要频繁操作头节点的场景。

    • 通过对比实现，可以深入理解链表的核心逻辑和指针操作的精髓。

    • 共同注意点：确保内存正确释放，避免内存泄漏；操作指针时注意边界条件。

http://www.xdnf.cn/news/8327.html

相关文章：

  • 教育行业课件共享难题：大文件分发效率优化方案
  • 广东省省考备考（第十八天5.23）—言语：语句排序题（听课后强化训练）
  • 对比关系型数据库与NoSQL数据库
  • nlf 2025 部署笔记
  • 利用 Python 爬虫获取唯品会 VIP 商品详情：实战指南
  • microsoft中word如何添加个人签名
  • 时序数据库 TDengine × Superset：一键构建你的可视化分析系统
  • PyQt学习系列10-性能优化与调试技巧
  • Java对象内存分配优化教学
  • 端到端大语言模型微调技术 Demo 全流程详解（附完整模块说明）
  • C语言数据结构
  • 【LaTex】基础语法入门
  • 使用Python在PyCharm中进行交通工程数据分析的完整流程，包括数据清洗、挖掘、关联、可视化和应用整合等各个阶段
  • RK3399 Android13设备插拔无线鼠标键盘设备出现APP或系统界面刷新现象
  • 详解osgb的顶点，纹理，索引，UV读取与存储
  • 注册并创建一个微信小程序
  • 第三章 软件工程模型和方法
  • 免费在线AI聊天工具
  • C# 按行写入txt大量数据
  • AI与.NET技术实操系列（八）：使用Catalyst进行自然语言处理
  • 极大似然估计
  • 2025电工杯：光伏电站发电功率日前预测问题 第二问 基于历史功率的光伏电站日前发电功率预测模型构建思路
  • 用 3D 可视化颠覆你的 JSON 数据体验
  • 持续更新 ，GPT-4o 风格提示词案例大全！附使用方式
  • Android 网络全栈攻略（五）—— 从 OkHttp 拦截器来看 HTTP 协议二
  • C++ vector 深度解析：从原理到实战的全方位指南
  • Flask 会话管理：从原理到实战，深度解析 session 机制
  • leetcode hot100：十一、解题思路大全：回溯（全排列、子集、电话号码的字母组合、组合总和、括号生成、单词搜索、分割回文串、N皇后）
  • C#对象初始化语句：优雅创建对象的黑科技
  • CSS3动画