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 __str__(self) -> str: 14 # """ 15 # 输出节点的信息 16 # :return: self.data 17 # """ 18 # return str(self.data) 19 20 def __repr__(self) -> str: 21 return str(self.data) 22 23 # def _getindex(self): 24 # return Link_list() 25 26 class Link_list: 27 """ 28 链表类: 29 属性: 1.链表头head 2.链表长度 30 方法: 1.是否为空 isEmpty 2.增加 append 3.删除节点 delete 4.修改(更新)节点 update 31 5.查找节点 getNode 6.获取节点的索引 getIndex 7.插入 insert 8.清空链表clear 32 """ 33 34 def __init__(self) -> None: 35 """ 36 初始化链表,head信息为空,长度为0 37 """ 38 self._head = None 39 self._length = 0 40 41 def isEmpty(self): 42 """ 43 判断链表是否为空 44 :return: 45 """ 46 return self._length == 0 47 48 def append(self, item): 49 """ 50 51 :param item: Node 或者 node的data信息 52 :return: None 53 """ 54 if not isinstance(item,Node): 55 item = Node(data=item) 56 if not self._head: 57 # head为Node对象 58 # head ---> data + nextNode 59 self._head = item 60 self._length += 1 61 else: 62 # 取到当前的Node对象 63 _node = self._head 64 # 如果不是最后一个节点则一直往下找 65 while _node._next: 66 _node = _node._next 67 # 将新的节点赋值给最后一个的_next属性 68 _node._next = item 69 self._length += 1 70 71 def delete(self,index): 72 """ 73 根据索引删除节点 74 :param index: 索引 75 :return: bool 76 """ 77 if not isinstance(index,int): 78 raise TypeError("index应该为int类型") 79 if self.isEmpty(): 80 print("当前链表为空") 81 return False 82 if index<0 or index>=self._length: 83 print("输入的索引不正确") 84 return False 85 elif index==0: 86 self._head=self._head._next 87 self._length-=1 88 return True 89 elif index==self._length-1: 90 _node = self._head 91 # 如果不是最后一个节点则一直往下找 92 for i in range(index): 93 _node = _node._next 94 _node._next=None 95 self._length-=1 96 return True 97 else: 98 _node = self._head 99 for j in range(index-1): 100 _node = _node._next 101 _node._next=_node._next._next 102 self._length-=1 103 return True 104 105 def pop(self,index): 106 """ 107 根据索引删除节点,并返回 108 :param index: 索引 109 :return: bool 110 """ 111 if not isinstance(index,int): 112 raise TypeError("index应该为int类型") 113 if self.isEmpty(): 114 print("当前链表为空") 115 return False 116 if index<0 or index>=self._length: 117 print("输入的索引不正确") 118 return False 119 elif index==0: 120 _node = self._head 121 self._head=self._head._next 122 self._length-=1 123 return _node 124 elif index==self._length-1: 125 _node = self._head 126 # 如果不是最后一个节点则一直往下找 127 for i in range(index): 128 _node = _node._next 129 __node = _node._next 130 _node._next=None 131 self._length-=1 132 return __node 133 else: 134 _node = self._head 135 for j in range(index-1): 136 _node = _node._next 137 __node = _node._next 138 _node._next=_node._next._next 139 self._length-=1 140 return __node 141 142 def getNode(self,index): 143 """ 144 根据index得到节点 145 :param index: 索引 146 :return: Node对象 147 """ 148 149 if not isinstance(index, int): 150 raise TypeError("index应该为int类型") 151 if self.isEmpty(): 152 print("当前链表为空") 153 return False 154 if index < 0 or index >= self._length: 155 print("输入的索引不正确") 156 return False 157 _node = self._head 158 for i in range(index): 159 _node = _node._next 160 return _node 161 162 def update(self,index,data): 163 """ 164 更新节点 165 :param index: 索引 166 :param data: 节点信息 167 :return: 返回修改后的节点 168 """ 169 if not isinstance(index, int): 170 raise TypeError("index应该为int类型") 171 if self.isEmpty(): 172 print("当前链表为空") 173 return False 174 if index < 0 or index >= self._length: 175 print("输入的索引不正确") 176 return False 177 _node = self._head 178 for i in range(index): 179 _node = _node._next 180 _node.data = data 181 return _node 182 183 184 def getIndex(self,node): 185 """ 186 根据节点得到节点索引 187 :param node:节点 188 :return:index 189 """ 190 if isinstance(node, Node): 191 for i in range(self._length): 192 if node is self.getNode(i): 193 return i 194 print("node异常") 195 return 196 else: 197 raise TypeError("类型不正确") 198 199 def insert(self,index,item): 200 if not isinstance(item, Node): 201 item = Node(data=item) 202 if not isinstance(index,int): 203 raise TypeError("index应该为int类型") 204 if index<0 or index>=self._length: 205 print("输入的索引不正确") 206 return False 207 if index==0: 208 old_next = self._head 209 item._next= old_next 210 self._head=item 211 self._length+=1 212 213 else: 214 _node = self._head 215 for i in range(index-1): 216 _node = _node._next 217 old_next = _node._next 218 _node._next = item 219 item._next = old_next 220 self._length += 1 221 return True 222 223 def clear(self): 224 self.head = None 225 self.length = 0 226 return True 227 228 def printl(self): 229 for i in range(self._length): 230 print(self.getNode(i))