Introducción
Estás trabajando en un proyecto para desarrollar un sistema de planificación de trenes para una red ferroviaria muy concurrida.
Se te ha pedido que desarrolles un prototipo para las rutas de tren del sistema de planificación.
Cada ruta consta de una secuencia de estaciones de tren en las que se detiene un tren determinado.
Instrucciones
Tu equipo ha decidido usar una lista doblemente enlazada para representar cada ruta de tren del horario.
Cada estación a lo largo de la ruta del tren estará representada por un nodo de la lista enlazada.
No tienes que preocuparte por las horas de llegada ni de salida de las estaciones.
Cada estación se representará simplemente con un número.
Las rutas se pueden ampliar, añadiendo estaciones al principio o al final de una ruta.
También se pueden acortar eliminando estaciones del principio o del final de una ruta.
A veces se cierra una estación y, en ese caso, hay que eliminarla de la ruta, aunque no esté ni al principio ni al final de esta.
El tamaño de una ruta no se mide por la distancia que recorre el tren, sino por el número de estaciones en las que se para.
La lista enlazada es una estructura de datos fundamental en informática y se usa a menudo en la implementación de otras estructuras de datos.
Como su nombre indica, es una lista de nodos enlazados entre sí.
Es una lista de «nodos», en la que cada nodo se enlaza con su vecino o vecinos.
En una lista simplemente enlazada, cada nodo se enlaza solo con el nodo que le sigue.
En una lista doblemente enlazada, cada nodo se enlaza tanto con el nodo que viene antes como con el que viene después.
Si quieres profundizar en las listas enlazadas, echa un vistazo a este artículo, que las explica con dibujos muy claros.
Cómo está estructurado este ejercicio en Python
Aunque las listas enlazadas se pueden implementar de muchas maneras y con diversas estructuras de datos subyacentes, aquí te pedimos que implementes la tuya con un enfoque de programación orientada a objetos.
En el fichero de plantilla verás el comienzo de una clase Node, además de una clase LinkedList.
Tu clase Node debe llevar un registro de su valor, así como de qué nodos van antes o después.
Los métodos push, pop, shift y unshift, además del método especial para len, deberías implementarlos en la clase LinkedList.
También puede resultarte útil implementar un método especial iter para la iteración.
A diferencia del ejercicio original, vamos a probar condiciones de error llamando a pop y shift sobre LinkedList vacías, así que tendrás que usar raise para lanzar los errores correspondientes.
Por último, nos gustaría que implementaras delete además de los métodos descritos anteriormente.
delete recibirá un argumento: el valor que hay que eliminar de la lista enlazada.
Si el valor aparece más de una vez, solo debe eliminarse la primera aparición.
Mensajes de excepción
A veces es necesario lanzar una excepción. Cuando lo hagas, siempre deberías incluir un mensaje de error significativo que indique cuál es el origen del error.
Esto hace que tu código sea más legible y ayuda mucho a la hora de depurar.
En los casos en los que sepas que el origen del error va a ser de un tipo concreto, puedes optar por lanzar uno de los tipos de error integrados, pero aun así deberías incluir un mensaje significativo.
Este ejercicio en concreto requiere que uses la sentencia raise para «lanzar» un ValueError cuando el valor de un nodo al que se le aplica delete() no se encuentra en la lista enlazada.
Además, debería lanzarse un IndexError si no queda ningún nodo al que hacer pop().
Los tests solo pasarán si lanzas estas exceptions con raise e incluyes mensajes junto a ellas.
Para lanzar un ValueError con un mensaje, escribe el mensaje como argumento del tipo exception:
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Para lanzar un IndexError con un mensaje, escribe el mensaje como argumento del tipo exception:
# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
raise IndexError("List is empty")
Métodos especiales en Python
Los tests de este ejercicio también llamarán a len() sobre tu LinkedLists.
Para que len() funcione, tendrás que crear un método especial __len__.
Para más detalles sobre cómo implementar métodos especiales o «dunder» en Python, consulta Python Docs: Basic Object Customization y Python Docs: object.len(self).
También te recomendamos crear un método especial __iter__ que te ayude a iterar sobre tu lista enlazada.
Fuente
Tema clásico de la informática
