Estructura de datos

En ciencias de la computación, una estructura de datos^[1] es una forma particular de organizar información en un computador para que pueda ser utilizada de manera eficiente.^[2][3][4] Diferentes tipos de estructuras de datos son adecuados para diferentes tipos de aplicaciones, y algunos son altamente especializados para tareas específicas.

Las estructuras de datos son medios para manejar grandes cantidades de información de manera eficiente para usos tales como grandes bases de datos y servicios de indización de Internet. Por lo general, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes. Algunos métodos formales de diseño de lenguajes de programación destacan las estructuras de datos, en lugar de los algoritmos, como el factor clave de organización en el diseño de software. Más precisamente, una estructura de datos es una colección de valores, las relaciones entre ellos y las funciones y operaciones que se pueden aplicar a los datos,^[5] es decir, es una estructura algebraica de datos.

Las estructuras de datos se basan generalmente en la capacidad de un ordenador para recuperar y almacenar datos en cualquier lugar de su memoria.

Las estructuras de datos pueden ser de diferentes tipos, dependiendo de la técnica que se utilice para su almacenamiento y recuperación, estos tipos son los siguientes:

• Estructura de datos estática.
• Estructura de datos dinámica.^[6]

Según la secuencia que se presenta entre cada elemento al momento de realizar el recorrido entre los elementos de la estructura de datos, esta se puede clasificar en los siguientes tipos:

• Estructura de datos lineal.
• Estructura de datos no lineal.

Existen numerosos tipos de estructuras de datos, generalmente construidas sobre otras más simples:

• Un vector es una serie de elementos en un orden específico, por lo general todos del mismo tipo (si bien los elementos pueden ser de casi cualquier tipo). Se accede a los elementos utilizando un entero como índice para especificar el elemento que se requiere. Las implementaciones típicas asignan palabras de memoria contiguas a los elementos de los vectores (aunque no siempre es el caso). Los vectores pueden cambiar de tamaño o tener una longitud fija.
• Un vector asociativo (también llamado diccionario o mapa) es una variante más flexible que un vector, en la que se puede añadir y eliminar libremente pares nombre-valor. Una tabla de hash es una implementación usual de un vector asociativo.
• Una lista enlazada (también llamada solamente lista) es una colección lineal de elementos de datos de cualquier tipo, llamados nodos, donde cada nodo tiene en sí mismo un valor y apunta al siguiente nodo de la lista enlazada. La principal ventaja de una lista enlazada sobre un vector es que siempre se pueden insertar y eliminar valores de forma eficiente sin reubicar el resto de la lista. Sin embargo, otras operaciones, como el acceso aleatorio a un elemento determinado, son más lentas en las listas que en los vectores.
• Un registro (también llamado tupla o estructura) es una estructura de datos agregados. Un registro es un valor que contiene otros valores, típicamente en un número fijo y la secuencia y por lo general un índice por nombres. Los elementos de los registros generalmente son llamados campos o celdas.
• Una unión es una estructura de datos que especifica cuál de una serie de tipos de datos permitidos podrá ser almacenada en sus instancias, por ejemplo flotante o entero largo. En contraste con un registro, que se podría definir para contener un flotante y un entero largo, en una unión solo hay un valor a la vez. Se asigna suficiente espacio para contener el tipo de datos de cualquiera de los miembros.
• Un tipo variante (también llamado registro variante o unión discriminada) contiene un campo adicional que indica su tipo actual.
• Un conjunto es un tipo de datos abstracto que puede almacenar valores específicos, sin orden particular y sin valores duplicados.
• Un multiconjunto es un tipo de datos abstracto que puede almacenar valores específicos, sin orden particular. A diferencia de los conjuntos, los multiconjuntos admiten repeticiones.
• Un grafo es una estructura de datos conectada compuesta por nodos. Cada nodo contiene un valor y una o más referencias a otros nodos. Los grafos pueden utilizarse para representar redes, dado que los nodos pueden referenciarse entre ellos. Las conexiones entre nodos pueden tener dirección, es decir un nodo de partida y uno de llegada.
• Las pilas y las colas son tipos de datos abstractos que pueden implementarse utilizando vectores o listas enlazadas. Una pila tiene dos operaciones principales: apilar (añade un elemento a la parte superior de la pila) y desapilar (elimina el elemento más alto de la pila), que siguen el principio de último en entrar, primero en salir (LIFO). Las colas tienen dos operaciones principales: encolar (añade un elemento a la parte posterior de la cola) y desencolar (elimina un elemento de la parte anterior de la cola), que siguen el principio de primero en entrar, primero en salir (FIFO).
• Un árbol es un caso particular de grafo dirigido en el que no se admiten ciclos y existe un camino desde un nodo llamado raíz hasta cada uno de los otros nodos. Una colección de árboles es llamada un bosque.
• Una clase es una plantilla para la creación de objetos de datos según un modelo predefinido. Las clases se utilizan como representación abstracta de conceptos, incluyen campos como los registros y operaciones que pueden consultar el valor de los campos o cambiar sus valores.

La mayoría de los lenguajes ensambladores y algunos lenguajes de bajo nivel, tales como BCPL, carecen de soporte de estructuras de datos. En cambio, muchos lenguajes de alto nivel y algunos lenguajes ensambladores de alto nivel, tales como MASM, tienen algún tipo de soporte incorporado para ciertas estructuras de datos, tales como los registros y arreglos. Por ejemplo, los lenguajes C y Pascal soportan estructuras y registros, respectivamente, además de arreglos y matrices multidimensionales.^[7][8]

La mayoría de los lenguajes de programación disponen de algún tipo de biblioteca o mecanismo que permita el uso de estructuras de datos en los programas. Los lenguajes modernos por lo general vienen con bibliotecas estándar que implementan las estructuras de datos más comunes. Ejemplos de ello son la biblioteca Standard Template Library de C++, las colecciones de Java^[9] y las bibliotecas .NET de Microsoft.

En programación, una estructura de datos puede ser declarada inicialmente escribiendo una palabra reservada, luego un identificador para la estructura y un nombre para cada uno de sus miembros, sin olvidar los tipos de datos que estos representan. Generalmente, cada miembro se separa con algún tipo de operador, carácter o palabra reservada.

En el lenguaje de programación Pascal, es posible crear una estructura de datos de la forma mencionada. La sintaxis básica es:

 Estruct Identificador, _
              Miembro1:TipoDeDato, _
              Miembro2:TipoDeDato, _
              ... 
              Miembro9:TipoDeDato

Para acceder a los miembros de una estructura, primero se debe crear una referencia a esta, generalmente con una variable de tipo; luego se pueden editar y obtener los datos de los miembros libremente.

 Estruc Estructura,Miembro1:Entero,Miembro2:Cadena,Miembro3:Byte
 Var Variable:Estructura
 Variable.Miembro1 = 40000
 Variable.Miembro2 = "Hola Mundo"
 Variable.Miembro3 = 255
 Mensaje(Variable.Miembro2) ' Muestra "Hola Mundo"