大学计算机专业教师试讲课件

数据结构与算法基础-链表(LinkedList)大学计算机专业教师应聘试讲讲师：[您的姓名]日期：2025年12月自我介绍与课程导入关于我：教育背景与理念教育背景毕业于XX大学计算机科学与技术专业（硕士），主要研究方向为人工智能与大数据分析。教学理念秉持“授人以鱼不如授人以渔”的理念，注重培养逻辑思维与问题解决能力，致力于将复杂概念简单化，激发大家对计算机科学的兴趣。课程导入：从数组到链表回顾：数组的局限数组支持快速随机访问，但大小固定难以扩展，且中间插入/删除元素时效率较低。新知：链表的登场为了克服数组的缺点，我们需要一种能够动态扩展、灵活插入删除的数据结构。这就是我们今天要深入学习的核心内容——链表。回顾：数组的局限性固定大小，难以动态扩展创建时需指定大小，扩容需重新分配内存并复制元素，耗时耗资源。插入和删除元素效率低中间操作需移动后续元素，平均时间复杂度O(n)，数据量越大效率越低。内存空间必须连续需要连续的内存块，容易产生内存碎片，降低内存利用率。什么是链表？核心定义链表是一种物理存储上非连续的存储结构。数据元素的逻辑顺序通过指针链接次序实现，而非物理位置。节点组成数据域(Data)：存储数据元素本身。指针域(Next)：存储指向下一个节点的地址。主要特点逻辑上连续：节点通过指针形成有序序列。物理上离散：节点存储位置分散，无需连续内存。链表的优势动态大小，易于扩展和收缩链表大小动态可变，可按需添加或删除节点，无需预先分配固定内存，灵活性高。插入和删除元素效率高仅需改变相邻节点指针指向，无需移动其他节点，平均时间复杂度为O(1)，操作极快。内存利用率高节点可分散存储在内存任意位置，充分利用零散空间，有效避免内存碎片问题。图示：数组与链表插入操作对比，链表仅需修改指针链表的基本类型单链表(SinglyLinkedList)每个节点只有一个指针域，指向下一个节点。只能从头节点开始向后遍历。双向链表(DoublyLinkedList)每个节点有两个指针域（prev/next）。可双向遍历，操作灵活，但占用更多内存。循环链表(CircularLinkedList)尾节点指针指向头节点，形成闭环。可以从任意节点开始遍历整个链表。单链表的节点结构（Python实现）Python实现代码classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next核心属性解析val(数据域)用于存储具体数据，例如整数、字符串等。它是节点承载业务信息的核心部分。next(指针域)存储下一个节点的引用（内存地址）。默认值为None，表示该节点是链表的尾节点。单链表的基本操作：初始化Python实现定义与初始化classLinkedList:def__init__(self):self.head=None#初始化头节点为None，表示空链表核心概念解析：Head节点访问入口head是链表的头节点，是我们遍历和操作整个链表的唯一入口。

空链表状态当head属性被赋值为None时，表明当前链表中不包含任何节点，处于空链表状态。单链表的基本操作：尾部插入(Append)核心操作步骤1.初始化节点创建一个新的节点对象，存储待插入的数据。2.处理空链表情况如果头节点(head)为None，直接将新节点设为头节点。3.遍历查找尾节点从头节点开始遍历，直到找到最后一个节点(next为None)。4.执行插入操作将最后一个节点的next指针指向新创建的节点。Python代码实现defappend(self,val):new_node=ListNode(val)ifnotself.head:#空链表处理self.head=new_node;returnlast=self.headwhilelast.next:last=last.nextlast.next=new_node执行过程示意图单链表的基本操作：头部插入(Prepend)核心操作步骤创建一个新的节点(Node)并赋值将新节点的next指针指向原头节点将链表的head引用更新为这个新节点操作示意图Python代码实现defprepend(self,val):new_node=ListNode(val)new_node.next=self.head#指向原头节点self.head=new_node#更新头节点单链表的基本操作：指定位置插入核心操作步骤检查合法性：位置需在0到链表长度之间头部插入：若位置为0，直接调用头部插入逻辑定位前驱：遍历找到目标位置的前一个节点链接后继：新节点的next指向原前驱的next链接前驱：原前驱的next指向新节点，完成插入插入过程示意图Python代码实现definsert_at_index(self,val,index):ifindex==0:returnself.prepend(val)new_node,current=ListNode(val),self.headfor_inrange(index-1):current=current.nextnew_node.next,current.next=current.next,new_node单链表的基本操作：删除节点操作步骤解析空链表判断：如果链表为空(head==null)，直接返回。删除头节点：若头节点即为目标，将head指向head.next。查找前驱节点：遍历链表，找到待删除节点的前一个节点。指针重定向：将前驱节点的next指向待删节点的next。内存回收：Python中无需手动释放，GC会自动处理。Python代码实现defdelete(self,val):ifnotself.head:returnifself.head.val==val:self.head=self.head.next;returncurr=self.headwhilecurr.nextandcurr.next.val!=val:curr=curr.nextifcurr.next:curr.next=curr.next.next操作示意图单链表的基本操作：查找节点操作步骤(Algorithm)1.遍历链表：从头节点(head)开始，沿着next指针依次访问每个节点。2.比较数值：检查当前节点的val是否等于目标值。3.返回结果：找到则返回该节点；若遍历结束未找到，返回None。代码实现(Python)defsearch(self,val):current=self.headwhilecurrent:

ifcurrent.val==val:

returncurrent#找到节点current=current.next

returnNone#未找到单链表的基本操作：打印链表核心逻辑与步骤初始化指针指向头节点(head)开始遍历循环访问每个节点，依次打印节点的val值使用特定格式(如->)连接值，末尾输出None执行示例链表结构：1->3->5打印结果：1->3->5->NonePython代码实现defprint_list(self):current_node=self.headwhilecurrent_node:print(current_node.val,end="->")current_node=current_node.nextprint("None")#表示链表结束综合实例演示Python核心实现代码#1.初始化与尾部插入llist=LinkedList();llist.append(1);llist.append(3)print("尾部插入后:");llist.print_list()#2.头部插入与指定位置插入llist.prepend(0);llist.insert_at_index(2,2)print("插入后:");llist.print_list()#3.查找与删除操作found=llist.search(3);print(f"找到:{found.val}")llist.delete(1);print("删除后:");llist.print_list()执行流程与输出结果尾部插入(Append)输出:1->3->5->None头部与指定位置插入(Prepend/Insert)输出:0->1->2->3->5->None查找节点(Search)输出:找到节点:3删除节点(Delete)输出:0->2->3->5->None单链表操作的时间复杂度分析操作类型单链表(平均/最坏)数组(平均/最坏)随机访问(Access)O(n)O(1)头部插入/删除O(1)O(n)尾部插入/删除O(n)(已知尾指针则O(1))O(1)中间插入/删除O(n)O(n)核心结论与场景建议链表在需要频繁进行插入和删除操作（尤其是在头部）的场景下效率更高；而数组在需要频繁随机访问元素的场景下表现更优。课堂小结链表的核心概念链表是由节点组成的线性结构，每个节点包含数据域和指针域。通过指针链接形成序列，其物理存储在内存中是不连续的。单链表的基本操作掌握了初始化、尾部/头部/指定位置插入、删除、查找和打印等核心操作。理解了通过指针遍历和修改节点指向的实现逻辑。与数组的对比分析链表适合频繁的插入和删除操作，效率较高；而数组适合频繁的随机访问。两者在时间复杂度和空间利用率上各有优劣。关键设计思想用“指针”的灵活性换取了“连续内存”的限制，这是一种重要的线性数据结构，为后续学