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相关内容感兴趣的读者可查看本站专题：《python数据结构与算法教程》、《python加密解密算法与技巧总结》、《python编码操作技巧总结》、《python函数使用技巧总结》、《python字符串操作技巧汇总》及《python入门与进阶经典教程》

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