Introdução
Estás a trabalhar num projeto para desenvolver um sistema de horários para uma rede ferroviária movimentada.
Foi-te pedido que desenvolvesses um protótipo para as rotas dos comboios no sistema de horários. Cada rota é composta por uma sequência de estações onde um determinado comboio para.
Instruções
A tua equipa decidiu usar uma lista duplamente ligada para representar cada rota de comboio no horário.
Cada estação ao longo da rota do comboio será representada por um nó na lista ligada.
Não precisas de te preocupar com as horas de chegada e de partida nas estações.
Cada estação será simplesmente representada por um número.
As rotas podem ser estendidas, acrescentando estações ao início ou ao fim de uma rota.
Também podem ser encurtadas, removendo estações do início ou do fim de uma rota.
Por vezes, uma estação é encerrada e, nesse caso, tem de ser removida da rota, mesmo que não esteja no início nem no fim da rota.
O tamanho de uma rota não se mede pela distância que o comboio percorre, mas pelo número de estações onde para.
A lista ligada é uma estrutura de dados fundamental da informática, usada frequentemente na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou vizinhos.
Numa lista ligada simples, cada nó liga-se apenas ao nó que se lhe segue.
Numa lista duplamente ligada, cada nó liga-se tanto ao nó que vem antes como ao nó que vem depois.
Se quiseres aprofundar os teus conhecimentos sobre listas ligadas, espreita este artigo, que as explica com desenhos muito claros.
Como este exercício está estruturado em Python
Embora as listas ligadas possam ser implementadas de várias formas, com diversas estruturas de dados subjacentes, pedimos-te aqui que implementes a tua lista ligada de forma orientada a objetos.
No ficheiro de partida, vais ver o início de uma classe Node, bem como de uma classe LinkedList.
A tua classe Node deve manter registo do seu valor, bem como dos nós que a precedem ou seguem.
Os teus métodos push, pop, shift, unshift e o método especial para len devem ser implementados na classe LinkedList.
Também podes achar útil implementar um método especial iter para a iteração.
Ao contrário do exercício principal, vamos testar condições de erro através de chamadas a pop e shift em LinkedLists vazias, por isso vais precisar de lançar erros com raise de forma adequada.
Por fim, gostaríamos que implementasses delete para além dos métodos descritos acima.
delete vai receber um argumento, que é o valor a remover da lista ligada.
Se o valor aparecer mais do que uma vez, só deve ser removida a primeira ocorrência.
Mensagens de exceção
Às vezes é necessário lançar uma exceção. Quando o fazes, deves incluir sempre uma mensagem de erro significativa para indicar qual é a origem do erro.
Isto torna o teu código mais legível e ajuda bastante na depuração.
Em situações em que sabes que a origem do erro será de um determinado tipo, podes optar por lançar um dos tipos de erro incorporados, mas ainda assim deves incluir uma mensagem significativa.
Este exercício em particular exige que uses a instrução raise para "lançar" um ValueError quando um valor de nó que está a ser alvo de delete() não for encontrado na lista ligada.
Além disso, deve ser lançado um IndexError se não houver nós restantes para pop().
Os testes só passam se fizeres raise destas exceptions e incluíres mensagens com elas.
Para lançar um ValueError com uma mensagem, escreve a mensagem como argumento para o tipo exception:
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Para lançar um IndexError com uma mensagem, escreve a mensagem como argumento para o 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 especiais em Python
Os testes deste exercício também vão chamar len() à tua LinkedList.
Para que len() funcione, vais precisar de criar um método especial __len__.
Para mais detalhes sobre como implementar métodos especiais ou "dunder" em Python, consulta Documentação do Python: personalização básica de objetos e Documentação do Python: object.len(self).
Também recomendamos criar um método especial __iter__ para ajudar a iterar sobre a tua lista ligada.
Fonte
Tópico clássico da informática
