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

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

article 2025/9/1 13:59:49

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

#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.lryc.cn/news/2384890.html

相关文章：

  • 光伏行业如何利用SD-WAN优化分布式网络：替代MPLS、VPN、4G/5G的网络架构升级与云安全方案全解析
  • 2025电工杯数学建模A题思路数模AI提示词工程
  • LLM | 论文精读 | NAACL 2025 | Clarify When Necessary：教语言模型何时该“问一句”再答！
  • 嵌入式鸿蒙openharmony应用开发环境搭建与工程创建实现
  • MDK的编译过程及文件类型全解
  • socc 19 echash论文部分解读
  • Linux Shell编程(八)
  • AI筑基，新质跃升｜英码科技亮相华为广东新质生产力创新峰会，发布大模型一体机新品，助力产业智能化转型
  • 手机打电话时由对方DTMF响应切换多级IVR语音菜单（话术脚本与实战）
  • 面试题——JDBC|Maven|Spring的IOC思想|DI思想|SpringMVC
  • DETR3D- 3D Object Detection from Multi-view Images via 3D-to-2D Queries
  • SpringBoot3整合WebSocket
  • 鸿蒙进阶——驱动框架UHDF 机制核心源码解读（一）
  • 电子电路：能认为电抗也是在做功吗？
  • DEEPSEEK + 其他工具的玩法
  • Idea 配合 devtools 依赖 实现热部署
  • 远程访问家里的路由器：异地访问内网设备或指定端口网址
  • 根据参数量，如何推断需要多少数据才能够使模型得到充分训练？
  • PycharmFlask 学习心得：路由（3-4）
  • 从逻辑学视角严谨证明数据加密的数学方法与实践
  • 敦煌网测评从环境搭建到风控应对，精细化运营打造安全测评体系
  • 现代化SQLite的构建之旅——解析开源项目Limbo
  • 本地分支git push 报错 fatal: The current branch XXXX has no upstream branch.
  • 人工智能100问☞第27问：神经网络与贝叶斯网络的关系？
  • Python----循环神经网络（WordEmbedding词嵌入）
  • ElasticSearch各种查询语法示例
  • CUDA的设备,流处理器(Streams)，核，线程块（threadblock），线程，网格（‌gridDim），块（block）和多gpu设备同步数据概念
  • PyTorch的dataloader制作自定义数据集
  • LeetCode 1340. 跳跃游戏 V（困难）
  • x-cmd install | cargo-selector：优雅管理 Rust 项目二进制与示例，开发体验升级