这篇文章主要介绍了Python单链表原理与实现方法,结合实例形式详细分析了Python单链表的具体概念、原理、实现方法与操作注意事项,需要的朋友可以参考下

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

Python实现单链表关于链表
    链表(Linked List)是由许多相同数据类型的数据项按照特定顺序排列而成的线性表。 链表中个数据项在计算机内存中的位置是不连续且随机的,数组在内存中是连续的。 链表数据的插入和删除很方便,但查找数据效率低下,不能像数组一样随机读取数据。
单链表的实现

    一个单向链表的节点由数据字段和指针组成,指针指向下一个元素所在内存地址

    定义一个链表节点类,self.value实例属性表示节点数据字段;self.next表示指针;初始化值为None

    class Node(object):
      def __init__(self, value=None, next=None):
        self.value = value
        self.next = next
    

    在单链表中第一个节点为头(head)指针节点(即头指针指向的节点为单链表第一个节点,后续简称头指针节点),从头指针节点出发可以遍历整个链表,进行元素查找,插入和删除,非常重要。一般不移动head头指针。

    单链表中最后一个节点为尾节点,其指针为None,表示结束。

    建立单链表我们首先需要创建头指针节点(引入头指针是为了方便操作单链表,对于头指针节点,只有指针域指向链表第一个节点,不含实际值)

    class linkedList(object):
      def __init__(self):
        self.head = Node()	# 创建头指针结点
        self.length = 0	# 初始链表长度,头指针节点不计入长度
      def __len__(self):	# 重写特殊方法返回self.length
        return self.length
    

    链表初始化之后,开始定义链表方法

    链表头部插入节点:

    • 调用Node()传入待插入的值value创建待插入节点

      判断当前链表是否为空链表,链表为空:

      • 插入节点既是链表头指针指向的节点也是尾节点(指向None)
    • 链表不为空:

      • 待插入节点指向原头指针节点,头指针重新指向待插入节点 首先需要将原头指针结点,存放到临时变量中(防止head指针变更时,指针断裂导致数据丢失,链表中指针就是连接的纽带,其中某个纽带断裂(即指针指向其他)则后续数据都将丢失) 将头指针指向新插入节点 新插入节点指针指向原头指针节点 长度+1
        def head_insert(self, value): # 链表头部插入
          node = Node(value)
          if self.head.next == None:
            self.head.next = node
            node.next = None
          else:
            # 插入元素指针域指向原head元素
            tmp_head = self.head.next # 原头指针节点存储到tmp_head
            self.head.next = node # 新head指针指向node
            node.next = tmp_head # 新插入节点指向原头指针节点
          self.length += 1
      

    链表头部删除节点:

    • 依旧是先判断链表是否为空,为空则返回False

      链表不为空时:

      • 头指针指针域(指针域存放下一节点的内存地址,即头指针节点)指向头指针,也就是说链表第一个节点变成了头指针head,由于head不计入链表,所以就相当于删除了第一个节点(有点绕) 同时返回删除的值
    •   def head_del(self): # 删除头结点,返回头结点的值
          if self.head.next == None:
            return False
          else:
            # 头指针指针域指向自己
            self.head = self.head.next
            self.length -= 1
            return self.head.value
      

    链表尾部添加节点:

    • 创建待插入节点对象

      判断链表是否为空,为空则头指针节点就是待插入节点,也是尾节点

      链表不为空:

      • 首先通过while循环(循环条件为节点指针是否为None)找到当前链表的最后一个元素 然后将当前最后一个元素指向待插入节点 长度+1
    •   def append(self, value):  # 链表尾部添加结点
          # 创建新插入的结点对象
          node = Node(value)
          if self.length == 0:
            self.head.next = node  # 只有一个节点,指针指向自己
          else:
            curnode = self.head.next  # 变量curnode存放指针
            while curnode.next != None:
              curnode = curnode.next
            curnode.next = node # 当为最后一个节点时,指针指向新插入节点
          self.length += 1
      

    指定位置后面插入节点:

    • 这里方法接受两个位置参数,index插入位置和value插入值

      依旧创建新节点对象

      判断是否为空

      在链表不为空的条件下:

      • 首先定义一个变量表示当前节点,以及一个index索引比较数i 使用while循环,索引比较数i != index时,更新当前节点 找到索引位置节点后,首先让插入节点指向索引位置节点的下一个节点 然后让索引位置节点指向插入节点 链表长度+1
    • def insert(self, index, value):
      	node = Node(value)
        if self.length == 0:
          self.head.next = node
        else:
          i = 0
          cur_node = self.head.next
          while i != index:
            cur_node = cur_node.next
            i += 1
          node.next = cur_node.next
          cur_node.next = node
        self.length += 1
      

    给定值删除该值节点:

    • 删除链表中给定的值我们需要遍历整个链表,因此需要创建一个可迭代对象

      定义节点迭代方法

      def iter_node(self):
        cur_node = self.head.next	#当前节点
        while cur_node.next != None:	# 对除最后一个节点进行可迭代化处理
          yield cur_node
          cur_node = curnode.next
        if cur_node.next == None:	# 对尾节点进行可迭代化处理
          yield cur_node
      

      重写特殊方法–iter–,用来声明这个类是一个迭代器

      def __iter__(self): # 遍历列表节点
        for node in self.iter_node():
           yield node.value
      

      首先定义一个Flag变量(默认为False),用来表示删除状态

      依旧判断链表是否为空

      链表不为空时:

      • 设置一个前驱节点(当找到需要删除的节点时,先让前驱节点指向删除节点的后继节点) for循环遍历链表
        • 找到符合条件的值就让前驱节点指向,删除节点的后继节点,然后del删除node,Flag更改为True 没找到符合条件的值,就更新前驱节点,继续遍历
    •   def delete_node(self, value):
          Flag = False
          if self.length == 0:
            return False
          else:
            previous_node = self.head  # 初始化前置节点为头结点
            for node in self.iter_node():
              if node.value == value:
                previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
                del node
                self.length -= 1
                Flag = True
              else:
                previous_node = node  # 更新前置节点的值
            return Flag
      

    完整代码:

    # 定义链表节点类
    class Node(object):
      def __init__(self, value=None, next=None):
        self.value = value # 节点元素
        self.next = next  # 指针
    
    
    # 单链表类
    class LinkedList(object):
      def __init__(self):
        self.head = Node() # 创建头结点
        self.length = 0 # 初始化链表长度
    
      def __len__(self):
        return self.length
    
      def __iter__(self): # 遍历列表节点
        for node in self.iter_node():
          yield node.value
    
      def iter_node(self):
        curnode = self.head.next
        while curnode.next != None:
          yield curnode
          curnode = curnode.next
        if curnode.next == None:
          yield curnode
    
      def head_insert(self, value): # 链表头部插入
        node = Node(value)
        if self.head.next == None:
          self.head.next = node
          node.next = None
        else:
          # 插入元素指针域指向原head元素
          tmp_head = self.head.next # 原头指针节点存储到tmp_head
          self.head.next = node # 新head指针指向node
          node.next = tmp_head # 新插入节点指向原头指针节点
        self.length += 1
    
      def head_del(self): # 删除头结点,返回头结点的值
        if self.head.next == None:
          return False
        else:
          # 头指针指针域指向自己
          self.head = self.head.next
          self.length -= 1
          return self.head.value
    
      def append(self, value):  # 链表尾部添加结点
        # 创建新插入的结点对象
        node = Node(value)
        if self.length == 0:
          self.head.next = node  # 只有一个节点,指针指向自己
        else:
          curnode = self.head.next  # 变量curnode存放指针
          while curnode.next != None:
            curnode = curnode.next
          curnode.next = node # 当为最后一个节点时,指针指向新插入节点
        self.length += 1
    	
      # 这里的insert是指定值后面插入不是指定位置
      def insert(self, index, value):
        node = Node(value)
        if self.length == 0:
          self.head.next = node
          self.length += 1
        else:
          for nd in self.iter_node():
            if nd.value == index:  # 如果nd节点值等于index,则插入到nd后
              tmp_node = nd.next # 将nd的指针存放到中间变量
              nd.next = node # nd节点指向插入节点
              node.next = tmp_node  # 插入节点指向原nd.next节点
              self.length += 1
              return True
          return False
    
      def replace(self, old_value, new_value):
        index = 0
        if self.length == 0:
          return False
        else:
          for node in self.iter_node():
            if node == old_value:
              node.value = new_value
              index += 1
        if index != 0:
          return index # 替换节点数量(存在节点值相同情况)
        else:
          return False  # 替换失败,未找到替换值
    
      def delete_node(self, value):
        Flag = False
        if self.length == 0:
          return False
        else:
          previous_node = self.head  # 初始化前置节点为头结点
          for node in self.iter_node():
            if node.value == value:
              previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
              del node
              self.length -= 1
              Flag = True
            else:
              previous_node = node  # 更新前置节点的值
          return Flag
    
    
    
    # 测试
    l = LinkedList()
    l.append(1)
    l.append(2)
    l.append(7)
    l.append(5)
    l.append(6)
    l.append(7)
    l.head_insert(3)
    print("当前链表长度:%s" %l.length)
    #print("删除头结点为:%d"% l.head_del())
    print("当前链表长度:%s" %l.length)
    i = 1
    #l.delete_node(7)
    for node in l:
      print("第%d个链表节点的值: %d"%(i, node))
      i += 1
    

    运行结果:

    当前链表长度:7
    当前链表长度:7
    第1个链表节点的值: 3
    第2个链表节点的值: 1
    第3个链表节点的值: 2
    第4个链表节点的值: 7
    第5个链表节点的值: 5
    第6个链表节点的值: 6
    第7个链表节点的值: 7

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与总结》、《Python编码操作总结》、《Python函数使用总结》、《Python字符串操作汇总》及《Python入门与进阶经典教程》

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

最新资讯
逐鹿“飞行汽车”,通用、小鹏、吉利为何都来了?

逐鹿“飞行汽车”,通用

从这个角度来看,飞行汽车存在成本高企、应用场景有待开
美团互助关停,网络互助行业走到分水岭

美团互助关停,网络互助

这次关停可以理解为是整个网络互助行业的一个分水岭。
俄媒:脸书公司悄悄“解封”特朗普脸书账号和Ins账号

俄媒:脸书公司悄悄“解

“今日俄罗斯”(RT)16日最新消息,脸书公司悄悄恢复了美国
特斯拉首任中国区总经理郑顺景离世 多位好友发文悼念

特斯拉首任中国区总经

特斯拉首任中国区总经理郑顺景离世,原因未知,多位好友已
Jeff Dean万字长文:2020谷歌10大领域AI技术发展

Jeff Dean万字长文:202

2021年已经度过十余天,Jeff Dean也在酝酿后在Google AI
饿了么怎么了?前有骑手猝死后有自焚 在外卖行业已掉队

饿了么怎么了?前有骑手

饿了么进入到了一个尴尬的境地,在被阿里收购后,原饿了么
最新文章
在pycharm中为项目导入anacodna环境的操作方法

在pycharm中为项目导

这篇文章主要介绍了在pycharm中为项目导入anacodna环
tensorflow的ckpt及pb模型持久化方式及转化详解

tensorflow的ckpt及pb

今天小编就为大家分享一篇tensorflow的ckpt及pb模型持
PyTorch笔记之scatter()函数的使用

PyTorch笔记之scatter

这篇文章主要介绍了PyTorch笔记之scatter()函数的使用
python3实现网页版raspberry pi(树莓派)小车控制

python3实现网页版ras

这篇文章主要为大家详细介绍了python3实现网页版raspb
完美解决pycharm导入自己写的py文件爆红问题

完美解决pycharm导入

今天小编就为大家分享一篇完美解决pycharm导入自己写
pycharm内无法import已安装的模块问题解决

pycharm内无法import

今天小编就为大家分享一篇pycharm内无法import已安装