Python创建链表

# 定义一个链表 class Node: """ 定义节点类 data:数据 _next:下一个数据 """ def __init__(self, data, _next=None): self.data = data self._next = _next def __repr__(self): """ 用来定义Node的字节输出, __repr__()方法是object类提供的方法， 所有的Python对象都具有__repr__() 方法。它是一个“自我描述”的方法， 该方法通常实现场景是：当开发人员直接打印该对象时， 系统将会输出该对象的“自我描述”信息，用来告诉外界该对象具有的状态信息。 object类提供的__repr__()方法总是返回该对象实现类的“类名+object at + 内存地址 ”值， 这个返回值并不能真正实现“自我描述”的功能， 因此如果用户需要自定义类能实现“自我描述”的功能，就必须重写__repr__()方法。 """ return str(self.data) class ChainTable(Node): """ 定义链表 """ def __init__(self): self.head = None self.length = 0 def isEmpty(self): return (self.length == 0) def add(self, dataOrNode): item = None if isinstance(dataOrNode, Node): item = dataOrNode else: item = Node(dataOrNode) if not self.head: # 若链表的头为空 self.head = item self.length += 1 else: node = self.head while node._next: # 当有节点时，新增下一个节点 node = node._next node._next = item self.length += 1 def delete(self, index): if self.isEmpty(): print("链表是空的") return if index < 0 or index >= self.length: print("超出索引长度") return # 删除第一个节点 if index == 0: self.head = self.head._next self.length -= 1 return # prev为保存前导节点 # node为保存当前节点 # 当j与index相等时就 # 相当于找到要删除的节点 j = 0 node = self.head prev = self.head while node._next and j < index: prev = node node = node._next j += 1 if j == index: # 找到节点后将下一个节点覆盖到本节点 prev._next = node._next self.length -= 1 def update(self, index, data): if self.isEmpty() or index < 0 or index >= self.length: print('索引超出范围') return j = 0 node = self.head while node._next and j < index: node = node._next j += 1 if j == index: node.data = data # 查找一个节点 def getItem(self, index): if self.isEmpty() or index < 0 or index >= self.length: print('超出索引长度') return j = 0 node = self.head while node._next and j < index: node = node._next j += 1 return node.data # 从头到尾打印链表 def print_chain(self): if self.isEmpty(): print('链表为空') num = [] node = self.head while node: num.append(node) node = node._next return num # 查找一个节点的索引 def getIndex(self, data): j = 0 if self.isEmpty(): print('链表为空') return node = self.head while node: if node.data == data: return j node = node._next j += 1 if j == self.length: print("%s not found" % str(data)) return def insert(self, index, dataOrNode): if self.isEmpty(): print('链表为空') return if index < 0 or index >= self.length: print('超出索引长度') return item = None if isinstance(dataOrNode, Node): item = dataOrNode else: item = Node(dataOrNode) if index == 0: item._next = self.head self.head = item self.length += 1 return j = 0 node = self.head prev = self.head while node._next and j < index: prev = node node = node._next j += 1 if j == index: item._next = node prev._next = item self.length += 1 def clear(self): self.head = None self.length = 0 def __repr__(self): if self.isEmpty(): return "链表为空" node = self.head nlist = '' while node: nlist += str(node.data) + ' ' node = node._next return nlist def __getitem__(self, ind): if self.isEmpty() or ind < 0 or ind >= self.length: print("超出索引长度") return return self.getItem(ind) def __setitem__(self, ind, val): if self.isEmpty() or ind < 0 or ind >= self.length: print("超出索引长度") return self.update(ind, val) def __len__(self): return self.length chainTable = ChainTable() for i in range(10): chainTable.add(i) print(chainTable.getIndex(1)) print(chainTable.print_chain())

在节点的删除操作，和对链表的销毁操作中。不必担心太多节点储存在内存中而出现内存泄漏的现象。因为Python有自动垃圾回收机制。当然如果觉得不删除节点不爽的话，可以调用对象的del()方法。

参考文章