Para eliminar todos los nodos debes recorrer la lista, bien mediante iteración o mediante recursión.
Si el nodo a eliminar es el primero solo necesitamos reasignar a __first
el nodo siguiente. Tal como ya haces en tu código.
Si el nodo a eliminar es el último solo tenemos que asignar al nodo anterior (penúltimo) como next_node
el valor None
. Para ello necesitamos una referencia al nodo anterior, que en una lista simplemente enlazada no tenemos... Luego veremos como.
Si tenemos que eliminar un nodo intermedio, debemos asignar al atributo next_node
del nodo anterior el valor de next_node
del nodo actual.
El problema que se nos plantea es que necesitamos una referencia al nodo anterior en el caso de que el nodo a eliminar no sea el primero. En una lista doblemente enlazada esto es trivial, cadas nodo tiene referencias al nodo anterior y siguiente. En este caso, solo tenemos la referencia al siguiente. La clave es usar una variable local en el método delete
que apunte siempre al nodo anterior al que se está comprobando, inicialmente será None
(dado que el primer nodo no tiene un nodo anterior), según iteremos vamos reasignado sin más.
Si la lista está ordenada podemos optimizar agregando un cortocircuito, en el momento que un nodo tenga un valor mayor al valor a eliminar dejamos de iterar sin más.
Para dar un ejemplo reproducible, voy a reutilizar el código de la anterior pregunta:
def delete(self, value):
prev_node = None
current_node = self.__first
for _ in range(self.__len):
# Solo si la lista es una lista ordenada ascendente
if current_node.value > value:
break
elif current_node.value == value:
if prev_node is None:
self.__first = current_node.next_node
else:
prev_node.next_node = current_node.next_node
self.__len -= 1
else:
prev_node = current_node
current_node = current_node.next_node
o usando un ciclo while
:
def delete(self, value):
prev_node = None
current_node = self.__first
while current_node is not None and (current_value:= current_node.value) <= value:
if current_value == value:
if prev_node is None:
self.__first = current_node.next_node
else:
prev_node.next_node = current_node.next_node
self.__len -= 1
else:
prev_node = current_node
current_node = current_node.next_node
Código completo reproducible:
class SortedLinkedList:
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
def __init__(self):
self.__first = None
self.__len = 0
def __len__(self):
return self.__len
def __iter__(self):
self.__current = self.__first
return self
def __next__(self):
if self.__current is not None:
result = self.__current.value
self.__current = self.__current.next_node
return result
else:
raise StopIteration
def insert(self, value):
item = self.Node(value)
if self.__first is None:
self.__first = item
elif self.__first.value > value:
self.__first, item.next_node = item, self.__first
else:
current_node = self.__first
for _ in range(self.__len - 1):
if current_node.next_node.value >= value:
item.next_node = current_node.next_node
current_node.next_node = item
break
current_node = current_node.next_node
else:
current_node.next_node = item
self.__len += 1
def delete(self, value):
prev_node = None
current_node = self.__first
for _ in range(self.__len):
if current_node.value > value:
break
elif current_node.value == value:
if prev_node is None:
self.__first = current_node.next_node
else:
prev_node.next_node = current_node.next_node
self.__len -= 1
else:
prev_node = current_node
current_node = current_node.next_node
if __name__ == "__main__":
my_slist = SortedLinkedList()
for i in range(10):
my_slist.insert(i)
my_slist.insert(i)
print(len(my_slist))
for item in my_slist:
print(item)
print("\nEl 0 eliminado")
my_slist.delete(0)
for item in my_slist:
print(item)
print("\nEl 7 eliminado")
my_slist.delete(7)
for item in my_slist:
print(item)
print("\nEl 9 eliminado")
my_slist.delete(9)
for item in my_slist:
print(item)
la idea sería la misma, solo tendrías que modificar el nombre de los atributos.