Empezaremos por una definición sencilla:
Las listas son una sucesión de cero o más elementos .
Esta es una definición muy simple y que no aclara demasiado en terminos informáticos, así que profundizaremos un poco más.
Hay varios tipos de listas, las hay enlazadas, no enlazadas, ordenadas y no ordenadas. Nosotros vamos a estudiar las listas enlazadas, tanto ordenadas como no ordenadas.
La diferencia que existe entre las listas enlazadas y las no enlazadas es que las enlazadas utilizan punteros, es decir, asignación dinámica de memoria, lo que optimiza la gestión de la misma. Una lista no enlazada es un simple array, y por lo tanto es un bloque contiguo de memoria, mientras que una lista enlazada es un conjunto de nodos que no tienen porque ocupar posiciones contiguas de memoria.
La diferencia entre listas ordenadas y no ordenadas es obvia, las ordenadas mantienen cierto orden entre sus elementos.
A partir de ahora nos centraremos en las listas enlazadas no ordenadas.
Una lista es una sucesión de nodos en la que a partir de un nodo se puede acceder al que ocupa la siguiente posición en la lista. Esta característica nos indica que el acceso a las listas es secuencial y no indexado, por lo que para acceder al último elemento de la lista hay que recorrer los n-1 elementos previos ( n es el tamaño de la lista).
Para que un nodo pueda acceder al siguiente y la lista no se rompa en varias listas cada nodo tiene que tener un puntero que guarde la dirección de memoria que ocupa el siguiente elemento. De esta forma un nodo se podría representar esquemáticamente así:
En el campo información se almacena el objeto a guardar y el puntero mantendrá la conexión con el nodo siguiente.
De esta forma al ir añadiendo nodos se iría formando una sucesión de nodos encadenados mediante punteros.
