python单链表中如何查找和删除节点？-木庄网络博客

本文摘自php中文网，作者青灯夜游，侵删。

在之前的文章【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：

1 2	`原链表： H-->3-->4-->5` `删除4后：H-->3-->5`

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

假设我们还要删除3

1	`删除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