数据结构：单向链表

一. 什么是单向链表单向链表是一种线性数据结构由一系列节点组成。每个节点包含两部分数据域data存储实际的数据。指针域next存储下一个节点的地址。与数组不同链表中的节点在内存中不要求连续存储而是通过指针逐个串联起来。因此链表的插入和删除操作不需要移动大量元素效率较高但随机访问某个节点则需要从头遍历时间复杂度为 O(n)2. 单向链表的结构head链表的头指针指向第一个节点。每个节点的 next 指向下一个节点。最后一个节点的next为null链表的最后一个节点的 next指向 null表示链表结束3. 单向链表带头结点的基本操作1.创建、2.增、3.删、4.改、5.查、6.销毁(采用多文件makefile)代码示例1.先由结构体定义一个链表类型链表类型结构体内可以存放任何数据类型的数据域以及存放一个指针域指向下一个节点2.创建空白链表开辟一个head的空间头节点指向NULL注意创建成功此时运行什么都不会显示3.链表增加节点1.头插法插入数据首先判断是否成功创建在定义一个新的节点用malloc在堆区上开辟空间判断是否成功开辟新节点先指向第一个有效节点表头在指向新的节点此时成功插入新节点接入传输的数据2.尾插法判断是否成功创建链表开辟新的节点空间新节点存指向下一个的地址为null定义一个链表类型的指针存储头节点让该指针走到末尾让p的下一个节点指向新节点此时null被覆盖新节点指针成为尾指针依次存放数据可以将打印链表的数据封装为一个函数4.删除链表节点判空函数判断头节点是否创建成功如果创建成功判断头节点的下一个有效节点是否不为空如果是真则返回1不是则返回01.头删法判断是否成功创建和判断是否存在有效节点如果是定义一个链表类型指针从存放头节点下一个节点。头节点的下一个节点指向待删节点的下一个节点释放p所指向的地址代表删除此时p为野指针将p指针赋值为null2.尾删法判断是否成功创建和判断是否存在有效节点如果是定义一个链表类型指针从存放头节点下一个节点此时注意这两个删除每次调用只能删除一个4.查找对应的数据首先还是判断是否创建成功定义一个链表类型指针存放头节点的前一个有效节点因为头节点不存放数据所以从下一个开始遍历链表找到输入的与链表内的数据匹配则返回该地址没有则返回null5.链表修改判断头节点与调用判空函数返回值如果两个同时返回结果表示真则返回空定义一个链表类型指针指向头的下一个有效节点为p循环查找链表是否存在有一个节点数据想要修改的值相等如果有则将当前节点数据修改成新的如果循环结束没有找到则返回空代表不存在这个数6.链表销毁首先还是判断是否创建成功链表销毁需要被调修改主调函数所以需要传递链表头地址的地址二级指针定义一个链表类型指针指向头为p以及链表类型指针q循环遍历q负责记录p的下一个节点p负责释放当前节点再将q指向下一个节点位置给p移动最后将头指针清空防止变成悬空指针二. 单向链表的优缺点1.优点插入和删除操作效率高不需要移动大量元素。内存利用率高按需分配节点空间。适合实现栈、队列等抽象数据结构。2.缺点只能单向遍历无法从当前节点找到前驱节点不能反向遍历不支持随机访问查找第 n 个节点必须从头遍历时间复杂度 O (n)尾插、尾删、指定节点删除效率低 O (n)需要遍历寻找前驱链断裂后后续节点丢失容易内存泄漏