What is a Linked List?

Una lista enlazada es una secuencia de valores donde cada valor vive en su propio nodo, y cada nodo contiene un puntero al siguiente nodo. La lista conoce su primer nodo (la cabeza); desde allí se llega a cada uno de los demás nodos siguiendo la cadena de punteros next.

A diferencia de un array, una lista enlazada no necesita un único bloque contiguo de memoria. Añadir un elemento en la cabeza es O(1): simplemente se crea un nuevo nodo y se apunta a la cabeza actual. La desventaja es que llegar al n-ésimo elemento es O(n), porque tenemos que recorrer la cadena nodo por nodo.

Las cinco operaciones principales en una lista enlazada son:

1. AddFirst: Añade un valor al principio de la lista.
2. AddLast: Añade un valor al final de la lista.
3. Get: Devuelve el valor en un índice dado.
4. Remove: Elimina el valor en un índice dado.
5. Size: Devuelve el número de valores almacenados actualmente.

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