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,next=None):self.element=element# 元素self.next=next# 指针classMyLinkedList:def__init__(self):self.__head=Noneself.__size=0# 返回链表中元素个数@property# 有它，外面访问size可以是 xx.size,没有它，外部访问size必须是 xx.size()defsize(self):returnself.__size# 判断链表是否为空defisEmpty(self):returnself.__size==0# 在指定位置插入元素definsert(self,index,element):# 第一步：检查index的合法性，合理的范围[0,self.__size]ifindex<0orindex>self.__size:raiseIndexError(f'{index}越界了')# 第二步: 创建新结点new_node=Node(element)# 创建新结点，此时新节点的next是Noneifindex==0:# 如果插入位置是0，需要单独谈论new_node.next=self.__head self.__head=new_nodeelse:# 第三步：根据index导航到对应的节点node=self.__head# 整个节点foriinrange(index-1):node=node.next# 经过这个循环，node最后指向 index 的前一个元素# 第四步：让新结点的next指向原来[index]位置的结点，[index]前一个结点的next指向新结点new_node.next=node.nextnode.next=new_node# 第五步：元素个数增加self.__size+=1# 在末尾插入元素defappend(self,element):# 第一步：遍历到尾结点node=self.__head# 第二步，创建新结点new_node=Node(element)# 修复：增加空链表的防御性判断ifself.__headisNone:self.__head=new_nodeelse:whilenode.nextisnotNone:node=node.next# 出了循环,node.next = None，说明是尾结点# 第三步，尾部追加元素node.next=new_node# 第四步：个数+1self.__size+=1# 删除指定位置的元素defremove(self,index):# 第一步：检查index的合法性，合理的删除范围[0,self.__size-1],检查index是否在已有元素的下标范围self.check_exsit_index(index)ifindex==0:# 头结点self.__head=self.__head.nextelse:# 第二步：根据index导航到[index-1]的结点node=self.find_element(index-1)# 经过这个循环，node最后指向的是index前一个结点# 第三步：要记录[index]位置的结点remove_node=node.next# 第四步：让node.next指向node的next.next结点# remove_node 是[index]位置的结点# node 是[index-1]位置的结点# remove_node的next是[index+1]位置的结点node.next=node.next.next# 第五步：[index]位置的结点的next和element都应该置空remove_node.element=Noneremove_node.next=None# 第六步：个数-1self.__size-=1# 合法检查：index是否在已有元素下标的合法范围内defcheck_exsit_index(self,index):# 是否index在已有元素的下标范围ifindex<0orindex>=self.__size:raiseIndexError(f"{index}越界了")# 修改指定位置的元素defset(self,index,element):# 第一步：检查index是否在已有元素的下标范围内self.check_exsit_index(index)# 第二步： 导航到index的位置node=self.find_element(index)# 循环出来后，node最后指向index位置的结点# 第三步：替换[index]位置结点的元素node.element=element# 查找元素deffind_element(self,index)->Any:node=self.__headforiinrange(index):node=node.nextreturnnode# 获取指定位置的元素defget(self,index):self.check_exsit_index(index)# 第二步： 导航到index的位置node=self.find_element(index)returnnode.element# 查找链表中某个元素的位置deffind(self,element):index=-1node=self.__headwhilenodeisnotNone:index=index+1ifnode.element==element:returnindex node=node.nextreturn-1# _str__ 是一个非常实用的魔术方法（Magic Method），专门用来自定义对象的字符串表示形式。# 有它，可以打印出元素的值，否则只能打印出地址值def__str__(self):result=""# 遍历node=self.__headwhilenodeisnotNone:result+=str(node.element)result+="->"ifnode.nextelse""node=node.nextreturnresultdef__iter__(self):node=self.__headwhilenodeisnotNone:yieldnode.element node=node.next# 测试if__name__=='__main__':link=MyLinkedList()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=' ')
