Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】
本文实例讲述了Python数据结构与算法之链表定义与用法。分享给大家供大家参考，具体如下：
本文将为大家讲解：
（1）从链表节点的定义开始，以类的方式，面向对象的思想进行链表的设计
（2）链表类插入和删除等成员函数实现时需要考虑的边界条件，
prepend（头部插入）、pop（头部删除）、append（尾部插入）、pop_last（尾部删除）
2.1插入：
空链表
链表长度为1
插入到末尾
2.2删除
空链表
链表长度为1
删除末尾元素
（3）从单链表到单链表的一众变体：
带尾节点的单链表
循环单链表
双链表
1.链表节点的定义
classLNode: def__init__(self,elem,next_=None): self.elem=elem self.next=next_
2.单链表的实现
重点理解插入、删除的实现及其需要考虑的边界条件：
classLinkedListUnderflow(ValueError):
pass
classLList:
def__init__(self):
self._head=None
defis_empty(self):
returnself._headisNone
defprepend(self,elem):
self._head=LNode(elem,self._head)
defpop(self):
ifself._headisNone:
raiseLinkedListUnderflow('inpop')
e=self._head.elem
self._head=self._head.next
returne
defappend(self,elem):
ifself._headisNone:
self._head=LNode(elem)
return
p=self._head
whilep.nextisnotNone:
p=p.next
p.next=LNode(elem)
defpop_last(self):
ifself._headisNone:
raiseLinkedListUnderflow('inpop_last')
p=self._head
ifp.nextisNone:
e=p.elem
self._head=None
returne
whilep.next.nextisnotNone:
p=p.next
e=p.next.elem
p.next=None
returne
简单总结：
（0）能够访问p.next.next的前提是p.next不为空；
（1）尾部插入，如果链表不为空，需且仅需改变的是尾部节点的指针；
（2）尾部删除，如果链表长度不为空，需且仅需改变的是倒数第二个节点的指针。
单链表的简单变形：具有尾部节点的单链表
classLList1(LList): def__init__(self): LList.__init__(self) self._rear=None ...
我们仅需重写的是：头部的插入、尾部的插入、尾部的删除
defprepend(self,elem):
ifself._headisNone:
self._head=LNode(elem)
self._rear=self._head
else:
self._head=LNode(elem,self._head)
defappend(self,elem):
ifself._headisNone:
self._head=LNode(elem)
self._rear=self._head
else:
self._rear.next=LNode(elem)
self._rear=self._rear.next
defpop_last(self):
ifself._headisNone:
raiseLinkedListUnderflow('inpop_last')
p=self._head
ifp.nextisNone:
e=p.elem
self._head=None
returne
whilep.next.nextisnotNone:
p=p.next
e=p.next.elem
self._rear=p
p.next=None
returne
单链表的变体：循环单链表
classLCList:
def__init__(self):
self._rear=None
defprepend(self,elem):
ifself._rearisNone:
self._rear=LNode(elem)
self._rear.next=self._rear
else:
self._rear.next=LNode(elem,self._rear.next)
defappend(self,elem):
self.prepend(elem)
self_rear=self._rear.next
defpop(self):
ifself._rearisNone:
raiseLinkedListUnderflow('inpop')
p=self._rear.next
ifpisNone:
self._rear=None
else:
self._rear.next=p.next
returnp.elem
defprintall(self):
ifself._rearisNone:
raise...
p=self._rear.next
whileTrue:
print(p.elem)
ifpisself._rear:
break
p=p.next
更多关于Python相关内容可查看本站专题：《Python数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。