Lista enlazada

En ciencias de la computación, una ‘’lista enlazada’’ es una estructura de datos lineal compuesta por una secuencia de nodos. Cada nodo almacena uno o más valores de datos y una o varias referencias —también llamadas ‘’enlaces’’ o ‘‘punteros’’— hacia otros nodos de la lista. A diferencia de los arreglos o vectores convencionales, los elementos de una lista enlazada no necesitan ocupar posiciones contiguas en memoria. Esto permite insertar o eliminar elementos sin necesidad de reorganizar físicamente el conjunto de datos. Además, el orden lógico de los nodos puede diferir del orden en que están almacenados, lo que otorga flexibilidad en la gestión dinámica de memoria. Las listas enlazadas constituyen la base de numerosas estructuras de datos más complejas, como las pilas, colas y diversas formas de árboles. Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares. Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp, Scheme y Haskell tienen estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.