110 lines
4.1 KiB
Markdown
110 lines
4.1 KiB
Markdown
# 单链表:如何查找和删除一个节点
|
||
|
||
> 原文：<https://www.pythoncentral.io/find-remove-node-linked-lists/>
|
||
|
||
## 先决条件
|
||
|
||
要了解单链表，你应该知道:
|
||
|
||
1. Python 3
|
||
2. OOP 概念
|
||
3. [单链表——插入节点并打印节点](https://www.pythoncentral.io/singly-linked-list-insert-node/)
|
||
|
||
## 我们会学到什么？
|
||
|
||
在上一个教程中，我们讨论了什么是单链表，如何添加一个节点以及如何打印所有的节点。如果您还没有阅读，我们强烈建议您先阅读，因为我们将基于这些概念进行构建。
|
||
|
||
本教程是关于如何删除一个节点，以及如何知道一个特定的元素是否存在于链表中。这两种方法都属于*linked list*类。让我们一个一个来看这些。
|
||
|
||
## 如何找到一个元素？
|
||
|
||
像大多数数据结构一样，找到一个元素是否存在的唯一方法是遍历整个链表。注意，如果链表是排序的，我们可以使用二分搜索法。但是这里我们要考虑一个未排序的链表。其工作方式是，用户给我们一个元素，我们返回 *真* 如果我们找到其他元素，我们返回 *假* 。您也可以使用计数器并返回元素的索引(如果它存在的话)。
|
||
|
||
### 算法
|
||
|
||
1. 设置指针到 *头*
|
||
2. 比较*curr . data*与输入值:
|
||
1. 如果相等，返回 *真*
|
||
2. 否则，移动到下一个指针
|
||
3. 重复步骤 1-2，直到找到元素或到达链表的末尾
|
||
|
||
### 代码
|
||
|
||
```py
|
||
def findNode(self,value):
|
||
|
||
curr = self.head
|
||
while curr:
|
||
if curr.getData() == value:
|
||
return True
|
||
curr = curr.getNextNode()
|
||
return False
|
||
```
|
||
|
||
## 如何从单链表中移除节点？
|
||
|
||
现在你知道如何找到一个节点，我们可以用它来删除一个节点。同样，有几种方法可以做到这一点。您可以删除第一个节点，也可以通过维护一个指向链表最后一个节点的尾指针来删除最后一个节点。我们在这里讨论的方法是，我们从用户那里获得一个值，在链表中找到这个元素，如果它存在，就删除它。让用户知道元素是否被成功移除是非常重要的。为此，我们返回 *真* 为成功，返回 *假* 否则。记得将 *大小* 属性减 1。
|
||
|
||
我们把要删除的节点称为当前节点。其思想是将前一个节点的 next 指向当前节点的下一个节点。例如，假设我们想从给定的链表中删除 4:
|
||
|
||
```py
|
||
Linked list: H-->3-->4-->5
|
||
|
||
Remove 4: H-->3-->5
|
||
```
|
||
|
||
我们让 3 的下一个节点指向 4 的下一个节点，也就是 5。
|
||
|
||
假设我们想要删除 3 个
|
||
|
||
```py
|
||
Remove 3: H-->5
|
||
```
|
||
|
||
我们让头部指针指向 3 的下一个，也就是 5。
|
||
|
||
**注意:**要在当前节点的下一个节点和前一个节点之间建立连接，跟踪前一个节点是很重要的。
|
||
|
||
### 算法
|
||
|
||
1. 有两个指针:
|
||
1. *当前 -* 最初 分 *到 头*
|
||
2. prev - 最初指向*无*
|
||
|
||
2. 如果输入值与*curr*:的数据匹配
|
||
1. 检查 *上一张* 是否存在:
|
||
1. 如果是，则将 *的下一个节点【上一个* 设置为 *的下一个节点*
|
||
2. 如果没有，只需将指向下一个节点(当你想删除第一个节点时就会出现这种情况)
|
||
3. 减量 *大小* 减 1
|
||
4. 返回*真实 *
|
||
3. 如果输入值与*curr*:的数据不匹配
|
||
1. 通过前进到下一个节点
|
||
1. 指向 *前一* 到 *当前*
|
||
2. 将 *当前* 指向 *当前* 的下一个节点
|
||
4. 重复步骤 1-3，直到链表结束
|
||
5. 如果到达链表的末尾，则返回 *False* 表示链表中没有元素匹配输入的值
|
||
|
||
### 代码
|
||
|
||
```py
|
||
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
|
||
```
|
||
|
||
## 结论
|
||
|
||
本教程到此结束。在以后的教程中，我们将会看到如何反转一个单链表。快乐的蟒蛇！ |