单链表python基本操作,python顺序表和链表

  单链表python基本操作,python顺序表和链表

  本文主要详细介绍python链表的基本概念和用法。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。

  本文分享python链表的基本概念和用法,供大家参考。具体情况如下

  

一、什么是链表

  链表由许多不同的节点组成,每个节点通过一个指针区域链接在一起。

  链表的头指针指向头节点,通过它可以找到其他节点信息。

  

二、什么是节点

  它由链表节点组成,每个节点包含两个部分,一个是元素区,一个是指针区。

  元素存储当前节点的值,指针区域指向下一个节点的对象。在C语言中,指针应该是下一个元素的内存地址。因为python中不研究指针,所以用下一个节点的对象来代替。这样就可以通过指针区找到下一个节点的信息,从而得到下一个节点的值。

  

三、为什么引入链表的概念

  1.先说数组的数据结构。数组是一个大的连续内存空间。每次初始化都需要开辟很大的内存空间,所以空间利用率比较低。链表不一样。链表的节点可以随机分布在任意位置,只需要指针穿透就可以了。

  2.在连续存储空间中,当插入一个元素时,所有其他元素的位置也会改变。在插入和删除元素时,效率较低。

  链表是一个不连续的内存空间,每个节点都有自己的内存空间,通过指针指向下一个节点。

  如果您在某处插入一个节点,您只需要改变指针的方向,而不需要改变所有其他元素。

  

四、链表的基本操作

  #实现头插入和尾插入,根据索引插入和删除节点并打印。

  #定义一个节点

  类别节点:

  def __init__(self,data):

  self.data=数据

  self.next=无

  类SingleLinkList:

  def __init__(self):

  self.head=无

  self.tail=无

  定义为_空(自身):

  “”链表为空吗?

  :返回:

  回归自我。头是无

  定义长度(自身):

  查找当前链表的长度

  :返回:

  计数=0

  cur=self.head

  虽然cur不是None:

  计数=1

  下一个

  返回计数

  def insert_head_node(自身,数据):

  将元素添加到“”链接列表的开头

  :参数数据:要保存的数据

  :返回:

  节点=节点(数据)

  node.next=self.head

  self.head=node

  def append_node(自身,数据):

  有很多方法可以在链表的末尾添加元素。

  :参数数据:

  :返回:

  #第一种方法是时间复杂度为O(n)的处理方法

  节点=节点(数据)

  #如果链表为空,则需要特殊处理

  if self.is_empty():

  self.head=node

  else:

  cur=self.head

  而cur.next不是None:

  下一个

  #退出循环时,cur指向尾节点。

  cur.next=node

  #第二种方法是引入尾指针。默认情况下,当前的链表是一个空的链表,它一直指向追加节点。

  # node=节点(数据)

  # if self.is_empty(): #第一次向空链表中添加节点时,头指针和尾指针同时指向新节点。

  # self.head=node

  # self.tail=node

  # else:

          # 当再次添加节点到链表中的时候, 头指针始终指向头节点,尾指针始终执行未节点,如果一直向未节点追加节点,只需移动tail指针即可

          #     self.tail.next = node

          #     self.tail = node

      def insert_node(self, pos, data):

          """指定位置添加元素

          :param pos:

          :param data:

          :return:

          """

          # 1, 在头部添加

          if pos <= 0:

              self.insert_head_node(data)

          # 2, 在尾部添加

          elif self.length() >= pos:

              self.append_node(data)

          # 3, 指定位置添加

          else:

              count = 0

              while count < (pos - 2):

                  count += 1

                  self.head = self.head.next

              # 这时候self.head 表示当前插入前一个节点

              # self.head.next 表示当前插入的后一个节点

              node = Node(data)

              self.head.next = node

              node.next = self.head.next

      def delete_node(self, data):

          """删除节点

          :param data:

          :return:

          """

          cur = self.head     # 记录当前节点的位置

          pre = None          # 记录当前节点位置的前置节点

          while cur is not None:

              # 找到了要删除的元素

              if cur.data == data:

                  # 在头部找到了要删除的元素

                  if cur == self.head:

                      self.head = cur.next

                      return True

                  else:

                      pre.next = cur.next

                      return True

              else:

                  # 不是要找的元素, 移动光标

                  pre = cur

                  cur = cur.next

      def search_node(self, data):

          """查找节点是否存在

          :return:

          """

          cur = self.head

          while cur is not None:

              if cur.data == data:

                  return True

              cur = cur.next

          return False

      def reveres_node(self):

          """链表反转

          :return:

          """

          if self.is_empty():

              return

          j = 0

          while j < self.length() - 1:

              cur = self.head

              for i in range(self.length() - 1):

                  cur = cur.next

                  if cur.next is None:

                      x = cur.data

                      self.delete_node(cur.data)

                      self.insert_node(j, x)

              j += 1

          return self.head

  以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

相关文章阅读

  • python基本数据类型详细介绍怎么写,python基本数据类型详细介绍图
  • python基本数据类型详细介绍怎么写,python基本数据类型详细介绍图,Python基本数据类型详细介绍
  • 简述python的输入和输出函数,Python基本输入输出通过哪些语句来实现
  • python基本统计值计算总结,python基本统计值计算代码
  • python的模块和包,python基本模块中的对象
  • python基本的内置函数,说明python中内置函数的运用
  • 什么是Python基本数据类型-基本数据类型有几种-,python里你常用的基本数据类型有哪些-
  • python怎么实现链表,单链表python基本操作
  • python中数学函数都有哪些,python基本函数有哪些
  • Python基本输入输出,python中输入和输出的用法
  • python基本变量类型,简单介绍python中的数据类型
  • python基本语句有哪些,python最基本的语法
  • python的基本数据类型,Python基本数据类型
  • python的数字有几种类型,python基本数据类型
  • python基本输入和输出,在Python中常用输入输出语句分别是
  • 留言与评论(共有 条评论)
       
    验证码: