Introdução
Você trabalha em uma empresa de streaming de música.
Você recebeu a tarefa de criar um recurso de playlist para o seu aplicativo de música.
Instruções
Escreva um protótipo do aplicativo de reprodução de música.
Para o protótipo, cada música será simplesmente representada por um número.
Dado um intervalo de números (os IDs das músicas), crie uma lista simplesmente encadeada.
Dada uma lista simplesmente encadeada, você deve conseguir inverter a lista para tocar as músicas na ordem inversa.
A lista encadeada é uma estrutura de dados fundamental na ciência da computação, e costuma ser usada na implementação de outras estruturas de dados.
O tipo mais simples de lista encadeada é a lista simplesmente encadeada.
Isso significa que cada elemento (ou "nó") contém dados, junto com algo que aponta para o próximo nó da lista.
Se você quiser se aprofundar em listas encadeadas, dê uma olhada neste artigo, que explica o assunto com desenhos bem feitos.
Como este exercício é estruturado em Python
Embora stacks e queues possam ser implementadas com lists, collections.deque, queue.LifoQueue e multiprocessing.Queue, este exercício espera uma pilha "Last in, First Out" (LIFO) usando uma lista simplesmente encadeada feita sob medida:
Isso não deve ser confundido com uma pilha LIFO usando um array dinâmico ou uma lista, que pode usar por baixo uma list, uma queue ou um array.
stacks baseadas em array dinâmico têm uma posição de head diferente, assim como complexidade de tempo (Big-O) e consumo de memória diferentes.
Veja estas duas perguntas do Stack Overflow para algumas considerações: Array-Based vs List-Based Stacks and Queues e Differences between Array Stack, Linked Stack, and Stack.
Para mais detalhes sobre listas encadeadas, pilhas LIFO e outros tipos abstratos de dados (ADT) em Python:
Classes em Python
A implementação "canônica" de uma lista encadeada em Python normalmente exige uma ou mais classes.
Para uma boa introdução a classes, veja classes e o exercício complementar ellens-alien-game, ou a seção de classes do Tutorial Oficial de Python.
Métodos especiais em Python
Os testes deste exercício vão chamar len() na sua LinkedList.
Para que len() funcione, você vai precisar criar um método especial __len__.
Para detalhes sobre como implementar métodos especiais, ou "dunder", em Python, veja Python Docs: Basic Object Customization e Python Docs: object.len(self).
Construindo um iterador
Para permitir que você percorra ou inverta sua LinkedList, você vai precisar implementar o método especial __iter__.
Veja como implementar um iterador para uma classe para detalhes de implementação.
Personalizando e lançando exceções
Às vezes é preciso tanto personalizar quanto raise exceções no seu código.
Quando fizer isso, inclua sempre uma mensagem de erro significativa que indique qual é a origem do erro.
Isso deixa seu código mais legível e ajuda bastante na depuração.
Exceções personalizadas podem ser criadas por meio de novas classes de exceção (veja classes para mais detalhes), que normalmente são subclasses de Exception.
Em situações em que você sabe que a origem do erro será uma derivada de um certo tipo de exceção, você pode escolher herdar de um dos built in error types sob a classe Exception.
Ao lançar o erro, você ainda deve incluir uma mensagem significativa.
Este exercício em particular exige que você crie uma exceção personalizada para ser lançada/"disparada" quando sua lista encadeada estiver vazia.
Os testes só vão passar se você personalizar as exceções adequadas, fizer o raise dessas exceções e incluir mensagens de erro adequadas.
Para personalizar uma exceção genérica, crie uma class que herde de Exception.
Ao lançar a exceção personalizada com uma mensagem, escreva a mensagem como argumento do 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.")
