本文共 4469 字，大约阅读时间需要 14 分钟。
# 只是把书上的敲了一下，萌新理解循环链表以及对应的操作还是有点懵逼，先记下来，以后忘了还能回来看看。class LNode: # 节点 def __init__(self, elem, next_=None): # next主要保存对下一个节点的引用 self.elem = elem self.next = next_class LinkedListUnderflow(ValueError): passclass LList: # 普通链表 def __init__(self): self._head = None def is_empty(self): return self._head is None def prepend(self, elem): self._head = LNode(elem, self._head) def pop(self): if self._head is None: raise LinkedListUnderflow(" in pop") e = self._head self._head = self._head.next return e def append(self, elem): if self._head is None: self._head = LNode(elem) return p = self._head while p.next is not None: p = p.next p.next = LNode(elem) # 当 p.next is None def pop_last(self): if self._head is None: raise LinkedListUnderflow(" in pop_last ") p = self._head if p.next is None: e = p.elem self._head = None return e while p.next.next is not None: p = p.next e = p.next.elem p.next = None return e def filter(self, pred): p = self._head while p is not None: if pred(p.elem): # 如果有找到，直接返回，否则遍历下一个节点 yield p.elem p = p.next def printall(self): p = self._head while p is not None: print(p.elem, end='') if p.next is not None: # 当p还有下一个节点，使用逗号添加元素分隔符 print(', ', end='') p = p.next print('') def for_each(self, prec): p = self._head while p is not None: prec(p) p = p.next def elements(self): p = self._head while p is not None: yield p.elem p = p.nextclass LList1(LList): # 普通链表 def __init__(self): LList.__init__(self) self._rear = None def prepend(self, elem): if self._rear is None: self._head = LNode(elem, self._head) self._rear = self._head else: self._head = LNode(elem, self._head) def append(self, elem): if self._head is None: self._head = LNode(elem, self._head) self._rear = self._head else: # 不是空表的话，利用对表尾的引用，直接在表尾后面附加新元素 self._rear.next = LNode(elem) self._rear = self._rear.next def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last") p = self._head if p.next is None: e = p.elem self._head = None return e while p.next.next is not None: p = p.next e = p.next.elem p.next = None self._rear = p # 更改尾节点的引用 return eclass LCList: # 环形链表 def __init__(self): self._rear = None def is_empty(self): return self._rear is None def prepend(self, elem): p = LNode(elem) if self._rear is None: # 自环 p.next = p self._rear = p else: p.next = self._rear.next # 环形插入 self._rear.next = p def append(self, elem): self.prepend(elem) self._rear = self._rear.next def pop(self): if self._rear is None: raise LinkedListUnderflow("in pop of LCList") p = self._rear.next if self._rear is p: self._rear = None else: self._rear.next = self._rear.next.next return p.elem def printall(self): if self.is_empty(): return p = self._rear.next while True: print(p.elem) if p is self._rear: break p = p.nextclass DLNode(LNode): # 双向引用节点 def __init__(self, elem, prev=None, next_=None): LNode.__init__(self, elem, next_) self.prev = prevclass DLList(LList1): # 双向链表 def __init__(self): LList1.__init__(self) def prepend(self, elem): p = DLNode(elem, None, self._head) if self._head is None: self._rear = p else: p.next.prev = p self._head = p def append(self, elem): p = DLNode(elem, self._rear, None) if self._head is None: self._head = p else: p.prev.next = p self._rear = p def pop(self): if self._head is None: raise LinkedListUnderflow("in pop of DLList") e = self._head.elem self._head = self._head.next if self._head is not None: self._head.prev = None return e def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop of DLList") e = self._rear.elem if self._rear is None: self._head = None else: self._head.next = None return e
转载地址：http://csjqi.baihongyu.com/