怎样从单链表中查找节点?
与大多数数据结构一样,查找元素是不是存在的唯一要领是遍历全部链表。请注意,假如链接列表已排序,我们能够运用二进制搜刮。然则在这里我们将斟酌一个未排序的链表。
事情道理:用户给定须要查找的节点元素,假如我们找到元素,我们返回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教程》
以上就是本篇文章的全部内容,愿望能对人人的进修有所协助。更多精彩内容人人能够关注ki4网相干教程栏目!!!
以上就是python单链表中怎样查找和删除节点?的细致内容,更多请关注ki4网别的相干文章!