当前位置:首页 >> 脚本专栏

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程序设计有所帮助。