What is a Doubly Linked List?

Una lista doblemente enlazada es una secuencia de nodos donde cada nodo contiene un valor y dos punteros: prev al nodo anterior, y next al nodo siguiente. La lista en sí hace un seguimiento de ambos extremos, el head (primer nodo) y el tail (último nodo).

Los dos punteros por nodo y la referencia extra a tail nos aportan mucho. Añadir al final es ahora O(1) (saltar directamente a tail en lugar de recorrer la cadena), y eliminar el último nodo también es O(1) (porque podemos llegar al penúltimo nodo desde tail.prev). La contrapartida es más memoria por nodo, además de más punteros que mantener sincronizados en cada inserción y eliminación.

Las cinco operaciones principales en una lista doblemente enlazada son:

1. AddFirst: Añadir un valor al principio de la lista.
2. AddLast: Añadir un valor al final de la lista (¡O(1)!).
3. Get: Devolver el valor en un índice dado.
4. RemoveLast: Eliminar el último nodo (¡O(1)!).
5. Size: Devolver el número de nodos almacenados actualmente.

¡Vamos a crear primero una clase Node y luego construiremos la DoublyLinkedList sobre ella!