Estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y enlaces a otros nodos.
Lista simple enlazada
Una lista enlazada es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y enlaces a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura.
Las listas enlazadas son estructuras dinámicas que se utilizan para almacenar datos que están cambiando constantemente. A diferencia de los vectores, las estructuras dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de añadir o eliminar información.
Son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un índice, sino, mediante un puntero. Es un conjunto de nodos uno seguido del otro que poseen la propiedad de tener un nodo inicio y un apuntador final. Las listas enlazadas pueden ser utilizadas cuando se necesitan hacer varias operaciones de inserción y eliminación de elementos. Mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero.
Inserción por cabeza
Al insertar un nuevo nodo en una lista simple enlazada, éste nuevo nodo se insertará al inicio de la lista por lo tanto el puntero del nodo nuevo debe de apuntar al primer nodo de la lista, y el puntero nuevo se convertirá en el puntero primero. En la Ilustración 2 se muestra este proceso de forma gráfica.
Inserción por cola
Se inserta un nuevo nodo al final de la lista de nodos, el último nodo de la lista estará apuntando a NULL, por lo tanto éste puntero ahora pasará a apuntar al nodo nuevo y el nodo insertado apuntará a NULL.
Eliminar
Primero se debe recorre la lista para buscar el elemento que se quiere eliminar. Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero siguiente permite el cambio hacia el próximo elemento. El desplazamiento se hace en una sola dirección del primer al último elemento. El puntero siguiente del último elemento de la lista tiene que apuntar hacia NULL (el fin de la lista).
Para poder eliminar un elemento de una lista enlazada hacemos uso de un puntero auxiliar, que nos guarda la referencia al elemento posterior al que se quiere eliminar. Se usa el puntero auxiliar para que éste sea enlazado con el puntero siguiente del nodo a eliminar. En la Ilustración 04 se muestra este procedimiento de forma gráfica.
