2

Quiero implementar un método que admita como parámetro un valor que debe ser eliminado de la lista. El método eliminará todos los nodos que tengan un valor igual al pasado como parámetro.

He realizado varios test de prueba pero siempre obtengo un fallo en el mismo, y es que Se recorren más nodos de los esperados

Método que quiero implementar

   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

1 respuesta 1

1

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.

6
  • 1
    Si, es lo mismo, pero solo es cierto mientras current_node sea self.__first, en las siguientes iteraciones esto puede o no puede ser así dependiendo de si seguimos iterando por los nodos intermedios o no, ene estos casos current_node apuntará a otro nodo de la lista que no es el primero, esto ocurre en current_node = current_node.next_node
    – FJSevilla
    Commented el 14 abr. 2020 a las 10:14
  • 1
    En cuanto a o segundo, si, puedes hacerlo sin problemas. Lo normal sería que la claase Node no se definiera dentro de la clase de la lista, pero esto es otro tema.
    – FJSevilla
    Commented el 14 abr. 2020 a las 10:17
  • 1
    Para aclarar lo primero mas, current_node representa en todo momento el nodo que en esa iteración estamos evaluando (viendo si su valor es o no igual al valor a eliminar). Cuando comenzamos a iterar sobre la lista debemos hacerlo por el primer nodo, por eso la asignación current_node = self.__first. Posteriormente current_node irá haciendo referencia a los otros nodos de la lista según iteremos sobre ella. Por cierto, aclarar que if prev_node is None se puede cambiar por if current_node is self.__first si te parece más claro.
    – FJSevilla
    Commented el 14 abr. 2020 a las 10:29
  • 1
    @LearningDeveloper ¿podrías agregar los test? Valor de los nodos insertados y nodos que intenta eliminar o algo para poder reproducir el problema al menos. He hecho varios tests con números negativos, positivos, floats e int, con una o varias repeticiones y no he encontrado fallo alguno. Para descartar ¿No lo éstas intentado usar con una lista sin ordenar u ordenada de mayor a menor? ¿Es mi código tal como está en el último ejemplo el que te falla o una implementación basada en el mismo?
    – FJSevilla
    Commented el 21 abr. 2020 a las 17:12
  • 1
    Si la lista se implementa de forma diferente el método debe adaptarse, si no es una lista ordenada ascendente también. (hay un comentario en el código indicando que el primer if debe eliminarse si la lista no es ordenada). Agrega los ejemplos en los que falla para ver si podemos dar con lo que está pasando y poder corregir la respuesta si hay verdaderamente algún fallo. Un saludo.
    – FJSevilla
    Commented el 21 abr. 2020 a las 17:12

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.