Estructura de datos

En informática , una estructura de datos es una forma de organizar y almacenar datos que se suele elegir para un acceso eficiente a los mismos. ^{[ 1 ] [ 2 ] [ 3 ]} Más precisamente, una estructura de datos es la implementación física de un tipo de dato , incluyendo las especificaciones de la organización de los datos y el formato de almacenamiento, así como las funciones u operaciones para trabajar con estos datos. Las estructuras de datos están estrechamente relacionadas con los tipos de datos abstractos (TDA). ^{[ 4 ]} La estructura de datos describe la representación de los datos en memoria y cómo se llevan a cabo las operaciones, mientras que el TDA describe la forma lógica o la estructura algebraica del tipo de dato —qué operaciones están permitidas y qué resultados producen— sin describir cómo se implementan esas operaciones. ^{[ 4 ]} Algunos autores no utilizan el término "tipo de dato abstracto" y simplemente se refieren a las formas lógica y física de la estructura de datos. ^{[ 5 ]}

Las estructuras de datos eficientes son esenciales para gestionar grandes conjuntos de datos y fundamentales para el diseño de algoritmos. Las bases de datos relacionales suelen utilizar índices de árbol B para la recuperación de datos, ^{[ 6 ]} mientras que las implementaciones de compiladores suelen utilizar tablas hash para buscar identificadores . ^{[ 7 ]} Los sistemas de archivos y los motores de búsqueda hacen un uso extensivo de estructuras de datos especializadas. ^{[ 8 ] [ 9 ]} Rob Pike ha afirmado que la elección de la estructura de datos casi siempre tiene un mayor impacto en la eficiencia que la elección del algoritmo, ya que este último suele ser evidente por sí mismo. ^{[ 10 ]} Las estructuras de datos se utilizan para organizar los datos tanto en la memoria principal ( RAM ) como en el almacenamiento secundario (como los discos). ^{[ 11 ]}

La implementación de una estructura de datos implica escribir un conjunto de subrutinas —como inserción, eliminación, recorrido o búsqueda— que crean y manipulan instancias de dicha estructura. Las estructuras de datos pueden implementarse utilizando diversos lenguajes y técnicas de programación. Una estructura de datos se corresponde directamente con una única implementación concreta, a diferencia de un TAD que describe el comportamiento y las operaciones independientemente de cualquier implementación particular. Puede haber múltiples estructuras de datos concretas para el mismo TAD; por ejemplo, una lista enlazada o un arreglo redimensionable para el TAD lista. ^{[ 12 ]} Por lo tanto, la eficiencia de una estructura de datos está estrechamente ligada a su implementación concreta y debe evaluarse mediante pruebas comparativas y simulaciones teóricas. ^{[ 13 ]}

Las estructuras de datos generalmente dependen de la capacidad de una computadora para almacenar y acceder a datos a través de direcciones de memoria (especificadas por un puntero —una cadena de bits— o, de forma más abstracta, mediante referencias ) que pueden almacenarse en memoria y ser manipuladas por el programa. Por ejemplo, los arreglos y registros almacenan elementos en ubicaciones de memoria contiguas, lo que requiere una disposición rígida pero permite un acceso indexado rápido mediante el cálculo de la dirección a través de operaciones aritméticas . En contraste, las estructuras de datos enlazadas (como las listas enlazadas y los árboles) almacenan direcciones de elementos relacionados dentro de su estructura, lo que permite un uso flexible de la memoria y un redimensionamiento dinámico. Estos diferentes métodos de estructuración de datos presentan diferentes ventajas y desventajas, y se adaptan a diferentes tareas. Por ejemplo, la asignación de memoria contigua en los arreglos facilita las operaciones rápidas de acceso y modificación, lo que optimiza el rendimiento en escenarios de procesamiento de datos secuenciales. ^{[ 14 ]}

Existen numerosos tipos de estructuras de datos, generalmente construidas a partir de tipos de datos primitivos más simples . Algunos ejemplos conocidos son: ^{[ 15 ]}

• Un array es una serie de elementos ordenados de forma específica, generalmente todos del mismo tipo (dependiendo del lenguaje, los elementos individuales pueden estar obligados a ser del mismo tipo o pueden ser de casi cualquier tipo). Se accede a los elementos mediante un índice entero que especifica el elemento deseado. Las implementaciones típicas asignan palabras de memoria contiguas para los elementos de los arrays (aunque esto no siempre es necesario). Los arrays pueden tener una longitud fija o ser redimensionables.
• Una lista enlazada (también llamada simplemente lista ) es una colección lineal de elementos de datos de cualquier tipo, denominados nodos, donde cada nodo tiene un valor y apunta al siguiente nodo de la lista. La principal ventaja de una lista enlazada sobre un array es que los valores se pueden insertar y eliminar de forma eficiente sin necesidad de reubicar el resto de la lista. Sin embargo, ciertas operaciones, como el acceso aleatorio a un elemento específico, son más lentas en las listas que en los arrays.
• Un registro (también llamado tupla o estructura ) es una estructura de datos agregada . Un registro es un valor que contiene otros valores, generalmente en número y secuencia fijos, y normalmente indexados por nombres. Los elementos de los registros se denominan habitualmente campos o miembros . En el contexto de la programación orientada a objetos , los registros se conocen como estructuras de datos simples para distinguirlos de los objetos. ^{[ 16 ]}
• Las tablas hash , también conocidas como mapas hash, son estructuras de datos que permiten la recuperación rápida de valores a partir de claves. Utilizan una función hash para asignar claves a índices en un array, lo que permite un acceso en tiempo constante en promedio. Las tablas hash se utilizan comúnmente en diccionarios, cachés e indexación de bases de datos. Sin embargo, pueden producirse colisiones de hash, lo que puede afectar su rendimiento. Para gestionar estas colisiones, se emplean técnicas como el encadenamiento y el direccionamiento abierto.
• Los grafos son conjuntos de nodos conectados por aristas que representan relaciones entre entidades. Se pueden usar para modelar redes sociales, redes informáticas y redes de transporte, entre otras cosas. Están compuestos por vértices (nodos) y aristas (conexiones entre nodos). Los grafos pueden ser dirigidos o no dirigidos, y pueden tener ciclos o ser acíclicos. Los algoritmos de recorrido de grafos incluyen la búsqueda en amplitud y la búsqueda en profundidad.
• Las pilas y las colas son tipos de datos abstractos que se pueden implementar mediante arreglos o listas enlazadas. Una pila tiene dos operaciones principales: insertar (añadir un elemento a la parte superior de la pila) y extraer (eliminar el elemento superior de la pila), que siguen el principio LIFO (último en entrar, primero en salir). Las colas tienen dos operaciones principales: encolar (añadir un elemento al final de la cola) y desencolar (eliminar un elemento del principio de la cola), que siguen el principio FIFO (primero en entrar, primero en salir).
• Los árboles representan una organización jerárquica de elementos. Un árbol consta de nodos conectados por aristas, donde un nodo es la raíz y todos los demás forman subárboles. Los árboles se utilizan ampliamente en diversos algoritmos y escenarios de almacenamiento de datos. Los árboles binarios (en particular, los montículos ), los árboles AVL y los árboles B son algunos tipos populares de árboles. Permiten una búsqueda, ordenación y representación jerárquica de datos eficiente y óptima.
• Un trie , o árbol de prefijos, es un tipo especial de árbol que se utiliza para recuperar cadenas de caracteres de forma eficiente. En un trie, cada nodo representa un carácter de una cadena, y las aristas entre los nodos representan los caracteres que los conectan. Esta estructura es especialmente útil para tareas como el autocompletado, la corrección ortográfica y la creación de diccionarios. Los tries permiten realizar búsquedas y operaciones rápidas basadas en prefijos de cadenas.

La mayoría de los lenguajes ensamblador y algunos lenguajes de bajo nivel , como BCPL (Basic Combined Programming Language), carecen de soporte integrado para estructuras de datos. Por otro lado, muchos lenguajes de programación de alto nivel y algunos lenguajes ensamblador de nivel superior, como MASM , cuentan con sintaxis especial u otro tipo de soporte integrado para ciertas estructuras de datos, como registros y matrices. Por ejemplo, los lenguajes C (descendiente directo de BCPL) y Pascal admiten estructuras y registros, respectivamente, además de vectores ( matrices unidimensionales ) y matrices multidimensionales. ^{[ 17 ] [ 18 ]}

La mayoría de los lenguajes de programación incluyen algún tipo de mecanismo de biblioteca que permite reutilizar las implementaciones de estructuras de datos en diferentes programas. Los lenguajes modernos suelen venir con bibliotecas estándar que implementan las estructuras de datos más comunes. Algunos ejemplos son la Biblioteca de Plantillas Estándar de C++ , el Marco de Colecciones de Java y el Marco .NET de Microsoft .

Los lenguajes modernos también suelen admitir la programación modular , es decir, 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 los detalles de implementación. Los lenguajes de programación orientados a objetos , como C++ , Java y Smalltalk , suelen utilizar clases para este fin.

Muchas estructuras de datos conocidas tienen versiones concurrentes que permiten que múltiples hilos de computación accedan simultáneamente a una única instancia concreta de una estructura de datos. ^{[ 19 ]}

• Peter Brass, Estructuras de datos avanzadas , Cambridge University Press , 2008, ISBN 978-0521880374
• Donald Knuth , El arte de la programación informática , vol. 1. Addison-Wesley , 3.ª edición, 1997, ISBN 978-0201896831
• Dinesh Mehta y Sartaj Sahni , Manual de estructuras de datos y aplicaciones , Chapman and Hall / CRC Press , 2004, ISBN 1584884355
• Niklaus Wirth , Algoritmos y estructuras de datos , Prentice Hall , 1985, ISBN 978-0130220059

• Estructuras de datos abiertas por Pat Morin
• GH Gonnet y R. Baeza-Yates , Manual de algoritmos y estructuras de datos en Pascal y C , segunda edición, Addison-Wesley, 1991, ISBN 0-201-41607-7
• Ellis Horowitz y Sartaj Sahni, Fundamentos de estructuras de datos en Pascal , Computer Science Press , 1984, ISBN 0-914894-94-3

• Descripciones del Diccionario de Algoritmos y Estructuras de Datos
• Curso de estructuras de datos
• Un análisis de las estructuras de datos desde la perspectiva de .NET
• Schaffer, C. Estructuras de datos y análisis de algoritmos