python数据结构——链表
链表由一个个节点组成，每个节点包含自己的存储数据和下一个节点。
单链表
简单实现
先创造一个类来表示节点与节点之间的关系
class Node:
def __init__(self,data = None,next = None):
self.data = data
self.next = next
再创造一个类来表示链表
class Linklist:
def __init__(self):
self.head = None
再创建几个实例总代码如下：
class Node:
def __init__(self,data = None,next = None):
self.data = data
self.next = next
class Linklist:
def __init__(self):
self.head = None
node1 = Node(1)
node2 = Node(2)
linkhead = Linklist
linkhead.head = node1
node1.next = node2
print(linkhead.head.data)
print(linkhead.head.next.data)
linkhead.head指向node1，node1中的next指向node2
所以输出的值为1，2。
增添与删除
这样手动添加明显太麻烦，下面设计链表添加和删除节点的操作，顺便在写一个展示链表内容的方法。
class Node: #先定义链表节点
def __init__(self,data,next = None):
self.data = data
self.next = next
class Linklist: #链表操作类
def __init__(self,head): #引入头节点
self.head = head
def addhead(self,data): #添加新的头节点
self.new = Node(data,self.head)
self.head = self.new
def addtail(self,data): #在链表末尾添加节点
self.new = Node(data)
temp = self.head
while temp.next:
temp = temp.next
temp.next = self.new
def add(self,data,index): #通过索引插入新的节点
self.new = Node(data)
temp = self.head
while index-1:
temp = temp.next
index -= 1
self.new.next = temp.next
temp.next = self.new
def deletehead(self): #删除头节点
self.head = self.head.next
def deletetial(self): #删除末节点
temp = self.head
while temp.next.next:
temp = temp.next
temp.next = None
def delete(self,index): #通过索引删除节点
temp = self.head
while index-1:
temp = temp.next
index -= 1
temp.next = temp.next.next
def display(self): #遍历链表并输出每个节点的data
temp = self.head
while temp:
print(temp.data,end=' ')
temp = temp.next
node = Node(0) #创建头节点
node = Linklist(node) #将其导入链表
for i in range(1,10): #循环在链表末尾插入节点
node.addtail(i)
node.display() #遍历展示链表
print("\n")
node.delete(3) #删除第4个元素
node.deletehead() #删除头节点
node.deletetial() #删除末节点
node.addhead(10) #添加头节点
node.add(11,3) #在第4个索引处插入11
node.display()
#输出
#0 1 2 3 4 5 6 7 8 9
#10 1 2 11 4 5 6 7 8
增添
其中插入节点，是将插入位置的上一个节点的next指向新节点，并且让新节点的next指向原来该位置的节点，就实现了插入操作。
增加新的头节点，是将新节点的next指向原头节点，再将新节点赋值给原头节点。
再末尾添加节点，先通过一个temp遍历链表，当发现一个节点的next为空时，即为原来最后一个节点，将这个节点的next赋值为新节点，即完成操作。
删除
而删除节点，是将需删除节点的上一个节点的next指向需要删除节点的下一个节点，即将需删除节点的两侧节点连接，而忽略需删除节点。
删除头节点，只需将头节点赋值为头节点的next。
删除末节点，同添加节点，但是遍历时只要遍历到该删除节点的上一个节点，也就是只要找到一个节点的next的next为空，然后使这个节点的next等于None。
双指针
使用两个指针对链表遍历可以很好的解决一些问题。
如判断环形链表（即链表的末节点不指向空，而是指向前面的节点），即可设置两个运动速度不同的快慢指针。快指针一次走两个节点，慢指针一次走一个节点
这样设置快慢指针，如果为环形链表，总会使快指针追上慢指针。如下函数：
def ring(self):
if not self.head or not self.head.next:
return False
self.slow = self.head
self.fast = self.head.next
while self.slow != self.fast:
if not self.fast.next or not self.fast:
return False
else:
self.fast = self.fast.next.next
self.slow = self.slow.next
return True
再如找到相交链表的相交起点，也是设置两个指针A，B，让这两个指针分别遍历A，B链表，遍历完后再分别遍历另一个链表，若能找到一点使A，B指针相等，那么这点即为两个链表相交的起点。因为若两个链表相交，那么我们这样的遍历方法，实际上每个指针都遍历了两个链表的单独部分和公共部分，所以他们若相交，这种遍历方法必能找到相交的起点。
def interset(self,headA,headB):
self.a = headA
self.b = headB
while self.a != self.b:
self.a = self.a.next if self.a else headB
self.b = self.b.next if self.b else headA
return self.a