Python單向鏈表和雙向鏈表原理與用法實例詳解

2020-01-04 14:36:10

字體：大中小

來源：轉載

供稿：網友

本文實例講述了Python單向鏈表和雙向鏈表原理與用法。分享給大家供大家參考，具體如下：

鏈表是一種數據結構，鏈表在循環遍歷的時候效率不高，但是在插入和刪除時優勢比較大。

鏈表由一個個節點組成。

單向鏈表的節點分為兩個部分：存儲的對象和對下一個節點的引用。注意是指向下一個節點。

而雙向鏈表區別于單向鏈表的是它是由三個部分組成：存儲的對象、對下一個節點的引用、對上一個節點的引用，可以實現雙向遍歷。

單向列表的結構如下圖：

Python,單向鏈表,雙向鏈表

head是頭節點，tail是尾節點，每個節點由Data存儲對象和Next對下一個節點引用組成

下面說一下單向鏈表插入和刪除的過程。

插入一個新節點：

Python,單向鏈表,雙向鏈表

原理：前一個節點的Next指向當前新節點，新節點的Next指向要插入節點位置的后一個節點。

注意：在實際應用時需要考慮插入位置是頭結點和尾節點的情況。

刪除一個節點：

Python,單向鏈表,雙向鏈表

原理：找到要刪除節點的上一個節點，直接上一個節點的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()

運行結果：

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

雙向鏈表的結構如下圖：

Python,單向鏈表,雙向鏈表

head是頭節點，tail是尾節點，每個節點由Data存儲對象，Next對下一個節點的引用和Pre對上一個節點的引用組成。可以實現雙向的遍歷

下面說一下雙向鏈表的插入和刪除

插入一個新節點：

Python,單向鏈表,雙向鏈表

原理：

找到要插入的節點位置，新節點的Next指向插入位置的下一個節點，插入位置的下一個節點的Pre指向新節點。
插入位置節點的左側Next指向新節點，新節點的Pre指向左側的節點。

刪除一個節點：

Python,單向鏈表,雙向鏈表

說明：

找到要刪除的節點的上一個節點
直接把上一個節點的Next指向要刪除節點的下一個節點
并把要刪除節點的下一個節點的Pre指向要上出節點的上一個節點即可

雙向鏈表的代碼：

class Node():  data = None  nextnode = None  prenode = None  def __init__(self, data):    self.data = dataclass 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.prenodeif __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()

運行結果：