Estructura de datos

Una estructura de datos conocida como tabla de hash.

En informática, una estructura de datos es un formato de organización, gestión y almacenamiento de datos que generalmente se elige para un acceso eficiente a los datos. Más precisamente, una estructura de datos es una colección de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a los datos, es decir, es una estructura algebraica sobre datos.

Uso

Las estructuras de datos sirven como base para los tipos de datos abstractos (ADT). El ADT define la forma lógica del tipo de datos. La estructura de datos implementa la forma física del tipo de datos.

Diferentes tipos de estructuras de datos se adaptan a diferentes tipos de aplicaciones y algunas están altamente especializadas para tareas específicas. Por ejemplo, las bases de datos relacionales suelen utilizar índices de árbol B para la recuperación de datos, mientras que las implementaciones de compiladores suelen utilizar tablas hash para buscar identificadores.

Las estructuras de datos brindan un medio para administrar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos y servicios de indexación de Internet. Por lo general, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes. Algunos métodos de diseño formal y lenguajes de programación enfatizan las estructuras de datos, en lugar de los algoritmos, como el factor organizador clave en el diseño de software. Las estructuras de datos se pueden utilizar para organizar el almacenamiento y la recuperación de información almacenada tanto en la memoria principal como en la memoria secundaria.

Implementación

Las estructuras de datos generalmente se basan en la capacidad de una computadora para obtener y almacenar datos en cualquier lugar de su memoria, especificados por un puntero, una cadena de bits que representa una dirección de memoria, que puede almacenarse en la memoria y manipularse mediante el programa. Por lo tanto, las estructuras de datos de matriz y registro se basan en el cálculo de las direcciones de los elementos de datos con operaciones aritméticas, mientras que las estructuras de datos vinculados se basan en el almacenamiento de las direcciones de los elementos de datos dentro de la propia estructura.

La implementación de una estructura de datos generalmente requiere escribir un conjunto de procedimientos que crean y manipulan instancias de esa estructura. La eficiencia de una estructura de datos no puede analizarse por separado de esas operaciones. Esta observación motiva el concepto teórico de un tipo de dato abstracto, una estructura de datos que se define indirectamente por las operaciones que se pueden realizar sobre él y las propiedades matemáticas de esas operaciones (incluido su costo de espacio y tiempo).

Ejemplos

La jerarquía tipo estándar del lenguaje de programación Python 3.

Existen numerosos tipos de estructuras de datos, generalmente basadas en tipos de datos primitivos más simples. Ejemplos bien conocidos son:

• Un array es un número de elementos en un orden específico, por lo general todo del mismo tipo (dependiendo del idioma, los elementos individuales pueden ser forzados a ser el mismo tipo, o puede ser de casi cualquier tipo). Los elementos se acceden usando un índice entero para especificar qué elemento es necesario. Las implementaciones típicas asignan palabras de memoria contiguas para los elementos de arrays (pero esto no es siempre una necesidad). Los rayos pueden ser de longitud fija o reizable.
• A lista vinculada (también llamado lista) es una colección lineal de elementos de datos de cualquier tipo, llamados nodos, donde cada nodo tiene un valor, y apunta al próximo nodo en la lista vinculada. La principal ventaja de una lista enlazada sobre un array es que los valores siempre pueden ser insertados y eliminados eficientemente sin reubicar el resto de la lista. Algunas otras operaciones, como el acceso aleatorio a un determinado elemento, son, sin embargo, más lentas en las listas que en los arrays.
• Un registro (también llamado tuple o struct) es una estructura de datos agregados. Un registro es un valor que contiene otros valores, típicamente en número fijo y secuencia y normalmente indexado por nombres. Los elementos de los registros suelen llamarse campos o miembros. En el contexto de la programación orientada hacia el objeto, los registros son conocidos como estructuras de datos viejas simples para distinguirlos de objetos.
• Mesas de baño, gráficos y árboles binarios.

Soporte de idiomas

La mayoría de los lenguajes ensambladores y algunos lenguajes de bajo nivel, como BCPL (Lenguaje de programación combinado básico), carecen de soporte integrado para estructuras de datos. Por otro lado, muchos lenguajes de programación de alto nivel y algunos lenguajes ensambladores de alto nivel, como MASM, tienen una sintaxis especial u otro soporte incorporado para ciertas estructuras de datos, como registros y matrices. Por ejemplo, los lenguajes C (un descendiente directo de BCPL) y Pascal admiten estructuras y registros, respectivamente, además de vectores (matrices unidimensionales) y matrices multidimensionales.

La mayoría de los lenguajes de programación cuentan con algún tipo de mecanismo de biblioteca que permite que diferentes programas reutilicen las implementaciones de estructuras de datos. Los lenguajes modernos generalmente vienen con bibliotecas estándar que implementan las estructuras de datos más comunes. Algunos ejemplos son la biblioteca de plantillas estándar de C++, Java Collections Framework y Microsoft.NET Framework.

Los lenguajes modernos también suelen admitir la programación modular, la separación entre la interfaz de un módulo de biblioteca y su implementación. Algunos proporcionan tipos de datos opacos que permiten a los clientes ocultar detalles de implementación. Los lenguajes de programación orientados a objetos, como C++, Java y Smalltalk, suelen utilizar clases para este propósito.

Muchas estructuras de datos conocidas tienen versiones concurrentes que permiten que varios subprocesos informáticos accedan a una sola instancia concreta de una estructura de datos simultáneamente.