Introducción
Estás trabajando en un proyecto para desarrollar un sistema de programación de trenes para una red ferroviaria muy transitada.
Te han pedido que desarrolles un prototipo para las rutas de trenes del sistema de programación.
Cada ruta consiste en una secuencia de estaciones de tren en las que se detiene un tren en particular.
Instrucciones
Tu equipo ha decidido usar una lista doblemente enlazada para representar cada ruta de tren en el horario.
Cada estación a lo largo de la ruta del tren se representará con un nodo en la lista enlazada.
No necesitas preocuparte por los horarios de llegada y salida en las estaciones.
Cada estación simplemente se representará con un número.
Las rutas se pueden extender agregando estaciones al principio o al final de una ruta.
También se pueden acortar quitando estaciones del principio o del final de una ruta.
A veces se cierra una estación y, en ese caso, hay que quitarla 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 la cantidad de estaciones en las que se detiene.
La lista enlazada es una estructura de datos fundamental en las ciencias de la computación, y a menudo se usa para implementar otras estructuras de datos.
Como su nombre lo indica, es una lista de nodos que están enlazados entre sí.
Es una lista de «nodos», donde cada nodo se enlaza con su vecino o sus vecinos.
En una lista simplemente enlazada, cada nodo se enlaza solo con el nodo que lo sigue.
En una lista doblemente enlazada, cada nodo se enlaza tanto con el nodo que está antes como con el que está 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 con distintas estructuras de datos subyacentes, aquí te pedimos que implementes tu lista enlazada con un enfoque de programación orientada a objetos.
En el archivo inicial verás el comienzo de una clase Node, así como una clase LinkedList.
Tu clase Node debe llevar un registro de su valor, así como de qué nodos la preceden o la siguen.
Tus métodos push, pop, shift y unshift, y el método especial para len, deben implementarse en la clase LinkedList.
También puede resultarte útil implementar un método especial iter para la iteración.
A diferencia del ejercicio principal, probaremos condiciones de error llamando a pop y shift sobre LinkedLists vacías, así que tendrás que lanzar los errores con raise como corresponda.
Por último, nos gustaría que implementes delete además de los métodos descritos anteriormente.
delete recibirá un argumento, que es el valor que se va a eliminar de la lista enlazada.
Si el valor aparece más de una vez, solo se debe eliminar la primera aparición.
Mensajes de excepción
A veces es necesario lanzar una excepción. Cuando lo hagas, siempre debes 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 que sepas que el origen del error será de cierto tipo, puedes optar por lanzar uno de los tipos de error integrados, pero aun así debes incluir un mensaje significativo.
Este ejercicio en particular requiere que uses la sentencia raise para «lanzar» un ValueError cuando el valor de un nodo que se está eliminando con delete() no se encuentre en la lista enlazada.
Además, se debe lanzar un IndexError si no quedan nodos para hacer pop().
Las pruebas solo pasarán si lanzas estas exceptions con raise y además incluyes mensajes con 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
Las pruebas de este ejercicio también llamarán a len() sobre tu LinkedList.
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 Documentación de Python: Personalización básica de objetos y Documentación de Python: 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 las ciencias de la computación
