Python单向链表和双向链表原理与用法实例详解

本文实例讲述了Python单向链表和双向链表原理与用法。分享给大家供大家参考，具体如下：

链表是一种数据结构，链表在循环遍历的时候效率不高，但是在插入和删除时优势比较大。

链表由一个个节点组成。

单向链表的节点分为两个部分：存储的对象和对下一个节点的引用。注意是指向下一个节点。

而双向链表区别于单向链表的是它是由三个部分组成：存储的对象、对下一个节点的引用、对上一个节点的引用，可以实现双向遍历。

单向列表的结构如下图：

head是头节点，tail是尾节点，每个节点由Data存储对象和Next对下一个节点引用组成

下面说一下单向链表插入和删除的过程。

插入一个新节点：

原理：前一个节点的Next指向当前新节点，新节点的Next指向要插入节点位置的后一个节点。

注意：在实际应用时需要考虑插入位置是头结点和尾节点的情况。

删除一个节点：

原理：找到要删除节点的上一个节点，直接上一个节点的Next指向删除位置的下一个节点。

注意：在实际应用中需要考虑到删除的节点是否是头节点或尾节点，需要考虑到链表的长度。

下面附上一个用python写的单链表的例子。

class Node:
 next = None
 data = None
 def __init__(self,nodeData):
   self.data = nodeData
class List:
 head = None
 size = 0
 def __init__(self):
   self.size = 0
   self.head = None
 #遍历链表
 def a(self):
   print("avx")
 def printlist(self):
   p=self.head
   while(p is not None):
     print(p.data)
     p=p.next
   print("——————————————————————————————————————")
 def insertlink(self, a, newdata):
   newnode = Node(newdata)
   if self.size == 0:
     print("The link is none")
     self.head = newnode
     self.size = self.size+1
   else:
     p = self.head
     while(p is not None )and (p.data != a):
       p = p.next
     if p.next is None:
       p.next = newnode
       self.size = self.size + 1
     else:
       newnode.next = p.next
       p.next = newnode
       self.size = self.size + 1
 #删除链表中的节点
 def deldata(self,a):
   if self.size == 0:
     print("The link is none")
   elif self.size ==1:
     self.head = None
     self.size = self.size -1
   else:
     p = self.head
     while(p is not None )and (p.data != a):
       q = p
       p = p.next
     if p is None:
       print("Can't find a")
     elif p == self.head:
       self.head = p.next
     elif p.data ==a and p.next is not None:
       q.next = q.next.next
       self.size = self.size - 1
     else:
       q.next = None
       self.size = self.size - 1
 #修改链表中的指定节点
 def updatelink(self,a,b):
   p = self.head
   print(p.data)
   while(p is not None ) and (p.data!=a):
     p = p.next
   if p is None:
     print("Can't find a")
   else:
       p.data = b
if __name__=="__main__":
   p = List()
   p.insertlink(1,1)
   p.insertlink(1,2)
   p.insertlink(1,3)
   p.insertlink(1,4)
   print("_________________________---insertlink")
   p.printlist()
   print("_________________________--chalink")
   p.updatelink(2,5)
   p.printlist()
   print("___________________________-----dellink")
   p.deldata(5)
   p.printlist()

运行结果：

The link is none
_________________________---insertlink
1
4
3
2
——————————————————————————————————————
_________________________--chalink
1
1
4
3
5
——————————————————————————————————————
___________________________-----dellink
1
4
3
——————————————————————————————————————

双向链表的结构如下图：

head是头节点，tail是尾节点，每个节点由Data存储对象，Next对下一个节点的引用和Pre对上一个节点的引用组成。可以实现双向的遍历

下面说一下双向链表的插入和删除

插入一个新节点：

原理：

找到要插入的节点位置，新节点的Next指向插入位置的下一个节点，插入位置的下一个节点的Pre指向新节点。
插入位置节点的左侧Next指向新节点，新节点的Pre指向左侧的节点。

删除一个节点：

说明：

找到要删除的节点的上一个节点
直接把上一个节点的Next指向要删除节点的下一个节点
并把要删除节点的下一个节点的Pre指向要上出节点的上一个节点即可

双向链表的代码：

class Node():
 data = None
 nextnode = None
 prenode = None
 def __init__(self, data):
   self.data = data
class PersonChan():
 size = 0
 head = None
 tail = None
 def __init__(self):
   self.head = None
   self.tail = None
   self.size = 0
 #增加节点
 def add_node(self, a):
   newnode = Node(a)
   if(self.head == None):
     self.head = newnode
     self.head.prenode = None
     self.tail = newnode
     self.tail.prenode = None
     self.tail.nextnode = None
     self.size = self.size+1
   else:
     temp = self.head
     while temp.nextnode is not None:#返回尾节点tail
       temp = temp.nextnode
     temp.nextnode = newnode
     self.tail = newnode
     self.tail.prenode = temp
     self.tail.nextnode = None
     self.size = self.size+1
 #在查找到的a后面增加节点
 def ins_node(self,a,b):
   newnode = Node(b)
   if self.head ==None:
     self.head = newnode
     self.tail = newnode
     print("Insert success:",newnode.data)
     self.size = self.size +1
   else:
     temp = self.head
     while(temp is not None)&(temp.data != a):
       temp = temp.nextnode
     if temp.nextnode == None:
       temp.nextnode = newnode
       self.tail = newnode
       self.tail.prenode = temp
       self.tail.nextnode = None
       temp = None
       print("Insert success:",newnode.data)
       self.size = self.size+1
     else:
       newnode.prenode = temp
       newnode.nextnode = temp.nextnode
       temp.nextnode = newnode
       print("Insert success:",newnode.data)
       self.size = self.size+1
 #删除节点
 def del_node(self,a):
   if self.head == None:
     pass
   elif self.head.data == a:
     if self.size ==1:
       self.head = None
       self.tail = None
       self.size = self.size-1
     else:
       self.head = self.head.nextnode
       self.size = self.size -1
   else:
     temp = self.head.nextnode
     while (temp is not None) and (temp.data != a):
       temp = temp.nextnode
     p = temp.prenode
     if temp != None:
       if temp.nextnode == None:
         self.tail = p
         self.tail.nextnod = None
       else:
         p.nextnode = temp.nextnode
         temp = None
       self.size = self.size -1
       print("Delete is success:",a)
 def listall(self):#正序排列
   if self.size == 0:
     print("No data in the list")
   else:
     temp = self.head
     while(temp is not None):
       print(temp.data)
       temp = temp.nextnode
 def lista(self):#倒序排列
   if self.size == 0:
     print("No data in the list")
   temp = self.tail
   while(temp is not None):
     print(temp.data)
     temp = temp.prenode
if __name__ == '__main__':
 link = PersonChan()
 link.add_node(1)
 link.add_node(2)
 link.add_node(3)
 link.add_node(4)
 link.listall()
 print("The list's size is:",link.size)
 link.lista()

运行结果：

1
2
3
4
("The list's size is:", 4)
4
3
2
1

希望本文所述对大家Python程序设计有所帮助。

来源：https://www.cnblogs.com/meitian/p/4584020.html