Estructura de datos
Artículo
Discusión
Leer
Editar
Ver historial
Herramientas
Ejemplo de tabla de hash.
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.[5]
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,[6] es
decir, es una estructura algebraica de datos.
Descripción
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 sirven de base para los tipos de datos abstractos (ADT,
del inglés abstract data types). Los ADT definen la forma lógica del tipo de datos.
La estructura de datos implementa la forma física del tipo de datos.[7]
Los distintos tipos de estructuras de datos se adaptan a distintos tipos de
aplicaciones, y algunas están altamente especializadas para tareas específicas. Por
ejemplo, las bases de datos relacionales utilizan habitualmente índices de árbol B
para la recuperación de datos,[8] mientras que las implementaciones del compilador
suelen utilizar tablas hash para buscar identificadores.[9]
Las estructuras de datos proporcionan un medio para gestionar grandes cantidades de
datos de forma eficiente para usos como grandes bases de datos y servicios de
indexación de Internet. Normalmente, las estructuras de datos eficientes son clave
para diseñar algoritmos eficientes. Algunos métodos de diseño formales y lenguajes
de programación enfatizan las estructuras de datos, más que 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 la
información almacenada tanto en la memoria principal como en la memoria secundaria.
[10]
Tipos de estructura de datos
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.[11]
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.
Ejemplos
La jerarquía de tipos estándar.[12]
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, en inglés 'Last In, First Out'). 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, en inglés 'First In, First
Out').
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.
Soporte en los lenguajes
Ejemplo de lenguaje ensamblador.
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.[13][14]
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[nota 1][15] y las bibliotecas .NET
de Microsoft.
Estructuras de datos en programación
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"
Listado de estructuras de datos
Vectores (matriz o arreglo)
Registro
Tipo de dato algebraico
Listas Enlazadas
Listas Simples
Listas Doblemente Enlazadas
Listas Circulares
una lista por salto (skip list).
Listas por saltos (Skip lists)
Representación simple de una pila.
Pilas (stack)
Colas (queue)
Cola de prioridades
Árboles
Ejemplo de un árbol binario completo.
Árboles Binarios
Árbol binario de búsqueda
Árbol binario de búsqueda equilibrado
Árboles Rojo-Negro
Árboles AVL
Rotación en un árbol biselado
Árboles biselados (Árboles Splay)
Árboles multicamino (o multirrama)
Ejemplo de árbol B.
Árboles B
Árboles B+
Conjuntos (sets)
Grafo etiquetado con 6 vértices y 7 aristas.
Grafos
Diccionarios [nota 2]
Tabla de racimo
Montículos (o heaps)
Montículo binario
Montículo binomial
Ejemplo de un montículo de Fibonacci.
Montículo de Fibonacci
Montículo suave
Montículo 2-3 [nota 3]
Otros
Un ejemplo de buffer circular.
Buffer circular
Estructura de datos para conjuntos disjuntos (algoritmo Unión-Buscar, Union-find)
Véase también
Dato
Metadatos
algoritmo
lenguaje de programación
tipo de dato
unión de datos
Modelo de datos
Estructuras de datos persistentes
Modelo entidad-relación
Estructuras de control
ASN.1
Seguridad de la información
Notas
El marco de colecciones de Java es un conjunto de clases e interfaces que
implementan estructuras de datos de colecciones que se pueden reutilizar
comúnmente.(«Lesson: Introduction to Collections». Oracle Corporation. Consultado
el 22 de diciembre de 2010.) Aunque se lo conoce como marco, funciona como una
biblioteca. El marco de colecciones proporciona interfaces que definen varias
colecciones y clases que las implementan.
En informática, una matriz asociativa, un mapa, una tabla de símbolos o un
diccionario es un tipo de datos abstracto que almacena una colección de pares
(clave, valor), de modo que cada clave posible aparece como máximo una vez en la
colección. En términos matemáticos, una matriz asociativa es una función con
dominio finito.(Collins, Graham; Syme, Donald (1995). «A theory of finite maps».
Higher Order Logic Theorem Proving and Its Applications. Lecture Notes in Computer
Science (en inglés) 971. pp. 122-137. ISBN 978-3-540-60275-0. doi:10.1007/3-540-
60275-5_61.) Admite operaciones de "búsqueda", "eliminación" e "inserción".
En informática, un montículo 2-3 es una estructura de datos, una variación del
montículo binario, diseñada en 1999 por Tadao Takaoka (Profesor de Computer science
en la Universidad de Canterbury). La estructura es similar al montículo de
Fibonacci y viene del árbol 2-3.
Referencias
Peláez, Canek (2018). Facultad de Ciencias, ed. Estructuras de datos con Java
moderno. Comportamiento + objetos = programas. Ciudad de México: Universidad
Nacional Autónoma de México. ISBN 978-607-30-0966-9.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford
(2009). Introduction to Algorithms, Third Edition (3rd edición). The MIT Press.
ISBN 978-0262033848.
Black, Paul E. (15 de diciembre de 2004). «data structure». En Pieterse, Vreda;
Black, Paul E., eds. Dictionary of Algorithms and Data Structures [online].
National Institute of Standards and Technology. Consultado el 6 de noviembre de
2018.
«Data structure». Encyclopaedia Britannica. 17 de abril de 2017. Consultado el 6
de noviembre de 2018.
Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching
(2nd edición). Addison-Wesley. pp. 513-558. ISBN 978-0-201-89685-5.
Wegner, Peter; Reilly, Edwin D. (29 de agosto de 2003). Encyclopedia of Computer
Science. Chichester, UK: John Wiley and Sons. pp. 507-512. ISBN 978-0470864128.
«Abstract Data Types». Virginia Tech - CS3 Data Structures & Algorithms. Archivado
desde el original el 10 de febrero de 2023. Consultado el 15 de febrero de 2023.
Gavin Powell (2006). «Chapter 8: Building Fast-Performing Database Models».
Beginning Database Design (en inglés). Wrox Press. ISBN 978-0-7645-7490-0.
«1.5 Applications of a Hash Table». University of Regina - CS210 Lab: Hash Table
(en inglés). Archivado desde el original el 27 de abril de 2021. Consultado el 14
de junio de 2018.
«When data is too big to fit into the main memory». Indiana University Bloomington
- Data Structures (C343/A594) (en inglés). Archivado desde el original el 10 de
abril de 2018.
«Estructuras de datos dinámicas/Texto completo».
"Documentation » The Python Language Reference » 3. Data model" (Documentación »
Referencia del lenguaje Python » 3. Modelo de datos) (en inglés)
https://docs.python.org/3/reference/datamodel.html#the-standard-type-hierarchy
«The GNU C Manual». Free Software Foundation. Consultado el 23 de marzo de 2016.
«Free Pascal: Reference Guide». Free Pascal. Consultado el 23 de marzo de 2016.
«Java tutorial. Trail: Collections». Oracle. Consultado el 23 de marzo de 2016.
Bibliografía
Peter Brass, Advanced Data Structures, Cambridge University Press, 2008, ISBN 978-
0521880374
Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3ra edición,
1997, ISBN 978-0201896831
Dinesh Mehta and Sartaj Sahni, Handbook of Data Structures and Applications,
Chapman and Hall/CRC Press, 2004, ISBN 1584884355
Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985, ISBN 978-
0130220059
Enlaces externos
Descripciones del Dictionary of Algorithms and Data Structures (en inglés)
Curso de estructuras de datos (en inglés)
Gaston Gonnet y Ricardo Baeza-Yates, Handbook of Algorithms and Data Structures -
in Pascal and C, second edition, Addison-Wesley, 1991, ISBN 0-201-41607-7 (en
inglés)
