Lista concatenata

Istruzioni

Implementa una lista doppiamente concatenata.

Come un array, una lista concatenata è una semplice struttura dati lineare. Con le liste concatenate si possono implementare diversi tipi di dati comuni, come code, pile e array associativi.

Una lista concatenata è una collezione di elementi di dati chiamati nodi. In una lista singolarmente concatenata ogni nodo contiene un valore e un collegamento al nodo successivo. In una lista doppiamente concatenata ogni nodo contiene anche un collegamento al nodo precedente.

Scriverai un'implementazione di una lista doppiamente concatenata. Implementa un Node che contenga un valore e i puntatori ai nodi successivo e precedente. Poi implementa una List che contenga i riferimenti al primo e all'ultimo nodo e offra un'interfaccia simile a quella di un array per aggiungere e rimuovere elementi:

• push (inserisce un valore in fondo);
• pop (rimuove un valore dal fondo);
• shift (rimuove un valore dall'inizio).
• unshift (inserisce un valore all'inizio);

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

Leggi di più sulle liste concatenate su Wikipedia.