03_单链表的实现

2、链表的功能定义方法说明size()返回链表中元素个数is_empty()判断链表是否为空insert(index, item)在指定位置插入元素append(item)在末尾插入元素remove(index)删除指定位置的元素set(index, item)修改指定位置的元素get(index)获取指定位置的元素find(item)查找链表中某个元素的位置__str__()返回字符串 [元素1, 元素2, 元素3]__iter__()返回迭代器对象在这里插入代码片# 定义节点fromtypingimportAnyfromenvs.nlp.Lib.unittestimportresultclassNode:def__init__(self,element,nextNone):self.elementelement# 元素self.nextnext# 指针classMyLinkedList:def__init__(self):self.__headNoneself.__size0# 返回链表中元素个数property# 有它外面访问size可以是 xx.size,没有它外部访问size必须是 xx.size()defsize(self):returnself.__size# 判断链表是否为空defisEmpty(self):returnself.__size0# 在指定位置插入元素definsert(self,index,element):# 第一步检查index的合法性合理的范围[0,self.__size]ifindex0orindexself.__size:raiseIndexError(f{index}越界了)# 第二步: 创建新结点new_nodeNode(element)# 创建新结点此时新节点的next是Noneifindex0:# 如果插入位置是0需要单独谈论new_node.nextself.__head self.__headnew_nodeelse:# 第三步根据index导航到对应的节点nodeself.__head# 整个节点foriinrange(index-1):nodenode.next# 经过这个循环node最后指向 index 的前一个元素# 第四步让新结点的next指向原来[index]位置的结点[index]前一个结点的next指向新结点new_node.nextnode.nextnode.nextnew_node# 第五步元素个数增加self.__size1# 在末尾插入元素defappend(self,element):# 第一步遍历到尾结点nodeself.__head# 第二步创建新结点new_nodeNode(element)# 修复增加空链表的防御性判断ifself.__headisNone:self.__headnew_nodeelse:whilenode.nextisnotNone:nodenode.next# 出了循环,node.next None说明是尾结点# 第三步尾部追加元素node.nextnew_node# 第四步个数1self.__size1# 删除指定位置的元素defremove(self,index):# 第一步检查index的合法性合理的删除范围[0,self.__size-1],检查index是否在已有元素的下标范围self.check_exsit_index(index)ifindex0:# 头结点self.__headself.__head.nextelse:# 第二步根据index导航到[index-1]的结点nodeself.find_element(index-1)# 经过这个循环node最后指向的是index前一个结点# 第三步要记录[index]位置的结点remove_nodenode.next# 第四步让node.next指向node的next.next结点# remove_node 是[index]位置的结点# node 是[index-1]位置的结点# remove_node的next是[index1]位置的结点node.nextnode.next.next# 第五步[index]位置的结点的next和element都应该置空remove_node.elementNoneremove_node.nextNone# 第六步个数-1self.__size-1# 合法检查index是否在已有元素下标的合法范围内defcheck_exsit_index(self,index):# 是否index在已有元素的下标范围ifindex0orindexself.__size:raiseIndexError(f{index}越界了)# 修改指定位置的元素defset(self,index,element):# 第一步检查index是否在已有元素的下标范围内self.check_exsit_index(index)# 第二步 导航到index的位置nodeself.find_element(index)# 循环出来后node最后指向index位置的结点# 第三步替换[index]位置结点的元素node.elementelement# 查找元素deffind_element(self,index)-Any:nodeself.__headforiinrange(index):nodenode.nextreturnnode# 获取指定位置的元素defget(self,index):self.check_exsit_index(index)# 第二步 导航到index的位置nodeself.find_element(index)returnnode.element# 查找链表中某个元素的位置deffind(self,element):index-1nodeself.__headwhilenodeisnotNone:indexindex1ifnode.elementelement:returnindex nodenode.nextreturn-1# _str__ 是一个非常实用的魔术方法Magic Method专门用来自定义对象的字符串表示形式。# 有它可以打印出元素的值否则只能打印出地址值def__str__(self):result# 遍历nodeself.__headwhilenodeisnotNone:resultstr(node.element)result-ifnode.nextelsenodenode.nextreturnresultdef__iter__(self):nodeself.__headwhilenodeisnotNone:yieldnode.element nodenode.next# 测试if__name____main__:linkMyLinkedList()print(最初的size:,link.size)print(是否为空,link.isEmpty())link.insert(0,hello)link.insert(1,world)link.insert(2,!)link.insert(3,Life)link.insert(4,is)link.insert(5,wonderful)link.insert(6,.)print(现在的size:,link.size)print(是否为空:,link.isEmpty())print(link:,link)link.append(33)print(link:,link)link.remove(0)print(link:,link)link.remove(6)print(link:,link)link.remove(3)print(link:,link)link.set(3,score)print(link:,link)print(link.get(3))print(life的位置:,link.find(life))print(world的位置:,link.find(world))print(.的位置:,link.find(.))print(Life的位置:,link.find(Life))print(使用for循环遍历)foriteminlink:print(item,end )