En informática , una estructura de datos enlazada es una estructura de datos que consiste en un conjunto de registros de datos ( nodos ) enlazados entre sí y organizados por referencias ( enlaces o punteros ). El enlace entre datos también puede denominarse conector .
En las estructuras de datos enlazadas, los vínculos suelen tratarse como tipos de datos especiales que solo se pueden desreferenciar o comparar para comprobar su igualdad. Por lo tanto, las estructuras de datos enlazadas se contrastan con las matrices y otras estructuras de datos que requieren realizar operaciones aritméticas en punteros. Esta distinción se mantiene incluso cuando los nodos se implementan realmente como elementos de una única matriz y las referencias son en realidad índices de matriz : siempre que no se realice ninguna operación aritmética en esos índices, la estructura de datos es esencialmente una estructura enlazada.
La vinculación se puede realizar de dos maneras: mediante asignación dinámica y mediante vinculación de índice de matriz.
Las estructuras de datos enlazadas incluyen listas enlazadas , árboles de búsqueda , árboles de expresión y muchas otras estructuras de datos ampliamente utilizadas. También son elementos fundamentales para muchos algoritmos eficientes, como la ordenación topológica [1] y la búsqueda de conjuntos mediante unión . [2]
Una lista enlazada es una colección de estructuras ordenadas no por su ubicación física en la memoria sino por enlaces lógicos que se almacenan como parte de los datos en la propia estructura. No es necesario que se almacenen en las ubicaciones de memoria adyacentes. Cada estructura tiene un campo de datos y un campo de dirección. El campo de dirección contiene la dirección de su sucesora .
Una lista enlazada puede ser simple, doble o múltiple y puede ser lineal o circular.
Este es un ejemplo de la clase de nodo utilizada para almacenar números enteros en una implementación Java de una lista enlazada:
clase pública IntNode { int público valor ; IntNode público enlace ; IntNode público ( int v ) { valor = v ; } } Este es un ejemplo de la estructura utilizada para la implementación de la lista enlazada en C:
struct nodo { int val ; struct nodo * siguiente ; }; Este es un ejemplo que utiliza typedefs :
typedef struct nodo nodo ; struct nodo { int val ; nodo * siguiente ; }; Nota: Una estructura como ésta, que contiene un miembro que apunta a la misma estructura, se denomina estructura autorreferencial.
Este es un ejemplo de la estructura de clase de nodo utilizada para la implementación de la lista enlazada en C++:
clase Nodo { int val ; Nodo * siguiente ; }; Un árbol de búsqueda es una estructura de datos en forma de árbol en cuyos nodos se pueden almacenar valores de datos de un conjunto ordenado , tal que en un recorrido en orden del árbol los nodos se visitan en orden ascendente de los valores almacenados.
En comparación con las matrices, las estructuras de datos enlazadas permiten una mayor flexibilidad a la hora de organizar los datos y asignarles espacio. En las matrices, el tamaño de la matriz debe especificarse con precisión al principio, lo que puede suponer un posible desperdicio de memoria o una limitación arbitraria que más adelante podría obstaculizar la funcionalidad de algún modo. Una estructura de datos enlazada se construye de forma dinámica y nunca necesita ser más grande de lo que requiere el programa. Tampoco requiere adivinar en el momento de la creación cuánto espacio debe asignarse. Esta es una característica clave para evitar el desperdicio de memoria.
En una matriz, los elementos de la matriz deben estar en una parte contigua (conectada y secuencial) de la memoria. Pero en una estructura de datos enlazada, la referencia a cada nodo proporciona a los usuarios la información necesaria para encontrar el siguiente. Los nodos de una estructura de datos enlazada también se pueden mover individualmente a diferentes ubicaciones dentro de la memoria física sin afectar las conexiones lógicas entre ellos, a diferencia de las matrices. Con el debido cuidado, un determinado proceso o subproceso puede agregar o eliminar nodos en una parte de una estructura de datos incluso mientras otros procesos o subprocesos están trabajando en otras partes.
Por otra parte, el acceso a cualquier nodo particular en una estructura de datos enlazada requiere seguir una cadena de referencias que se almacenan en cada nodo. Si la estructura tiene n nodos, y cada nodo contiene como máximo b enlaces, habrá algunos nodos a los que no se pueda acceder en menos de log b n pasos, lo que ralentiza el proceso de acceso a estos nodos; esto a veces representa una ralentización considerable, especialmente en el caso de estructuras que contienen una gran cantidad de nodos. Para muchas estructuras, algunos nodos pueden requerir, en el peor de los casos, hasta n −1 pasos. Por el contrario, muchas estructuras de datos de matriz permiten el acceso a cualquier elemento con un número constante de operaciones, independientemente del número de entradas.
En términos generales, la implementación de estas estructuras de datos vinculadas se realiza mediante estructuras de datos dinámicas . Nos da la oportunidad de volver a utilizar un espacio determinado. La memoria se puede utilizar de manera más eficiente mediante el uso de estas estructuras de datos. La memoria se asigna según la necesidad y, cuando ya no se necesita más memoria, se realiza la desasignación.
Las estructuras de datos enlazadas también pueden generar una sobrecarga de asignación de memoria sustancial (si los nodos se asignan individualmente) y frustrar los algoritmos de paginación de memoria y de almacenamiento en caché del procesador (ya que generalmente tienen una localidad de referencia deficiente ). En algunos casos, las estructuras de datos enlazadas también pueden utilizar más memoria (para los campos de enlace) que las estructuras de matriz de la competencia. Esto se debe a que las estructuras de datos enlazadas no son contiguas. Las instancias de datos se pueden encontrar en toda la memoria, a diferencia de las matrices.
En las matrices, se puede acceder inmediatamente al elemento n, mientras que en una estructura de datos vinculada tenemos que seguir múltiples punteros, por lo que el tiempo de acceso al elemento varía según dónde se encuentre el elemento en la estructura.
En algunos modelos teóricos de computación que imponen las restricciones de estructuras vinculadas, como la máquina de punteros , muchos problemas requieren más pasos que en el modelo de máquina de acceso aleatorio sin restricciones .