【408数据结构与算法】—单链表的基本操作（六）

【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 指向新结点