How to find and delete nodes in python singly linked list?

In the previous article [How to insert and output nodes in a singly linked list in python? ] introduces to you what a singly linked list is, and how to add nodes and output all nodes. The following article will introduce how to find and delete nodes. I hope it will be helpful to you.

How to find a node from a singly linked list?

As with most data structures, the only way to find out whether an element exists is to traverse the entire linked list. Note that we can use binary search if the linked list is sorted. But here we will consider an unsorted linked list.

Working principle: The user gives the node element that needs to be found. If we find the element, we return true, otherwise we return false; you can also use a counter and return the index of the element (if it exists).

Algorithm

1. Set the pointer curr to the head

2. Compare curr.data with the input value:

●　If equal, return True

● Otherwise, go to the next pointer

3. Repeat steps 1-2 until the element is found or the end of the linked list is met

Implementation code:

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

How to delete nodes from a singly linked list?

From the above example we know how to find nodes, then we can use it to delete nodes. We can get a value from the user, find the element in the linked list, and remove it if it exists.

Note: It is very important to let the user know whether the element was successfully deleted. Therefore, it returns True when the deletion is successful, otherwise it returns False; please remember to decrement the size attribute by 1.

Let us call the node to be deleted the current node. The idea is to link the next node of the previous node to the next node of the current node. For example, suppose we want to remove 4 from the given linked list:

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

We need to point the next node of 3 to the next node of 4, which is 5.

Suppose we also delete 3

删除3后：H-->5

Note: To establish a connection between the previous node and the node next to the current node, be sure to keep track of the previous node.

Algorithm

1. There are two pointers:

● CURR - initially assigned to the header

● prev - initially pointed to None

2. If the entered value matches the data of curr, check the existence of prev:

● If so, set the next node of prev to the next node of curr

●●If not, just point the head to the next node of curr (this happens when you want to delete the first node)

●●Decrease the size attribute by 1

● Return True

3. If the input value does not match the data of curr, go to the next node in the following way:

● Point to the previous curve

● Point CURR to the next node CURR

4. Repeat steps 1-3 until the end of the linked list

5. If the end of the linked list is reached, False is returned, indicating that there are no elements in the linked list with The input value matches

Implementation code:

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

Related video tutorial recommendation: "python3 tutorial"

The above is this The entire content of this article, I hope it will be helpful to everyone's study. For more exciting content, you can pay attention to the relevant tutorial columns of the PHP Chinese website! ! !

The above is the detailed content of How to find and delete nodes in python singly linked list?. For more information, please follow other related articles on the PHP Chinese website!