Track
/
Tcl
Tcl
/
Esercizi
/
Lista concatenata
Lista concatenata

Lista concatenata

Medio

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.

Note

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.

Note di implementazione

Scriverai un'implementazione di una lista doppiamente concatenata.

Implementa un Node che contiene un valore insieme ai puntatori al nodo successivo e a quello precedente.

Poi implementa una LinkedList che contiene i riferimenti al primo e all'ultimo nodo e offre un'interfaccia simile a quella di un array per aggiungere e rimuovere elementi:

  • push (inserisce un valore in fondo);
  • pop (rimuove il valore in fondo);
  • shift (rimuove il valore in testa);
  • unshift (inserisce un valore in testa);
  • delete (rimuove il primo nodo corrispondente)

Per mantenere semplice l'implementazione, i test non copriranno le condizioni di errore. In particolare: né pop né shift verranno mai chiamati su una lista vuota.


Fonte

Argomento classico dell'informatica
Modifica tramite GitHub Il link si apre in una nuova finestra o scheda
Tcl Exercism

Vuoi iniziare Lista concatenata?

Iscriviti a Exercism per imparare e padroneggiare Tcl con 135 esercizi e il mentoring di persone reali, tutto gratis.