Introdução
Trabalhas numa empresa de streaming de música.
Deram-te a tarefa de criar uma funcionalidade de playlists para o teu reprodutor de música.
Instruções
Escreve um protótipo da aplicação de leitor de música.
Para o protótipo, cada música será representada apenas por um número.
Dado um intervalo de números (os IDs das músicas), cria uma lista simplesmente ligada.
Dada uma lista simplesmente ligada, deves conseguir inverter a lista para reproduzir as músicas pela ordem inversa.
A lista ligada é uma estrutura de dados fundamental na informática, usada frequentemente na implementação de outras estruturas de dados.
O tipo mais simples de lista ligada é a lista simplesmente ligada.
Isso significa que cada elemento (ou «nó») contém dados, a par de algo que aponta para o nó seguinte da lista.
Se quiseres aprofundar os teus conhecimentos sobre listas ligadas, espreita este artigo, que explica tudo com uns desenhos muito bons.
Como este exercício está 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 "o último a entrar, o primeiro a sair" (LIFO) que usa uma lista simplesmente ligada feita à medida:
Isto não deve ser confundido com uma pilha LIFO que usa um array dinâmico ou uma lista, que pode usar list, queue ou array por baixo.
As stacks baseadas em arrays dinâmicos têm uma posição de head diferente e uma complexidade temporal (Big-O) e ocupação de memória diferentes.
Consulta estas duas perguntas do Stack Overflow para teres 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 ligadas, pilhas LIFO e outros tipos de dados abstratos (ADT) em Python:
Classes em Python
A implementação "canónica" de uma lista ligada em Python exige normalmente uma ou mais classes.
Para uma boa introdução às classes, consulta o classes e o exercício complementar ellens-alien-game, ou a secção sobre classes do Tutorial Oficial de Python.
Métodos especiais em Python
Os testes deste exercício vão chamar len() ao teu LinkedList.
Para que len() funcione, tens de criar um método especial __len__.
Para detalhes sobre como implementar métodos especiais ou "dunder" em Python, consulta Documentação Python: personalização básica de objetos e Documentação Python: object.len(self).
Construir um iterador
Para permitir percorrer ou inverter o teu LinkedList, tens de implementar o método especial __iter__.
Consulta implementar um iterador para uma classe para obteres detalhes de implementação.
Personalizar e lançar exceções
Por vezes, é necessário personalizar e raise exceções no teu código.
Quando o fazes, deves incluir sempre uma mensagem de erro significativa que indique qual é a origem do erro.
Isto torna o teu código mais legível e ajuda imenso na depuração.
Podes criar exceções personalizadas através de novas classes de exceção (consulta classes para mais detalhes) que são normalmente subclasses de Exception.
Nas situações em que sabes que a origem do erro será uma derivada de um certo tipo de exceção, podes optar por herdar de um dos built in error types sob a classe Exception.
Ao lançar o erro, deves continuar a incluir uma mensagem significativa.
Este exercício em particular exige que cries uma exceção personalizada para ser lançada/"thrown" quando a tua lista ligada estiver vazia.
Os testes só passam se personalizares as exceções adequadas, fizeres raise dessas exceções e incluíres mensagens de erro adequadas.
Para personalizar uma exceção genérica, cria uma class que herde de Exception.
Ao lançar a exceção personalizada com uma mensagem, escreve a mensagem como argumento para o 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.")
