1 class Node: 2 ''' 3 节点类 4 链表节点结构 data next 5 data: 节点保存的数据 6 _next: 保存下一个节点对象 7 ''' 8 9 def __init__(self, data, pnext=None): 10 self.data = data 11 self._next = pnext 12 13 def __repr__(self) -> str: 14 return str(self.data) 15 16 17 class Link_list: 18 """ 19 链表类: 20 属性: 1.链表头head 2.链表长度 21 方法: 1.是否为空 isEmpty 2.增加 append 3.删除节点 delete 4.修改(更新)节点 update 22 5.查找节点 getNode 6.获取节点的索引 getIndex 7.插入 insert 8.清空链表clear 23 """ 24 25 def __init__(self) -> None: 26 """ 27 初始化链表,head信息为空,长度为0 28 """ 29 self._head = None 30 self._length = 0 31 32 def isEmpty(self): 33 """ 34 判断链表是否为空 35 :return: 36 """ 37 return self._length == 0 38 39 def append(self, item): 40 """ 41 42 :param item: Node 或者 node的data信息 43 :return: None 44 """ 45 46 if not isinstance(item, Node): 47 item = Node(data=item) 48 49 if not self._head: 50 # head为Node对象 51 # head ---> data + nextNode 52 self._head = item 53 self._length += 1 54 else: 55 # 取到第一个的Node对象 56 _node = self._head 57 # 如果不是最后一个节点则一直往下找,使用while的原因是不知道会有多少个 58 while _node._next: 59 # 得到后继为空的,也就是最后一个 60 _node = _node._next 61 # 将新的节点赋值给最后一个的_next属性 62 _node._next = item 63 self._length += 1 64 65 def insert(self, index, item): 66 if not isinstance(item, Node): 67 item = Node(data=item) 68 if not isinstance(index, int): 69 raise TypeError("index应该为int类型") 70 if index < 0 or index >= self._length: 71 print("输入的索引不正确") 72 return False 73 if index == 0: 74 # 在链表的头部进行添加 75 old_head = self._head 76 item._next = old_head 77 self._head = item 78 self._length += 1 79 80 else: 81 # 得到第一个node 82 _node = self._head 83 for i in range(index - 1): 84 # 得到插入位置的前驱 85 _node = _node._next 86 # 得到本来在指定位置的node 87 old_index_node = _node._next 88 # 给插入的node设置前驱 89 _node._next = item 90 # 给插入的元素设置后继 91 item._next = old_index_node 92 self._length += 1 93 return True 94 95 def delete(self, index): 96 """ 97 根据索引删除节点 98 :param index: 索引 99 :return: bool 100 """ 101 if not isinstance(index, int): 102 raise TypeError("index应该为int类型") 103 if self.isEmpty(): 104 print("当前链表为空") 105 return False 106 if index < 0 or index >= self._length: 107 print("输入的索引不正确") 108 return False 109 elif index == 0: 110 self._head = self._head._next 111 self._length -= 1 112 return True 113 elif index == self._length - 1: 114 _node = self._head 115 # 如果不是最后一个节点则一直往下找 116 for i in range(index): 117 _node = _node._next 118 _node._next = None 119 self._length -= 1 120 return True 121 else: 122 _node = self._head 123 for j in range(index - 1): 124 _node = _node._next 125 _node._next = _node._next._next 126 self._length -= 1 127 return True 128 129 130 131 def pop(self,index=None): 132 """ 133 134 :type int 135 :param index: 136 :return: 137 """ 138 # 先判断链表是否是空的 139 if self.isEmpty(): 140 print("当前链表为空") 141 return False 142 if index is None: 143 # 不指定index的时候,直接弹出最后一个 144 index = self._length-1 145 if not isinstance(index, int): 146 raise TypeError("index应该为int类型") 147 if index < 0 or index >= self._length: 148 print("输入的索引不正确") 149 return False 150 # 获取head指向的node 151 first_node = self._head 152 _node = first_node 153 for i in range(index-1): 154 # 得到第index-1个位置的node 155 _node = _node._next 156 157 if index==0: 158 self._head=first_node._next 159 self._length-=1 160 return first_node 161 else: 162 select_node = _node._next 163 _node._next= select_node._next 164 self._length-=1 165 return select_node 166 167 168 169 170 171 172 173 174 # def pop(self, index): 175 # """ 176 # 根据索引删除节点,并返回 177 # :param index: 索引 178 # :return: bool 179 # """ 180 # if not isinstance(index, int): 181 # raise TypeError("index应该为int类型") 182 # if self.isEmpty(): 183 # print("当前链表为空") 184 # return False 185 # if index < 0 or index >= self._length: 186 # print("输入的索引不正确") 187 # return False 188 # elif index == 0: 189 # """弹出第一个node""" 190 # # 得到第0个node 191 # _node = self._head 192 # # 将head指向第二个node 193 # self._head = _node._next 194 # self._length -= 1 195 # return _node 196 # elif index == self._length - 1: 197 # """弹出最后一个node""" 198 # # 先找到head指向的node,即第0个node 199 # _node = self._head 200 # # 如果不是最后一个节点则一直往下找 201 # 202 # for i in range(index - 1): 203 # # 拿到倒数第二个node 204 # _node = _node._next 205 # end_node = _node._next 206 # # 给倒数第二个node设置新的后继,None 207 # _node._next = None 208 # self._length -= 1 209 # return end_node 210 # else: 211 # # 中间的node 212 # _node = self._head 213 # for j in range(index - 1): 214 # # 得到指定index的前驱 215 # _node = _node._next 216 # # 得到应得的node 217 # selected_node = _node._next 218 # # 将弹出的node的前驱的后继设置成要弹出的node的后继 219 # _node._next = selected_node._next 220 # self._length -= 1 221 # return selected_node 222 223 def getNode(self, index): 224 """ 225 根据index得到节点 226 :type int 227 :param index: 索引 228 :type: Node 229 :return: Node对象 230 """ 231 if not isinstance(index, int): 232 raise TypeError("index应该为int类型") 233 if self.isEmpty(): 234 print("当前链表为空") 235 return False 236 if index < 0 or index >= self._length: 237 print("输入的索引不正确") 238 return False 239 # 得到第0个node 240 _node = self._head 241 for i in range(index): 242 _node = _node._next 243 return _node 244 245 def update(self, index, data): 246 """ 247 更新节点 248 :param index: 索引 249 :param data: 节点信息 250 :return: 返回修改后的节点 251 """ 252 if not isinstance(index, int): 253 raise TypeError("index应该为int类型") 254 if self.isEmpty(): 255 print("当前链表为空") 256 return False 257 if index < 0 or index >= self._length: 258 print("输入的索引不正确") 259 return False 260 _node = self._head 261 for i in range(index): 262 _node = _node._next 263 _node.data = data 264 return _node 265 266 def getIndex(self, node): 267 """ 268 根据节点得到节点索引 269 :param node:节点 270 :return:index 271 """ 272 if isinstance(node, Node): 273 for i in range(self._length): 274 if node is self.getNode(i): 275 return i 276 print("node异常") 277 return 278 else: 279 raise TypeError("类型不正确") 280 281 def clear(self): 282 self.head = None 283 self._length = 0 284 return True 285 286 def printl(self): 287 for i in range(self._length): 288 print(self.getNode(i))