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

更新時(shí)間：2018年08月31日 14:31:53 作者：每天1990

這篇文章主要介紹了Python單向鏈表和雙向鏈表原理與用法,結(jié)合實(shí)例形式詳細(xì)分析了單向鏈表與雙向鏈表的概念、原理以及創(chuàng)建、添加、刪除等相關(guān)操作技巧,需要的朋友可以參考下

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

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，鏈表在循環(huán)遍歷的時(shí)候效率不高，但是在插入和刪除時(shí)優(yōu)勢(shì)比較大。

鏈表由一個(gè)個(gè)節(jié)點(diǎn)組成。

單向鏈表的節(jié)點(diǎn)分為兩個(gè)部分：存儲(chǔ)的對(duì)象和對(duì)下一個(gè)節(jié)點(diǎn)的引用。注意是指向下一個(gè)節(jié)點(diǎn)。

而雙向鏈表區(qū)別于單向鏈表的是它是由三個(gè)部分組成：存儲(chǔ)的對(duì)象、對(duì)下一個(gè)節(jié)點(diǎn)的引用、對(duì)上一個(gè)節(jié)點(diǎn)的引用，可以實(shí)現(xiàn)雙向遍歷。

單向列表的結(jié)構(gòu)如下圖：

head是頭節(jié)點(diǎn)，tail是尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)由Data存儲(chǔ)對(duì)象和Next對(duì)下一個(gè)節(jié)點(diǎn)引用組成

下面說(shuō)一下單向鏈表插入和刪除的過(guò)程。

插入一個(gè)新節(jié)點(diǎn)：

原理：前一個(gè)節(jié)點(diǎn)的Next指向當(dāng)前新節(jié)點(diǎn)，新節(jié)點(diǎn)的Next指向要插入節(jié)點(diǎn)位置的后一個(gè)節(jié)點(diǎn)。

注意：在實(shí)際應(yīng)用時(shí)需要考慮插入位置是頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的情況。

刪除一個(gè)節(jié)點(diǎn)：

原理：找到要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，直接上一個(gè)節(jié)點(diǎn)的Next指向刪除位置的下一個(gè)節(jié)點(diǎn)。

注意：在實(shí)際應(yīng)用中需要考慮到刪除的節(jié)點(diǎn)是否是頭節(jié)點(diǎn)或尾節(jié)點(diǎn)，需要考慮到鏈表的長(zhǎng)度。

下面附上一個(gè)用python寫(xiě)的單鏈表的例子。

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
  #刪除鏈表中的節(jié)點(diǎn)
  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
  #修改鏈表中的指定節(jié)點(diǎn)
  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()

運(yùn)行結(jié)果：

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

雙向鏈表的結(jié)構(gòu)如下圖：

head是頭節(jié)點(diǎn)，tail是尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)由Data存儲(chǔ)對(duì)象，Next對(duì)下一個(gè)節(jié)點(diǎn)的引用和Pre對(duì)上一個(gè)節(jié)點(diǎn)的引用組成。可以實(shí)現(xiàn)雙向的遍歷

下面說(shuō)一下雙向鏈表的插入和刪除

插入一個(gè)新節(jié)點(diǎn)：

原理：

找到要插入的節(jié)點(diǎn)位置，新節(jié)點(diǎn)的Next指向插入位置的下一個(gè)節(jié)點(diǎn)，插入位置的下一個(gè)節(jié)點(diǎn)的Pre指向新節(jié)點(diǎn)。
插入位置節(jié)點(diǎn)的左側(cè)Next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的Pre指向左側(cè)的節(jié)點(diǎn)。

刪除一個(gè)節(jié)點(diǎn)：

說(shuō)明：

找到要?jiǎng)h除的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
直接把上一個(gè)節(jié)點(diǎn)的Next指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
并把要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的Pre指向要上出節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)即可

雙向鏈表的代碼：

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
  #增加節(jié)點(diǎn)
  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:#返回尾節(jié)點(diǎn)tail
        temp = temp.nextnode
      temp.nextnode = newnode
      self.tail = newnode
      self.tail.prenode = temp
      self.tail.nextnode = None
      self.size = self.size+1
  #在查找到的a后面增加節(jié)點(diǎn)
  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
  #刪除節(jié)點(diǎn)
  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()

運(yùn)行結(jié)果：