Introdução
Você está trabalhando em um projeto para desenvolver um sistema de agendamento de trens para uma rede ferroviária movimentada.
Você ficou responsável por desenvolver um protótipo para as rotas de trem do sistema de agendamento.
Cada rota é uma sequência de estações de trem em que um determinado trem para.
Instruções
Sua equipe decidiu usar uma lista duplamente encadeada para representar cada rota de trem no cronograma.
Cada estação ao longo da rota do trem será representada por um nó na lista encadeada.
Você não precisa se preocupar com os horários de chegada e de partida nas estações.
Cada estação será representada simplesmente por um número.
As rotas podem ser estendidas, adicionando 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.
Às vezes uma estação é fechada e, nesse caso, ela precisa ser removida da rota, mesmo que não esteja no início nem no fim dela.
O tamanho de uma rota não é medido pela distância que o trem percorre, mas por quantas estações ele para.
A lista encadeada é uma estrutura de dados fundamental na ciência da computação, frequentemente usada na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós que estão ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou aos seus vizinhos.
Em uma lista simplesmente encadeada, cada nó se liga apenas ao nó que vem depois dele.
Em uma lista duplamente encadeada, cada nó se liga tanto ao nó que vem antes quanto ao nó que vem depois.
Se você quiser se aprofundar em listas encadeadas, confira este artigo, que explica o assunto com desenhos bem explicativos.
Como este exercício está estruturado em Python
Embora listas encadeadas possam ser implementadas de várias maneiras, com diversas estruturas de dados por baixo, aqui pedimos que você implemente sua lista encadeada com orientação a objetos.
No arquivo stub, você vai ver o início de uma classe Node, além de uma classe LinkedList.
Sua classe Node deve guardar o próprio valor, além de quais nós vêm antes ou depois.
Os métodos push, pop, shift e unshift, e também o método especial para len, devem ser implementados na classe LinkedList.
Talvez também seja útil implementar um método especial iter para a iteração.
Diferente do exercício principal, vamos testar condições de erro chamando pop e shift em LinkedLists vazias, então você vai precisar usar raise para lançar os erros adequados.
Por fim, além dos métodos descritos acima, queremos que você implemente delete.
delete vai receber um argumento, que é o valor a ser removido da lista encadeada.
Se o valor aparecer mais de uma vez, apenas a primeira ocorrência deve ser removida.
Mensagens de exceção
Às vezes é necessário lançar uma exceção. Quando você faz isso, deve sempre incluir 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.
Em situações em que você sabe que a origem do erro será de um determinado tipo, você pode optar por lançar um dos tipos de erro embutidos, mas ainda deve incluir uma mensagem significativa.
Este exercício em particular exige que você use a instrução raise para "lançar" um ValueError quando o valor passado para delete() não for encontrado na lista encadeada.
Além disso, um IndexError deve ser lançado se não houver mais nós para pop().
Os testes só vão passar se você fizer raise dessas exceptions e incluir mensagens junto com elas.
Para lançar um ValueError com uma mensagem, escreva a mensagem como argumento do 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, escreva a mensagem como argumento do 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() na sua LinkedLists.
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).
Também recomendamos criar um método especial __iter__ para ajudar na iteração da sua lista encadeada.
Fonte
Tópico clássico da ciência da computação
