Lista enlazada simple

Instrucciones

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

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

Dada una lista enlazada simple, debes poder invertir la lista para reproducir las canciones en el orden opuesto.

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) que use una lista enlazada simple hecha a medida:

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

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

• Baeldung: estructuras de datos de 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)

Las clases en Python

La implementación «canónica» de una lista enlazada en Python normalmente requiere una o más classes. Para una buena introducción a classes, consulta la classes y el ejercicio complementario ellens-alien-game, o la sección de 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 la documentación de Python: personalización básica de objetos y la documentación de Python: object.len(self).

Cómo construir un iterador

Para poder recorrer tu LinkedList en un bucle o invertirla, 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.

Cómo personalizar y lanzar excepciones

A veces es necesario tanto personalizar como raise excepciones en tu código. 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.

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

Cuando 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 están bajo la clase Exception. Cuando lances el error, igual debes incluir un mensaje significativo.

Este ejercicio en particular 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, las lanzas con raise e incluyes 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.