2.2链表学案20232024学年浙教版信息技术选择性必修1

在刚开始学习选修课程的时候，大家一定最头痛的是链表这个章节吧，尤其很多同学之前接触的是VB，在Python中这块内容变化多端，考试中试题类型也很丰富，那下面我们就从最基础的链表基本知识学起，深入浅出地讲解下去，大家夯实基础，以不变应万变！链表的概念：链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。节点结构：data(数据域)：用来保存实际需要处理的数据元素。next(指针域)：用来保存该节点相邻节点的存储地址。链表的存储方式链表内存存放方式：链表的种类：链表的特性链表的时间复杂度：要访问由n个节点组成的链表中的第x个节点，时间复杂度为O（x）链表的基本操作：案例List=[[“煎饺”，1]，[“馄饨”，3]，[“面饽饽”，1]，[“生煎包”，4]，[“麦糊烧”，2]]链表元素的全访问：head=0p=headWhilep!=1printList[p][0]p=List[p][1]链表元素的条件访问：head=0p=headWhilep!=1iflen(List[p][0])==2printList[p][0]p=List[p][1]链表头节点的删除：head=List[head][1]链表尾节点的删除：head=0q=p=headWhileList[p][1]!=1q=pp=List[p][1]List[q][1]=1链表中间指定节点的删除：ⅰ指定删除节点的索引mhead=0q=p=headWhilep!=mq=pp=List[p][1]List[q][1]=List[m][1]ⅱ指定删除节点的数据域（生煎包）head=0q=p=headWhileList[p][0]!=“生煎包”q=pp=List[p][1]List[q][1]=List[p][1]链表节点的插入（newdata=“酱香饼”）链表头节点的插入：List.append([“酱香饼”，head])head=len(List)1链表尾节点的插入：head=0q=p=headWhilep!=1q=pp=List[p][1]List.append([“酱香饼”，1])List[q][1]=len(List)1链表指定索引前位置插入（m）head=0q=p=headWhilep!=mq=pp=List[p][1]List.append([“酱香饼”，m])List[q][1]=len(List)1链表指定索引后位置插入（m）head=0p=headWhilep!=mp=List[p][1]List.append([“酱香饼”，List[m][1]])List[p][1]=len(List)1链表节点的替换（replacedata=“酱香饼”）链表头节点的替换List.append([“酱香饼”，List[head][1]])head=len(List)1链表尾节点的替换head=0q=p=headWhileList[p][1]!=1q=pp=List[p][1]List.append([“酱香饼”，1])List[q][1]=len(list)1链表指定索引m节点的替换head=0q=p=headWhilep!=mq=pp=List[p][1]List.append([“酱香饼”，List[m][1])List[q][1]=len(list)1链表指定数据域（生煎包）节点的替换head=0q=p=headWhileList[p][0]!=