单向链表的创建、插入、删除、遍历

文章目录单向链表从创建到操作全解析 1. 单向链表的基本概念 2. 实现单向链表 ️2.1 定义节点类2.2 创建链表3. 插入操作 ➕3.1 在头部插入3.2 在尾部插入3.3 在特定位置插入4. 删除操作 ❌4.1 删除头部节点4.2 删除特定值节点4.3 删除特定位置节点5. 遍历操作 5.1 简单遍历打印5.2 搜索元素6. 完整代码示例 7. 应用场景与总结 单向链表从创建到操作全解析 链表是计算机科学中最基础且重要的数据结构之一而单向链表更是许多复杂结构的基石。掌握它将为你的编程之路打下坚实基础在计算机科学中链表Linked List是一种常见的数据结构用于存储元素的集合。与数组不同链表中的元素在内存中并非连续存放而是通过指针相互连接。其中单向链表Singly Linked List是最简单的链表类型每个节点包含数据和指向下一个节点的指针。本文将深入探讨单向链表的创建、插入、删除和遍历操作并提供详细的代码示例和图表说明。1. 单向链表的基本概念 单向链表由一系列节点组成每个节点包含两部分数据域Data存储实际的数据。指针域Next存储指向下一个节点的地址。链表的第一个节点称为头节点Head最后一个节点的指针指向NULL表示链表结束。由于节点通过指针连接链表可以动态地增长或缩小非常灵活。下面是一个简单的单向链表结构示意图使用 Mermaid 图表展示HeadData: 10Next: -Data: 20Next: -Data: 30Next: NULL与数组相比链表的主要优点是动态大小和高效插入/删除但缺点是无法随机访问元素。如果你想了解更多关于数据结构的基础知识可以参考 GeeksforGeeks 的数据结构指南这是一个非常全面的资源。2. 实现单向链表 ️我们将使用 Python 来实现单向链表因为 Python 语法简洁易懂适合教学目的。其他语言如 C 或 Java的实现逻辑类似。2.1 定义节点类首先我们需要定义一个节点类表示链表中的每个元素classNode:def__init__(self,data):self.datadata# 数据域self.nextNone# 指针域初始化为 None这个类很简单data存储值next存储对下一个节点的引用。2.2 创建链表创建链表通常从初始化头节点开始。头节点是链表的起点如果链表为空头节点为None。classLinkedList:def__init__(self):self.headNone# 初始化头节点为空# 示例创建一个空链表my_listLinkedList()此时链表为空head为None。接下来我们将通过插入操作添加节点。3. 插入操作 ➕插入操作是链表的常见操作之一可以在头部、尾部或特定位置插入节点。3.1 在头部插入在头部插入节点是最简单的插入方式。新节点成为头节点并指向原来的头节点。definsert_at_head(self,data):new_nodeNode(data)# 创建新节点new_node.nextself.head# 新节点指向原头节点self.headnew_node# 更新头节点为新节点示例使用my_listLinkedList()my_list.insert_at_head(10)# 链表10 - NULLmy_list.insert_at_head(20)# 链表20 - 10 - NULL这个过程可以通过以下 Mermaid 图表可视化新节点: 20原头节点: 10HeadNULL3.2 在尾部插入在尾部插入需要遍历链表找到最后一个节点然后将其next指向新节点。definsert_at_tail(self,data):new_nodeNode(data)ifself.headisNone:# 如果链表为空self.headnew_nodeelse:currentself.headwhilecurrent.next:# 遍历到最后一个节点currentcurrent.nextcurrent.nextnew_node# 最后一个节点指向新节点示例使用my_listLinkedList()my_list.insert_at_tail(10)# 链表10 - NULLmy_list.insert_at_tail(20)# 链表10 - 20 - NULL3.3 在特定位置插入在特定位置如第 k 个节点后插入稍微复杂一些。需要先找到第 k 个节点然后调整指针。definsert_after_position(self,data,position):ifposition0:print(位置无效)returnnew_nodeNode(data)currentself.head count0whilecurrentandcountposition:currentcurrent.nextcount1ifcurrentisNone:print(位置超出链表长度)else:new_node.nextcurrent.nextcurrent.nextnew_node示例使用my_listLinkedList()my_list.insert_at_tail(10)my_list.insert_at_tail(30)my_list.insert_after_position(20,0)# 在位置0后插入20: 10 - 20 - 30 - NULL插入操作是链表的优势之一平均时间复杂度为 O(1) 对于头部插入O(n) 对于其他位置。如果你想深入了解时间复杂度的概念可以阅读 Programiz 的算法复杂度指南。4. 删除操作 ❌删除操作移除链表中的节点可以按值或按位置删除。4.1 删除头部节点删除头部节点很简单将头节点指向下一个节点即可。defdelete_at_head(self):ifself.headisNone:print(链表为空无法删除)else:self.headself.head.next# 头节点指向下一个节点示例使用my_listLinkedList()my_list.insert_at_head(10)my_list.insert_at_head(20)my_list.delete_at_head()# 删除20链表变为: 10 - NULL4.2 删除特定值节点删除特定值节点需要遍历链表找到该节点并调整指针绕过它。defdelete_by_value(self,data):ifself.headisNone:print(链表为空无法删除)returnifself.head.datadata:# 如果头节点就是要删除的节点self.headself.head.nextreturncurrentself.headwhilecurrent.next:ifcurrent.next.datadata:current.nextcurrent.next.next# 绕过要删除的节点returncurrentcurrent.nextprint(未找到值为,data,的节点)示例使用my_listLinkedList()my_list.insert_at_tail(10)my_list.insert_at_tail(20)my_list.insert_at_tail(30)my_list.delete_by_value(20)# 删除20链表变为: 10 - 30 - NULL删除过程可以通过以下 Mermaid 图表展示删除值为20的节点渲染错误:Mermaid 渲染失败: Parse error on line 10: ...-- D C -.- D // 虚线表示被移除的链接 D ----------------------^ Expecting SEMI, NEWLINE, EOF, AMP, START_LINK, LINK, LINK_ID, got NODE_STRING4.3 删除特定位置节点类似插入删除特定位置节点需要遍历到该位置的前一个节点。defdelete_by_position(self,position):ifself.headisNoneorposition0:print(无效操作)returnifposition0:self.headself.head.nextreturncurrentself.head count0whilecurrentandcountposition-1:currentcurrent.nextcount1ifcurrentisNoneorcurrent.nextisNone:print(位置超出范围)else:current.nextcurrent.next.next示例使用my_listLinkedList()my_list.insert_at_tail(10)my_list.insert_at_tail(20)my_list.insert_at_tail(30)my_list.delete_by_position(1)# 删除位置1的节点20链表变为: 10 - 30 - NULL删除操作的时间复杂度与插入类似头部删除为 O(1)其他为 O(n)。5. 遍历操作 遍历是访问链表中每个元素的过程通常用于打印、搜索或处理数据。5.1 简单遍历打印从头节点开始依次访问每个节点并打印其数据直到遇到NULL。deftraverse(self):currentself.headwhilecurrent:print(current.data,end - )currentcurrent.nextprint(NULL)示例使用my_listLinkedList()my_list.insert_at_tail(10)my_list.insert_at_tail(20)my_list.insert_at_tail(30)my_list.traverse()# 输出: 10 - 20 - 30 - NULL5.2 搜索元素遍历链表检查每个节点的数据是否匹配目标值。defsearch(self,data):currentself.head position0whilecurrent:ifcurrent.datadata:returnposition# 返回找到的位置currentcurrent.nextposition1return-1# 未找到示例使用positionmy_list.search(20)# 返回1ifposition!-1:print(元素找到位置:,position)else:print(元素未找到)遍历的时间复杂度为 O(n)因为需要访问每个节点。对于大型链表优化遍历算法可能很重要但单向链表的基本遍历无法避免 O(n) 复杂度。6. 完整代码示例 下面是一个完整的 Python 程序包含单向链表的所有操作classNode:def__init__(self,data):self.datadata self.nextNoneclassLinkedList:def__init__(self):self.headNonedefinsert_at_head(self,data):new_nodeNode(data)new_node.nextself.head self.headnew_nodedefinsert_at_tail(self,data):new_nodeNode(data)ifself.headisNone:self.headnew_nodeelse:currentself.headwhilecurrent.next:currentcurrent.nextcurrent.nextnew_nodedefinsert_after_position(self,data,position):ifposition0:print(位置无效)returnnew_nodeNode(data)currentself.head count0whilecurrentandcountposition:currentcurrent.nextcount1ifcurrentisNone:print(位置超出链表长度)else:new_node.nextcurrent.nextcurrent.nextnew_nodedefdelete_at_head(self):ifself.headisNone:print(链表为空无法删除)else:self.headself.head.nextdefdelete_by_value(self,data):ifself.headisNone:print(链表为空无法删除)returnifself.head.datadata:self.headself.head.nextreturncurrentself.headwhilecurrent.next:ifcurrent.next.datadata:current.nextcurrent.next.nextreturncurrentcurrent.nextprint(未找到值为,data,的节点)defdelete_by_position(self,position):ifself.headisNoneorposition0:print(无效操作)returnifposition0:self.headself.head.nextreturncurrentself.head count0whilecurrentandcountposition-1:currentcurrent.nextcount1ifcurrentisNoneorcurrent.nextisNone:print(位置超出范围)else:current.nextcurrent.next.nextdeftraverse(self):currentself.headwhilecurrent:print(current.data,end - )currentcurrent.nextprint(NULL)defsearch(self,data):currentself.head position0whilecurrent:ifcurrent.datadata:returnposition currentcurrent.nextposition1return-1# 演示代码if__name____main__:llLinkedList()ll.insert_at_tail(10)ll.insert_at_tail(20)ll.insert_at_tail(30)print(初始链表:)ll.traverse()ll.insert_at_head(5)print(在头部插入5后:)ll.traverse()ll.insert_after_position(15,1)print(在位置1后插入15后:)ll.traverse()ll.delete_by_value(20)print(删除值20后:)ll.traverse()posll.search(15)print(元素15的位置:,pos)输出结果初始链表: 10 - 20 - 30 - NULL 在头部插入5后: 5 - 10 - 20 - 30 - NULL 在位置1后插入15后: 5 - 10 - 15 - 20 - 30 - NULL 删除值20后: 5 - 10 - 15 - 30 - NULL 元素15的位置: 2这个完整示例展示了如何组合使用各种操作来管理链表。你可以尝试修改代码练习这些操作。7. 应用场景与总结 单向链表在许多实际场景中都有应用实现栈和队列链表可以高效地支持先进先出FIFO或后进先出LIFO操作。动态内存管理在操作系统中链表用于管理空闲内存块。浏览器历史记录许多浏览器使用链表来支持前进和后退功能。音乐播放列表播放列表中的歌曲可以组织为链表方便插入和删除。链表的优点包括动态大小、高效插入/删除但缺点是无法随机访问、需要额外内存存储指针。在选择数据结构时应根据具体需求权衡利弊。如果你想进一步学习链表和其他数据结构Wikipedia 的链表条目提供了详细的理论背景和历史信息。总之单向链表是编程和计算机科学基础中的重要组成部分。掌握它的操作不仅有助于理解更复杂的数据结构还能提高你解决实际问题的能力。快乐编码✨注意本文代码示例采用 Python 实现其他语言逻辑类似。确保在实践时根据语言特性调整语法。