Python单向链表和双向链表原理与用法实例详解-创新互联

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

创新互联公司是专业的白银网站建设公司,白银接单;提供成都网站设计、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行白银网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

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

链表由一个个节点组成。

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

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

单向列表的结构如下图:

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

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

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

插入一个新节点:

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

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

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

删除一个节点:

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

原理:找到要删除节点的上一个节点,直接上一个节点的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()


文章题目:Python单向链表和双向链表原理与用法实例详解-创新互联
标题网址:http://myzitong.com/article/ccoggj.html