Python - 链表浅析

Python - 链表浅析本篇用Python代码模拟链表1. 链表介绍概述链表属于数据结构之线性结构的一种每个节点都只能有1个前驱和1个后继节点。作用用于优化顺序表的弊端如果没有足够的连续的内存空间会导致扩容失败。链表扩容时有地儿就行连不连续无所谓。组成由节点组成其中节点由以下两部分组成元素域 (数值域)存储数据。链接域 (地址域)存储下一个节点的地址。分类根据节点类型不同链表主要分为单向链表节点由1个数值域和1个地址域组成前边节点的地址域存储的是后续节点的地址最后1个节点的地址域为None。单向循环链表尾节点的地址域指向头节点。双向链表节点包含前驱指针和后继指针。双向循环链表双向链表的头尾相连。2. 自定义代码模拟链表 - 思路分析NodeObj类 (节点类)item: 数值域 (元素域)next: 地址域 (链接域)LinkedList类 (链表类)属性:head: 表示头结点指向第1个节点。行为 (方法):is_empty(): 判断链表是否为空length(): 获取链表长度travel(): 遍历整个链表add(item): 链表头部添加元素append(item): 链表尾部添加元素insert(pos, item): 指定位置添加元素remove(item): 删除节点search(item): 查找节点是否存在测试: 在main模块中进行功能验证。3. 代码实现# 1. 自定义 NodeObj 类表示节点类classNodeObj:# 初始化属性def__init__(self,item):self.itemitem# 元素域 (数值域)self.nextNone# 链接域 (地址域)# 2. 自定义 LinkedList 类表示链表classLinkedList:# 1. 初始化属性def__init__(self,nodeNone):self.headnode# 链表的头结点指向第1个节点# 2. is_empty(self) 链表是否为空defis_empty(self):returnself.headisNone# 3. length(self) 链表长度deflength(self):count0curself.headwhilecurisnotNone:count1curcur.nextreturncount# 4. travel(self) 遍历整个链表deftravel(self):curself.head items[]whilecurisnotNone:items.append(str(cur.item))curcur.nextprint( - .join(items))# 5. add(self, item) 链表头部添加元素defadd(self,item):头部插入时间复杂度 O(1)nodeNodeObj(item)node.nextself.head self.headnode# 6. append(self, item) 链表尾部添加元素defappend(self,item):尾部追加时间复杂度 O(n)nodeNodeObj(item)ifself.is_empty():self.headnodeelse:curself.headwhilecur.nextisnotNone:curcur.nextcur.nextnode# 7. insert(self, pos, item) 指定位置添加元素definsert(self,pos,item): :param pos: 从0开始索引 :param item: 插入的数据 ifpos0:self.add(item)elifpos(self.length()-1):self.append(item)else:nodeNodeObj(item)count0preself.head# 移动到 pos 位置的前一个节点whilecount(pos-1):count1prepre.next# 执行插入node.nextpre.nextpre.nextnode# 8. remove(self, item) 删除节点defremove(self,item):curself.head preNonewhilecurisnotNone:ifcur.itemitem:# 判断是否是头结点ifpreisNone:self.headcur.nextelse:pre.nextcur.nextreturnTrue# 删除成功else:precur curcur.nextreturnFalse# 未找到# 9. search(self, item) 查找节点是否存在defsearch(self,item):curself.headwhilecurisnotNone:ifcur.itemitem:returnTruecurcur.nextreturnFalse# 3. 在 main 中测试if__name____main__:print(--- 测试节点类 ---)# 3.1 测试节点类node1NodeObj(10)# 3.2 打印当前节点的 元素域 (数值域) 和 链接域 (地址域)print(f元素域 (数值域):{node1.item})# 10print(f链接域 (地址域):{node1.next})# Noneprint(fnode1 对象:{node1})# 地址值print(fnode1 的类型:{type(node1)})print(-*20)print(\n--- 测试链表类 ---)# 3.2 测试链表类my_linkedlistLinkedList(node1)print(f头结点为{my_linkedlist.head})print(f头结点的元素域{my_linkedlist.head.item})# 10print(f头结点的地址域{my_linkedlist.head.next})# Noneprint(\n--- 功能测试 ---)# 测试是否为空print(f链表是否为空{my_linkedlist.is_empty()})print(f链表长度{my_linkedlist.length()})# 遍历print(当前链表内容,end)my_linkedlist.travel()# 头部添加my_linkedlist.add(20)print(头部添加 20 后,end)my_linkedlist.travel()# 尾部添加my_linkedlist.append(30)print(尾部添加 30 后,end)my_linkedlist.travel()# 指定位置插入my_linkedlist.insert(1,25)print(位置 1 插入 25 后,end)my_linkedlist.travel()# 查找print(f查找 25 是否存在{my_linkedlist.search(25)})print(f查找 100 是否存在{my_linkedlist.search(100)})# 删除my_linkedlist.remove(25)print(删除 25 后,end)my_linkedlist.travel()print(f最终链表长度{my_linkedlist.length()})