当前位置:Gxlcms > Python > python单链表中如何查找和删除节点?

python单链表中如何查找和删除节点?

时间:2021-07-01 10:21:17 帮助过:70人阅读

在之前的文章【python单链表中如何插入和输出节点?】中给大家介绍了单链表是什么,以及如何进行添加节点、输出所以节点。下面本篇文章给大家介绍如何查找和删除节点,希望对大家有所帮助。

如何从单链表中查找节点?

与大多数数据结构一样,查找元素是否存在的唯一方法是遍历整个链表。请注意,如果链接列表已排序,我们可以使用二进制搜索。但是在这里我们将考虑一个未排序的链表。

工作原理:用户给定需要查找的节点元素,如果我们找到元素,我们返回true,否则返回false;还可以使用计数器并返回元素的索引(如果存在)。

算法

1、将指针curr设置为头部

2、将curr.data与输入值进行比较:

● 如果相等,则返回True

● 否则,转到下一个指针

3、重复步骤1-2,直到找到元素或满足链接列表的结尾

实现代码:

def findNode(self,value):
       curr = self.head
       while curr:
           if curr.getData() == value:
               return True
           curr = curr.getNextNode()
       return False

如何从单链表中删除节点?

从上面的示例中我们知道了如何查找节点,那么我们可以利用它来删除节点。我们可以从用户那里获取一个值,在链接列表中找到该元素,如果它存在,就将其删除。

注:让用户知道元素是否被成功删除是非常重要的。因而,当删除成功就返回True,否则返回False;请记住将size属性减1。

让我们将要删除的节点称为当前节点。其思想是将前一个节点的next链接到当前节点的next节点。例如,假设我们要从给定的链接列表中删除4:

原链表: H-->3-->4-->5 
删除4后:H-->3-->5

我们需要将3的下一个节点指向4的下一个节点,即5。

假设我们还要删除3

删除3后:H-->5

注:要在上一个节点和当前节点的下一个节点之间建立连接,请务必跟踪上一个节点。

算法

1、有两个指针:

● CURR - 最初 分给头

● prev - 最初指向无

2、如果输入的值与curr的数据匹配,检查prev存在:

● 如果是,则将prev的下一个节点设置为curr的下一个节点

● 如果不是,只需将头部指向curr的下一个节点(当您要删除第一个节点时会发生这种情况)

● 将size属性减1

● 返回True

3、如果输入的值与curr的数据不匹配,通过以下方式前往下一个节点:

● 指向先前的曲线

● 指着CURR到下一个节点CURR

4、重复步骤1-3直到链表结束

5、如果到达链接列表的末尾,则返回False,表示链接列表中没有元素与输入的值匹配

实现代码:

def removeNode(self,value):
        prev = None
        curr = self.head
        while curr:
            if curr.getData() == value:
                if prev:
                    prev.setNextNode(curr.getNextNode())
                else:
                    self.head = curr.getNextNode()
                return True
                    
            prev = curr
            curr = curr.getNextNode()
            
        return False

相关视频教程推荐:《python3教程》

以上就是本篇文章的全部内容,希望能对大家的学习有所帮助。更多精彩内容大家可以关注Gxl网相关教程栏目!!!

以上就是python单链表中如何查找和删除节点?的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行