Lista enlazada

Instrucciones

Implementa una lista doblemente enlazada.

Igual que un array, una lista enlazada es una estructura de datos lineal sencilla. Con las listas enlazadas se pueden implementar varios tipos de datos comunes, como colas, pilas y arrays asociativos.

Una lista enlazada es una colección de elementos de datos llamados nodos. En una lista simplemente enlazada, cada nodo contiene un valor y un enlace al nodo siguiente. En una lista doblemente enlazada, cada nodo también contiene un enlace al nodo anterior.

Vas a escribir una implementación de una lista doblemente enlazada. Implementa un Node que contenga un valor y punteros al nodo siguiente y al anterior. Después, implementa un List que contenga referencias al primer y al último nodo y que ofrezca una interfaz similar a la de un array para añadir y eliminar elementos:

• push (insertar un valor al final);
• pop (eliminar el valor del final);
• shift (eliminar el valor del principio).
• unshift (insertar un valor al principio);

Para que tu implementación sea sencilla, los tests no cubrirán condiciones de error. En concreto: nunca se llamará a pop ni a shift con una lista vacía.

Lee más sobre las listas enlazadas en Wikipedia.