1 classNode:2 '''

3 节点类4 链表节点结构 data next5 data: 节点保存的数据6 _next: 保存下一个节点对象7 '''

8

9 def __init__(self, data, pnext=None):10 self.data =data11 self._next =pnext12 #13 #def __str__(self) -> str:

14 #"""

15 #输出节点的信息

16 #:return: self.data

17 #"""

18 #return str(self.data)

19

20 def __repr__(self) ->str:21 returnstr(self.data)22

23 #def _getindex(self):

24 #return Link_list()

25

26 classLink_list:27 """

28 链表类:29 属性: 1.链表头head 2.链表长度30 方法: 1.是否为空 isEmpty 2.增加 append 3.删除节点 delete 4.修改(更新)节点 update31 5.查找节点 getNode 6.获取节点的索引 getIndex 7.插入 insert 8.清空链表clear32 """

33

34 def __init__(self) ->None:35 """

36 初始化链表,head信息为空,长度为037 """

38 self._head =None39 self._length =040

41 defisEmpty(self):42 """

43 判断链表是否为空44 :return:45 """

46 return self._length ==047

48 defappend(self, item):49 """

50

51 :param item: Node 或者 node的data信息52 :return: None53 """

54 if notisinstance(item,Node):55 item = Node(data=item)56 if notself._head:57 #head为Node对象

58 #head ---> data + nextNode

59 self._head =item60 self._length += 1

61 else:62 #取到当前的Node对象

63 _node =self._head64 #如果不是最后一个节点则一直往下找

65 while_node._next:66 _node =_node._next67 #将新的节点赋值给最后一个的_next属性

68 _node._next =item69 self._length += 1

70

71 defdelete(self,index):72 """

73 根据索引删除节点74 :param index: 索引75 :return: bool76 """

77 if notisinstance(index,int):78 raise TypeError("index应该为int类型")79 ifself.isEmpty():80 print("当前链表为空")81 returnFalse82 if index<0 or index>=self._length:83 print("输入的索引不正确")84 returnFalse85 elif index==0:86 self._head=self._head._next87 self._length-=1

88 returnTrue89 elif index==self._length-1:90 _node =self._head91 #如果不是最后一个节点则一直往下找

92 for i inrange(index):93 _node =_node._next94 _node._next=None95 self._length-=1

96 returnTrue97 else:98 _node =self._head99 for j in range(index-1):100 _node =_node._next101 _node._next=_node._next._next102 self._length-=1

103 returnTrue104

105 defpop(self,index):106 """

107 根据索引删除节点,并返回108 :param index: 索引109 :return: bool110 """

111 if notisinstance(index,int):112 raise TypeError("index应该为int类型")113 ifself.isEmpty():114 print("当前链表为空")115 returnFalse116 if index<0 or index>=self._length:117 print("输入的索引不正确")118 returnFalse119 elif index==0:120 _node =self._head121 self._head=self._head._next122 self._length-=1

123 return_node124 elif index==self._length-1:125 _node =self._head126 #如果不是最后一个节点则一直往下找

127 for i inrange(index):128 _node =_node._next129 __node =_node._next130 _node._next=None131 self._length-=1

132 return __node

133 else:134 _node =self._head135 for j in range(index-1):136 _node =_node._next137 __node =_node._next138 _node._next=_node._next._next139 self._length-=1

140 return __node

141

142 defgetNode(self,index):143 """

144 根据index得到节点145 :param index: 索引146 :return: Node对象147 """

148

149 if notisinstance(index, int):150 raise TypeError("index应该为int类型")151 ifself.isEmpty():152 print("当前链表为空")153 returnFalse154 if index < 0 or index >=self._length:155 print("输入的索引不正确")156 returnFalse157 _node =self._head158 for i inrange(index):159 _node =_node._next160 return_node161

162 defupdate(self,index,data):163 """

164 更新节点165 :param index: 索引166 :param data: 节点信息167 :return: 返回修改后的节点168 """

169 if notisinstance(index, int):170 raise TypeError("index应该为int类型")171 ifself.isEmpty():172 print("当前链表为空")173 returnFalse174 if index < 0 or index >=self._length:175 print("输入的索引不正确")176 returnFalse177 _node =self._head178 for i inrange(index):179 _node =_node._next180 _node.data =data181 return_node182

183

184 defgetIndex(self,node):185 """

186 根据节点得到节点索引187 :param node:节点188 :return:index189 """

190 ifisinstance(node, Node):191 for i inrange(self._length):192 if node isself.getNode(i):193 returni194 print("node异常")195 return

196 else:197 raise TypeError("类型不正确")198

199 definsert(self,index,item):200 if notisinstance(item, Node):201 item = Node(data=item)202 if notisinstance(index,int):203 raise TypeError("index应该为int类型")204 if index<0 or index>=self._length:205 print("输入的索引不正确")206 returnFalse207 if index==0:208 old_next =self._head209 item._next=old_next210 self._head=item211 self._length+=1

212

213 else:214 _node =self._head215 for i in range(index-1):216 _node =_node._next217 old_next =_node._next218 _node._next =item219 item._next =old_next220 self._length += 1

221 returnTrue222

223 defclear(self):224 self.head =None225 self.length =0226 returnTrue227

228 defprintl(self):229 for i inrange(self._length):230 print(self.getNode(i))