Lista enlazada simple

Instrucciones

Escribe un prototipo de la aplicación de reproductor de música.

Para el prototipo, cada canción se representará simplemente con un número. Dado un rango de números (los identificadores de las canciones), crea una lista enlazada simple.

Dada una lista enlazada simple, deberías poder invertir la lista para reproducir las canciones en el orden inverso.

Cómo está estructurado este ejercicio en Python

Aunque las stacks y las queues se pueden implementar con lists, collections.deque, queue.LifoQueue y multiprocessing.Queue, este ejercicio espera una pila "último en entrar, primero en salir" (LIFO) usando una lista enlazada simple hecha a medida:

Esto no debe confundirse con una pila LIFO que use un array dinámico o una list, que puede usar por debajo una list, una queue o un array. Las stacks basadas en arrays dinámicos tienen una posición de head distinta, además de una complejidad temporal (Big-O) y un consumo de memoria diferentes.

Consulta estas dos preguntas de Stack Overflow para ver algunas consideraciones: Pilas y colas basadas en arrays frente a basadas en listas enlazadas y Diferencias entre pila de array, pila enlazada y pila. Para más detalles sobre las listas enlazadas, las pilas LIFO y otros tipos de datos abstractos (ADT) en Python:

• Baeldung: estructuras de datos con listas enlazadas (cubre varias implementaciones)
• Geeks for Geeks: pila con lista enlazada
• Mosh sobre estructuras de datos abstractas (cubre muchos ADT, no solo listas enlazadas)

Clases en Python

La implementación "canónica" de una lista enlazada en Python suele requerir una o más classes. Para una buena introducción a las classes, consulta classes y el ejercicio complementario ellens-alien-game, o la sección sobre clases del tutorial oficial de Python.

Métodos especiales en Python

Los tests de este ejercicio 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).

Crear un iterador

Para poder recorrer con un bucle o invertir tu LinkedList, tendrás que implementar el método especial __iter__. Consulta cómo implementar un iterador para una clase para ver los detalles de implementación.

Personalizar y lanzar excepciones

A veces es necesario tanto personalizar como raise excepciones en tu código. Cuando lo hagas, deberías incluir siempre 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.

Las excepciones personalizadas se pueden crear mediante nuevas clases de excepción (consulta classes para más detalles) que normalmente son subclases de Exception.

En situaciones en las que sepas que el origen del error será una derivada de cierto tipo de excepción, puedes optar por heredar de uno de los built in error types que hay bajo la clase Exception. Al lanzar el error, deberías seguir incluyendo un mensaje significativo.

Este ejercicio en concreto requiere que crees una excepción personalizada que se lance («arroje») cuando tu lista enlazada esté vacía. Los tests solo pasarán si personalizas las excepciones adecuadas, lanzas esas excepciones con raise e incluyes los mensajes de error adecuados.

Para personalizar una excepción genérica, crea una class que herede de Exception. Cuando lances la excepción personalizada con un mensaje, escribe el mensaje como argumento del tipo exception:

# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
    """Exception raised when the linked list is empty.

    message: explanation of the error.

    """
    def __init__(self, message):
        self.message = message

# raising an EmptyListException
raise EmptyListException("The list is empty.")

---

Fuente

Inspirado en «Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby», listas enlazadas simples.