【408数据结构与算法】—单链表的基本操作（六）
一、单链表—取第i个元素值
算法的思路：分别取出第3个元素和第i个元素的内容。从链表的头指针出发，顺着链域next逐个结点往下搜索，直到搜索到第i个结点为止，因此，链表不是随机存取结构
算法的思路：
- 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初始值p=L->next
- j做计数器，累计当前扫描过的节点数，j的初始值为1
- 当p指向扫描到的下一结点时，计数器j加1
- 当j==i时，p所指的结点就是要找的第i个结点
二、单链表—按值查找
按值查找—根据指定数据获取该数据所在的位置（地址）例如：分别查找30和值为15的元素
算法步骤：
- 从第一个结点起，依次和e相比较
- 如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址
- 如果查遍整个链表都没有找到其值和e相等的元素则返回0或null
算法描述
算法设计—根据指定数据获取该数据位置序号
三、单链表—插入
插入—在第i个结点前插入值为e的新结点
算法步骤：
- 首先找到ai-1的存储位置p
- 生成一个数据域为e的新结点s
- 插入新结点：新结点的指针域指向结点ai;结点ai-1的指针域指向新结点
- 📢思考：步骤1和步骤2能互换位置吗？先执行2后执行1，可以吗？
📢不可以，会丢失ai的地址
算法描述：
四、单链表—删除
- 删除第i个结点
- 算法步骤：
- 首先找到ai-1的存储位置p,保存要删除的a的值
- 令p->next指向ai+1
- 释放结点ai的空间
算法描述
五、单链表的查找时间效率分析
- 查找：因线性表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)
- 插入和删除：因线性表不需要移动元素，只要修改指针，一般情况下时间复杂度为O（1）； 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)
六、单链表的建立
1️⃣ 建立单链表—头插法：元素插入在链表头部，也叫前插法
算法思路：
- 从一个空表开始，重复读入数据
- 生成新结点，将读入数据存放到新结点的数据域中
- 从最后一个结点开始，依次将各结点插入到链表的前端
例如：建立链表L（a,b,c,d,e）
2️⃣ 建立单链表—尾插法：元素插入在链表尾部，也叫后插法
- 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
- 初始时，r同L均指向头结点，每读一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点
