2

Buenos días quiero implementar en la clase SortedLinkedList un método que admita como parámetro un valor a insertar en la lista. El valor se insertará en orden, de forma que se inserte, después de todos los que sean menores y justo antes de los que sean mayores o iguales. La lista permanecerá ordenada de menor a mayor en todo momento.

Este primer módulo genera la lista, por tanto en el método que quiero implementar no tengo que crear ninguna lista

import random

from sortedlinkedlist import SortedLinkedList

if __name__ == "__main__":
    my_slist = SortedLinkedList()

    for i in range(10):
        my_slist.insert(random.randint(10, 100))

    for item in my_slist:
        print(item)

En este segundo módulo se encuentra una serie de métodos qe tratan las listas encadenadas y no deben ser modificados porque he comprobado que funcionan

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 != None:
            result = self.__current.value
            self.__current = self.__current.next_node
            return result
        else:
            raise StopIteration

A continuación va el método que quiero implementar. Esto es lo que he intentado

def insert(self, value):
        if value == 0:
            self.insert_as_first(value)
        elif value == len(self):
            self.append(value)
        elif value < 0 or value > len(self):
            raise IndexError
        else:
            current = self.__first
            current_pos = 1

            while current_pos < value:
                current = current.next_node
                current_pos += 1

            current.next_node = self.Node(value, current.next_node)
            self.__len += 1

1 respuesta 1

2

Cuando vas a insertar un nuevo nodo en la lista podemos tener una de estas situaciones:

♦ La lista está vacía

Por lo tanto self.__first es None y self.__len es 0. En este caso simplemente tenemos que crear una nueva instancia de Node y asignarlo a self.__first.

♦ El valor a ingresar es menor que el valor del primer nodo de la lista

En este caso nuestro nuevo nodo debe pasar a ser el primero:

introducir la descripción de la imagen aquí

Para ello hacemos:

  1. Instanciamos un nuevo Nodo y le asignamos a su atributo next_node el nodo asociado a self.__first hasta ahora, el que era el primer nodo de la lista.
  2. Después reasignamos a self.__first nuestro nuevo nodo para que pase a ser el primero.

♦ Nada de lo anterior ocurre

En este caso el nodo debe ser insertado entre otros nodos o al final de la lista. Por tanto debemos iterar sobre la misma hasta encontrar la posición en la que nuestro nuevo nodo quedaría ordenado:

  • Si encontramos un nodo con valor menor al que queremos agregar pero cuyo siguiente nodo tiene un valor superior o igual, debemos insertar el nuevo nodo entre ambos.

    introducir la descripción de la imagen aquí

    Esto se haría en dos pasos:

    1. Asignamos al atributo next_node de nuestro nuevo nodo el nodo siguiente al que estamos en ésta iteración (el primero nodo de la lista cuyo valor es mayor o igual al valor de nuestro nodo nuevo)
    2. Reasignamos al atributo next_node del nodo actual de la iteración, el último cuyo valor es menor a nuestro nuevo nodo, la instancia del nodo recién creado.
  • Si llegamos a un nodo en el que el nodo que le sigue es None (último nodo de la lista) solo tenemos que asignarle al atributo next_node de éste nodo nuestro nuevo nodo, que pasará a ser el último.

    introducir la descripción de la imagen aquí

Tu método podría quedar algo así:

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
        while True:
            if current_node.next_node is None:
                current_node.next_node = item
                break
            elif 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
    self.__len += 1

Otra posibilidad es usar un for in - else con range aprovechando que nuestra lista implementa len:

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

Al evitar dos comparaciones la inserción es algo más eficiente.

No uses los operadores de igualdad/desigualdad (==/!=) para saber si una variable está asociada a None, None es un singleton, la forma correcta es usar el operador de identidad (is/is not):

3
  • Tenía un pequeño problema con el código. He realizado pruebas para dicho bloque de código y obtengo los siguientes fallos. Si trato de insertar un elemento menor que los existentes obtengo que: La longitud de lista resultante es incorrecta: 7 Se esperaba: 6. Asi mismo, obtengo esta otra excepción si trato de Insertar un elemento en una lista vacía. La longitud de lista resultante es incorrecta: 2 Se esperaba: 1 Commented el 10 abr. 2020 a las 14:53
  • 1
    Hola @LearningDeveloper, tenía un "pequeño" error al sumar a __len, en su momento modifiqué el código sacando el incremento de los condicionales, pero se me pasó eliminar la línea de los dos primeros (if y else) lo que hacía que se incrementara en dos si el item a insertar es el menor o no existen items en la lista. Corregido, gracias por el aviso y perdón por el despiste :(
    – FJSevilla
    Commented el 10 abr. 2020 a las 15:07
  • 1
    Muchas gracias nuevamente por su tiempo y ayuda. El código pasa todos los test. No me había percatado de ese despiste y pensé que era fallo de los test o algo. Muchas gracias por todo y no pasa nada por el despiste, faltaría más :) Commented el 10 abr. 2020 a las 15:17

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.