从链表节点定义中删除的节点会不会保留数据并使计算机的处理

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

思路: 最容易想到的是遍历链表节点定义,将数据域为val的节点删除但是,单链表節点定义一涉及删除那么就得找到待删除节点的前驱节点,然而第一个节点没有前驱节点当val恰为第一个节点的数据域时,这时就要做絀不同的操作


 
 
 
 
 

思路: 既然知道删除没有头节点的节点需要用别的方法,那么创建一个虚拟头节点使所有节点都有头节点,就可以用同┅种方法解决了


 
 

思路: 将一个链表节点定义看为head,和head.next两部分先删除head.next链表节点定义中等于给定值 val 的所有节点后,在判断head节点是否要被删除


 
  • 链表节点定义(Linked List)是由许多相同數据类型的数据项按照特定顺序排列而成的线性表
  • 链表节点定义中个数据项在计算机内存中的位置是不连续且随机的,数组在内存中是連续的
  • 链表节点定义数据的插入和删除很方便,但查找数据效率低下不能像数组一样随机读取数据。
  • 一个单向链表节点定义的节点由數据字段和指针组成指针指向下一个元素所在内存地址

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

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

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

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

  • 链表节点定义初始化之后开始定义链表节点定义方法

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

    • 判断当前链表节点定义是否为空链表节点定义,链表节点定义为空:

      • 插入节点既是链表节点定义头指针指向的节点也是尾節点(指向None)
      • 待插入节点指向原头指针节点头指针重新指向待插入节点
      • 首先需要将原头指针结点,存放到临时变量中(防止head指针变更时指针斷裂导致数据丢失,链表节点定义中指针就是连接的纽带其中某个纽带断裂(即指针指向其他)则后续数据都将丢失)
      • 将头指针指向新插入节點
      • 新插入节点指针指向原头指针节点
    • 依旧是先判断链表节点定义是否为空,为空则返回False

      • 头指针指针域(指针域存放下一节点的内存地址即頭指针节点)指向头指针,也就是说链表节点定义第一个节点变成了头指针head由于head不计入链表节点定义,所以就相当于删除了第一个节点(有點绕)
    • 判断链表节点定义是否为空为空则头指针节点就是待插入节点,也是尾节点

      • 首先通过while循环(循环条件为节点指针是否为None)找到当前链表節点定义的最后一个元素
      • 然后将当前最后一个元素指向待插入节点
  • 指定位置后面插入节点:

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

    • 在链表节点定义不为空的条件下:

      • 首先定义一个变量表示当前节点,以及一个index索引比较数i
      • 使用while循环索引比较数i != index时,更新当前节点
      • 找到索引位置节点后首先让插入节点指向索引位置节点的下一个节点
      • 然后让索引位置节点指向插入节点
    • 删除链表节点定义中给定的值我们需偠遍历整个链表节点定义,因此需要创建一个可迭代对象

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

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

      • 设置一个前驱节点(当找到需要删除的节点时先让前驱节点指向删除节点的后继节点)
        • 找到符合条件的值就让前驱节点指向,删除节点的后继节点然后del删除node,Flag更改为True
        • 没找到符合条件的值就更新前驱节点,继续遍历
  • 
     
     
     
     
     
    

我要回帖

更多关于 链表节点定义 的文章

 

随机推荐