Introduzione
Stai lavorando a un progetto per sviluppare un sistema di pianificazione dei treni per una rete ferroviaria molto trafficata.
Ti è stato chiesto di sviluppare un prototipo per le tratte dei treni del sistema di pianificazione.
Ogni tratta è composta da una sequenza di stazioni ferroviarie in cui un determinato treno fa fermata.
Istruzioni
Il tuo team ha deciso di usare una lista doppiamente concatenata per rappresentare ogni percorso ferroviario dell'orario.
Ogni stazione lungo il percorso del treno sarà rappresentata da un nodo della lista concatenata.
Non devi preoccuparti degli orari di arrivo e di partenza alle stazioni.
Ogni stazione sarà semplicemente rappresentata da un numero.
I percorsi possono essere estesi, aggiungendo stazioni all'inizio o alla fine di un percorso.
Si possono anche accorciare rimuovendo stazioni dall'inizio o dalla fine di un percorso.
A volte una stazione viene chiusa, e in quel caso va rimossa dal percorso, anche se non si trova all'inizio o alla fine.
La dimensione di un percorso non si misura in base a quanto lontano viaggia il treno, ma in base a quante stazioni tocca.
La lista concatenata è una struttura dati fondamentale dell'informatica, spesso usata per implementare altre strutture dati.
Come suggerisce il nome, è una lista di nodi collegati tra loro.
È una lista di «nodi», in cui ogni nodo è collegato al suo vicino o ai suoi vicini.
In una lista semplicemente concatenata ogni nodo è collegato solo al nodo che lo segue.
In una lista doppiamente concatenata ogni nodo è collegato sia al nodo che viene prima sia a quello che viene dopo.
Se vuoi approfondire le liste concatenate, dai un'occhiata a questo articolo, che le spiega con dei bei disegni.
Come è strutturato questo esercizio in Python
Sebbene le liste concatenate si possano implementare in molti modi diversi, con diverse strutture dati di base, qui ti chiediamo di implementare la lista concatenata seguendo lo stile OOP.
Nel file stub vedrai l'inizio di una classe Node, oltre a una classe LinkedList.
La classe Node dovrebbe tenere traccia del suo valore, oltre che dei nodi che la precedono e la seguono.
I metodi push, pop, shift, unshift e il metodo speciale per len vanno implementati nella classe LinkedList.
Potresti anche trovare utile implementare un metodo speciale iter per l'iterazione.
A differenza dell'esercizio principale, testeremo le condizioni di errore chiamando pop e shift su LinkedList vuote, quindi dovrai sollevare gli errori nel modo appropriato con raise.
Infine, vorremmo che implementassi anche delete, oltre ai metodi elencati sopra.
delete prende un argomento, cioè il valore da rimuovere dalla lista concatenata.
Se il valore compare più di una volta, va rimossa solo la prima occorrenza.
Messaggi delle eccezioni
A volte è necessario sollevare un'eccezione. Quando lo fai, dovresti sempre includere un messaggio di errore significativo che indichi qual è l'origine dell'errore.
Così il codice diventa più leggibile e il debug risulta molto più semplice.
Nei casi in cui sai che l'origine dell'errore sarà di un certo tipo, puoi scegliere di sollevare uno dei tipi di errore predefiniti, ma dovresti comunque includere un messaggio significativo.
Questo esercizio in particolare richiede che tu usi la istruzione raise per «lanciare» un ValueError quando il valore passato a delete() non si trova nella lista concatenata.
Inoltre, va sollevato un IndexError se non ci sono più nodi da estrarre con pop().
I test passeranno solo se sollevi queste exceptions con raise e le accompagni con un messaggio.
Per sollevare un ValueError con un messaggio, scrivi il messaggio come argomento del tipo di exception:
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Per sollevare un IndexError con un messaggio, scrivi il messaggio come argomento del tipo di exception:
# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
raise IndexError("List is empty")
Metodi speciali in Python
I test di questo esercizio chiameranno anche len() sulla LinkedLists.
Perché len() funzioni, dovrai creare un metodo speciale __len__.
Per i dettagli su come implementare i metodi speciali o «dunder» in Python, vedi Python Docs: personalizzazione di base degli oggetti e Python Docs: object.len(self).
Ti consigliamo anche di creare un metodo speciale __iter__ che aiuti a iterare sulla lista concatenata.
Fonte
Argomento classico dell'informatica
