I want to implement a method that accepts as a parameter a value that must be removed from the list. The method will remove all nodes that have a value equal to the one passed as a parameter.
I have carried out several test tests but I always get an error in it, and it is that more nodes than expected are traversed
Method I want to implement
def eliminar(self, value):
prev_node = None
current_node = self.__first
i = 0
while i <= self.__len:
i += 1
if current_node == None:
break
elif current_node.value == value:
if prev_node is None:
self.__first = current_node.next_node
elif current_node.next_node is None:
prev_node.next_node = None
self.__len -= 1
break
else:
prev_node.next_node = current_node.next_node
self.__len -= 1
elif prev_node == current_node:
current_node = current_node.next_node
else:
if current_node.value > value:
break
To remove all nodes you must iterate through the list , either by iteration or by recursion.
If the node to remove is the first node we just need to reassign to
__first
the next node. Just like you already do in your code.If the node to delete is the last node we only have to assign the previous (penultimate) node as
next_node
the valueNone
. For this we need a reference to the previous node, which in a simply linked list we don't have... Later we will see how.If we have to remove an intermediate node, we must assign the attribute
next_node
of the previous node the value ofnext_node
the current node.The problem we face is that we need a reference to the previous node in case the node to delete is not the first one. In a doubly linked list this is trivial, each node has references to the previous and next node. In this case, we only have the reference to the next. The key is to use a local variable in the method
delete
that always points to the previous node to the one being checked, initially it will beNone
(since the first node does not have a previous node), as we iterate we will be reassigned without further ado.If the list is ordered, we can optimize by adding a short circuit, as soon as a node has a value greater than the value to be eliminated, we simply stop iterating.
To give a reproducible example, I'm going to reuse the code from the previous question:
or using a loop
while
:Full reproducible code:
the idea would be the same, you would only have to modify the name of the attributes.