La estructura de datos conocida como lista enlazada (ligada o encadenada, “linked list”) es una colección de nodos dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente elemento por un “enlace”.
Palabras clave:
- Puntero: Puede tratarse del instrumento que se utiliza para señalar algo en una pantalla, un pizarrón, un mapa u otra superficie. En este caso se refiere a la dirección de memoria que contiene el dato guardado.
- Enlace: En este caso nos interesa aludir a su acepción como una unión o un vínculo entre distintos elementos.
- Dato: Cifra, letra o palabra que se suministra a la computadora como entrada y la máquina almacena en un determinado formato.
- Nodo: En programación, concretamente en estructuras de datos, un nodo es uno de los elementos de una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para uno de los procesadores que lo componen.
Definición:
Gracias a la asignación dinámica de memoria, se pueden implementar listas de modo que la memoria física utilizada se corresponda exactamente con el número de elementos de la tabla. Para ello se recurre a los punteros y variables apuntadas que se crean en tiempo de ejecución. Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un “enlace”.
La idea básica consiste en construir una lista cuyos elementos, llamados nodos, se componen de dos partes (campos): la primera parte contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Dato, TipoElemento, Info, etc.), y la segunda parte es un puntero al siguiente nodo de la lista. Además, la lista posee la cantidad de nodos que hay entrelazados.
Las listas se pueden dividir en cuatro categorías:
- Listas simplemente enlazadas. Cada nodo contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos (“adelante”).
- Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo (“adelante”) como en recorrido inverso (“atrás”).
- Lista circular simplemente enlazada. Una lista simplemente enlazada en la que el último elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de modo circular (“en anillo”).
- Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directa (“adelante”) como inversa (“atrás”)
Para que esta estructura sea un tipo de dato abstracto “lista enlazada”, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de una lista enlazada son:
- Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.
- Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.
- Buscar: busca un elemento en la lista.
- Localizar: obtiene la posición del nodo en la lista
- Vaciar: borra todos los elementos de la lista
 |
 |
| Imagen 1 | Imagen 2 |
En la Imagen 1 se logra apreciar lo que es un nodo y cómo están establecidas de manera simbólica las listas. La imagen no hace alusión a que los datos se encuentran en secuencia en un bloque de memoria pero que se puede llegar a ellos por medio de enlaces.
En la Imagen 2 se logra apreciar de manera metafórica la similitud de una lista y un tren donde, la lista poseerá un elemento con el cual se pueda conectar con todos los demás.
En 2016, "Metáfora: los trenes y las listas dinámicas" establece que a la hora de añadir un nodo, se realiza de una forma parecida a como se añadiría un vagón en el tren. Primero se debe crear el vagón/nodo, luego recorrer la lista/tren hasta la posición deseada y añadirlo en ese lugar. En la lista lo único que se debe realizar es modificar los enlaces, para que el nodo anterior apunte al nuevo y éste al siguiente.
Imagen 3
Para eliminar un nodo, parecido al método anterior. Se recorre la lista hasta llegar al nodo deseado y se modifican los enlaces. En este caso, solo se debe modificar el enlace del nodo anterior para que apunte al siguiente.
Imagen 4
Como se ha comentado anteriormente en cada nodo de las listas doblemente enlazadas hay dos enlaces, al nodo anterior y siguiente. Además, también se tiene acceso a la cola de la lista (último nodo). De esta manera, se puede recorrer la lista empezando por el último nodo o el primero.
Notas de programación:
- Para manipular una esta estructura de datos dinámica, aparte de declararla hay que inicializarla con el constructor de la lista, de no hacer esto, no se podrán utilizar los métodos.
- Las variables apPrimerNodo o apUltimoNodo deben de inicializarse en nullptr y el contador de nodos en 0 para evitar errores.
Errores de programación:
- No se pueden ingresar elementos de otro tipo de dato del que se estableció en la creación del TAD.
- No se puede llamar a un método de un objeto si este es nullptr.
Referencias:
- Definición de nodo — Definicion.de. (2019). Recuperado de https://definicion.de/nodo/
- Definición de puntero — Definicion.de. (2019). Recuperado de https://definicion.de/puntero/
- Definición de enlace — Definicion.de. (2019). Recuperado https://definicion.de/enlace/
- Joyanes Aguilar, L., Sánchez García, L., & Zahonero Martínez, I. (2007). Estructura de datos en C++. McGraw-Hill,.
- Metáfora: los trenes y las listas dinámicas. (2016, 26 octubre). Recuperado 10 mayo, 2019, de https://aeiua.wordpress.com/2016/10/26/metafora-los-trenes-y-las-listas-dinamicas/
- Estructuras de datos: listas enlazadas, pilas y colas.. (s.f.). Recuperado 10 mayo, 2019, de http://www.calcifer.org/documentos/librognome/glib-lists-queues.html