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

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

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

链表由一个个节点组成。

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

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

单向列表的结构如下图：

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

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

插入一个新节点：

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

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

删除一个节点：

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

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

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

class Node:  next = None  data = None  def __init__(self,nodeData):    self.data = nodeDataclass 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 = bif __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()