En informática , una estructura de datos vinculada es una estructura de datos que consta de un conjunto de registros de datos ( nodos ) vinculados entre sí y organizados por referencias ( enlaces o punteros ). El vínculo entre datos también se puede llamar conector .
En las estructuras de datos vinculadas, los vínculos generalmente se tratan como tipos de datos especiales que solo pueden desreferenciarse o compararse por igualdad. Por 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 sola matriz, y las referencias son en realidad índices de matriz : siempre que no se realice aritmética en esos índices, la estructura de datos es esencialmente vinculada.
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 vinculadas incluyen listas vinculadas , árboles de búsqueda , árboles de expresión y muchas otras estructuras de datos ampliamente utilizadas. También son bloques de construcción clave para muchos algoritmos eficientes, como topological sort [1] y set union-find . [2]
Tipos comunes de estructuras de datos vinculadas
Listas vinculadas
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 estructura misma. No es necesario que se almacene en las ubicaciones de memoria adyacentes. Cada estructura tiene un campo de datos y un campo de dirección. El campo Dirección contiene la dirección de su sucesor .
La lista enlazada puede estar enlazada de forma simple, doble o múltiple y puede ser lineal o circular.
- Propiedades básicas
- Los objetos, llamados nodos , están vinculados en una secuencia lineal.
- Siempre se mantiene una referencia al primer nodo de la lista. Esto se llama "cabeza" o "frente". [3]
Una lista vinculada con tres nodos contiene dos campos cada uno: un valor entero y un vínculo al siguiente nodo
Ejemplo en Java
Este es un ejemplo de la clase de nodo utilizada para almacenar enteros en una implementación Java de una lista vinculada:
público de clase IntNode { pública int valor ; enlace IntNode público ; IntNode público ( int v ) { valor = v ; } }
Ejemplo en C
Este es un ejemplo de la estructura utilizada para la implementación de la lista enlazada en C:
struct nodo { int val ; nodo de estructura * siguiente ; };
Este es un ejemplo usando typedefs :
typedef struct nodo nodo ;struct nodo { int val ; nodo * siguiente ; };
Nota: Una estructura como esta que contiene un miembro que apunta a la misma estructura se llama estructura autorreferencial.
Ejemplo en C ++
Este es un ejemplo de la estructura de clases de nodo utilizada para la implementación de la lista vinculada en C ++:
class Node { int val ; Nodo * siguiente ; };
Buscar árboles
Un árbol de búsqueda es una estructura de datos de árbol en cuyos nodos se pueden almacenar valores de datos de algún conjunto ordenado , que es tal que en un recorrido en orden del árbol, los nodos se visitan en orden ascendente de los valores almacenados.
- Propiedades básicas
- Los objetos, llamados nodos, se almacenan en un conjunto ordenado.
- El recorrido en orden proporciona una lectura ascendente de los datos en el árbol.
Ventajas y desventajas
Lista vinculada frente a matrices
En comparación con las matrices, las estructuras de datos vinculadas permiten una mayor flexibilidad en la organización de los datos y en la asignación de espacio para ellos. En las matrices, el tamaño de la matriz debe especificarse con precisión al principio, lo que puede ser un potencial desperdicio de memoria o una limitación arbitraria que luego obstaculizaría la funcionalidad de alguna manera. Una estructura de datos vinculada se construye dinámicamente y nunca necesita ser más grande de lo que requiere el programa. Tampoco requiere adivinar en el momento de la creación, en términos de 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 vinculada, la referencia a cada nodo brinda a los usuarios la información necesaria para encontrar el siguiente. Los nodos de una estructura de datos vinculada 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 otro lado, el acceso a cualquier nodo en particular en una estructura de datos enlazados 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 puede llegar 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 un gran número de nodos. Para muchas estructuras, algunos nodos pueden requerir 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 general, la implementación de estas estructuras de datos vinculadas se realiza a través de estructuras de datos dinámicas . Nos da la oportunidad de volver a utilizar un espacio en particular. La memoria se puede utilizar de manera más eficiente utilizando estas estructuras de datos. La memoria se asigna según la necesidad y cuando no se necesita más memoria, se realiza la desasignación.
Desventajas generales
Las estructuras de datos vinculadas también pueden incurrir en una sobrecarga sustancial de asignación de memoria (si los nodos se asignan individualmente) y frustrar los algoritmos de paginación de memoria y almacenamiento en caché del procesador (ya que generalmente tienen una localidad de referencia deficiente ). En algunos casos, las estructuras de datos vinculadas también pueden usar más memoria (para los campos de vínculo) que las estructuras de matriz de la competencia. Esto se debe a que las estructuras de datos vinculadas 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 al n-ésimo elemento inmediatamente, mientras que en una estructura de datos enlazados tenemos que seguir varios punteros para que el tiempo de acceso al elemento varíe según el lugar de la estructura en el que se encuentre el elemento.
En algunos modelos teóricos de cálculo que refuerzan las restricciones de las estructuras vinculadas, como la máquina de puntero , muchos problemas requieren más pasos que en el modelo de máquina de acceso aleatorio sin restricciones .
Ver también
Referencias
- ^ Donald Knuth , El arte de la programación informática
- ^ Bernard A. Galler y Michael J. Fischer . Un algoritmo de equivalencia mejorado. Communications of the ACM , Volumen 7, Número 5 (mayo de 1964), páginas 301–303. El papel que origina bosques desarticulados. Biblioteca digital ACM
- ^ http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf