¿Qué es una estructura de datos vinculados?

Una estructura de datos vinculados es una colección de datos organizados en un formato similar a una lista. Cada dato de la lista se denomina nodo. Cada nodo está conectado al siguiente de la lista por una referencia a la dirección de memoria de ese nodo posterior. Las estructuras de datos vinculados se utilizan en lugar de una matriz cuando se desconoce el número de nodos en una lista o puede crecer o reducirse en el transcurso del ejecución del programa El tipo más común de estructura de datos vinculados se denomina lista vinculada.

Un nodo de una estructura de datos vinculada generalmente contiene dos elementos de información: una referencia a los datos reales que se almacenan y una referencia al siguiente nodo de la lista. Una lista vinculada se recorre, o se busca, por pasos a través de cada uno de los nodos de datos, comenzando por el primero, o el encabezado de la lista. No hay forma de encontrar información en una lista vinculada sin moverse secuencialmente a través de los nodos de principio a fin.

La mayoría de las estructuras de datos vinculadas usarán la menor cantidad de memoria posible durante la ejecución del programa. Si se crea una lista vinculada con un solo nodo y no se agregan otros nodos, esa lista ocupará el memoria requerida para un solo nodo. Esto está en marcado contraste con una estructura de datos de matriz en la que el tamaño de toda la matriz debe declararse y asignarse al inicio del programa y no puede cambiarse .

Las listas vinculadas pagan por su uso eficiente de los recursos de memoria al requerir más potencia informática. Encontrar un dato específico en una lista vinculada requiere recorrer toda la lista cada vez, por lo que puede ser más lento acceder a la información en la mitad de la lista: eliminar o reordenar datos en una lista vinculada también puede ser más intensivo desde el punto de vista computacional que administrar una matriz en la que los elementos se pueden intercambiar fácilmente.

No es necesario que una estructura de datos vinculada tenga una sola referencia al siguiente nodo; puede tener varios. Algunas listas vinculadas tienen dos referencias de nodo, una al siguiente nodo de la lista y otra al nodo anterior. Estas se conocen como listas doblemente vinculadas. Esto puede hacer que moverse a través de un listar en cualquier dirección mucho más rápido, aunque a expensas de un mayor uso de memoria para la estructura de datos.

Es posible que las listas vinculadas tengan tres o más referencias a otros nodos en la lista. Esto crea una estructura similar a un árbol con ramas enteras de nodos que se generan a partir de una sola. Estos tipos de datos las estructuras se denominan listas con enlaces múltiples. Las listas con enlaces múltiples son particularmente útiles para algoritmos de clasificación complejos que se utilizan para estructurar datos. Los árboles de búsqueda son posibles en gran medida debido al uso de estructuras de datos vinculados para crear múltiples ramas de longitud variable.