Colección (tipo de datos abstractos) - Collection (abstract data type)

En ciencias de la computación , una colección es una agrupación de un número variable de elementos de datos (posiblemente cero) que tienen algún significado compartido para el problema que se está resolviendo y necesitan ser operados juntos de alguna manera controlada. Generalmente, los elementos de datos serán del mismo tipo o, en los lenguajes que admiten la herencia, se derivarán de algún tipo de ancestro común. Una colección es un concepto aplicable a los tipos de datos abstractos y no prescribe una implementación específica como una estructura de datos concreta , aunque a menudo existe una opción convencional (ver Contenedor para la discusión de la teoría de tipos ).

Los ejemplos de colecciones incluyen listas , conjuntos , conjuntos múltiples , árboles y gráficos .

Las matrices (o tablas) de tamaño fijo generalmente no se consideran una colección porque contienen una cantidad fija de elementos de datos, aunque comúnmente juegan un papel en la implementación de las colecciones. Las matrices de tamaño variable generalmente se consideran colecciones.

Colecciones lineales

Muchas colecciones definen un orden lineal particular, con acceso a uno o ambos extremos. La estructura de datos real que implementa dicha colección no necesita ser lineal; por ejemplo, una cola de prioridad a menudo se implementa como un montón , que es una especie de árbol. Las colecciones lineales importantes incluyen:

Liza

En una lista, el orden de los elementos de datos es significativo. Se permiten elementos de datos duplicados. Ejemplos de operaciones en listas son buscar un elemento de datos en la lista y determinar su ubicación (si está presente), eliminar un elemento de datos de la lista, agregar un elemento de datos a la lista en una ubicación específica, etc. Las operaciones en la lista deben ser la adición de elementos de datos en un extremo y la eliminación de elementos de datos en el otro, generalmente se denominará cola o FIFO . Si las operaciones principales son la adición y eliminación de elementos de datos en un solo extremo, se denominará pila o LIFO . En ambos casos, los elementos de datos se mantienen dentro de la colección en el mismo orden (a menos que se eliminen y se vuelvan a insertar en otro lugar), por lo que estos son casos especiales de la colección de listas. Otras operaciones especializadas en listas incluyen la clasificación, donde, nuevamente, el orden de los elementos de datos es de gran importancia.

Pilas

Una pila es una estructura de datos LIFO con dos operaciones principales: empujar , que agrega un elemento al "top" de la colección, y pop , que elimina el elemento superior.

Colas

Colas de prioridad

En una cola de prioridad, las pistas del elemento de datos mínimo o máximo en la colección se mantienen, de acuerdo con algún criterio de orden, y el orden de los otros elementos de datos no importa. Uno puede pensar en una cola de prioridad como una lista que siempre mantiene el mínimo o el máximo en la cabeza, mientras que los elementos restantes se guardan en una bolsa.

Colas de dos extremos

Colas de prioridad de dos extremos

Colecciones asociativas

En cambio, otras colecciones pueden interpretarse como una especie de función: dada una entrada, la colección produce una salida. Las colecciones asociativas importantes incluyen:

Un conjunto puede interpretarse como un multiset especializado, que a su vez es un arreglo asociativo especializado, en cada caso limitando los valores posibles, considerando un conjunto representado por su función indicadora .

Conjuntos

En un conjunto, el orden de los elementos de datos no importa (o no está definido), pero no se permiten elementos de datos duplicados. Ejemplos de operaciones en conjuntos son la adición y eliminación de elementos de datos y la búsqueda de un elemento de datos en el conjunto. Algunos idiomas admiten conjuntos directamente. En otros, los conjuntos se pueden implementar mediante una tabla hash con valores ficticios; sólo las claves se utilizan para representar el conjunto.

Multijuegos

En un conjunto múltiple (o bolsa), como en un conjunto, el orden de los elementos de datos no importa, pero en este caso se permiten elementos de datos duplicados. Ejemplos de operaciones en conjuntos múltiples son la adición y eliminación de elementos de datos y la determinación de cuántos duplicados de un elemento de datos en particular están presentes en el conjunto múltiple. Los conjuntos múltiples se pueden transformar en listas mediante la acción de ordenar.

Matrices asociativas

En una matriz asociativa (o mapa, diccionario, tabla de búsqueda), como en un diccionario, una búsqueda en una clave (como una palabra) proporciona un valor (como una definición). El valor puede ser una referencia a una estructura de datos compuesta. Una tabla hash suele ser una implementación eficiente y, por lo tanto, este tipo de datos a menudo se conoce como "hash".

Gráficos

En un gráfico, los elementos de datos tienen asociaciones con uno o más elementos de datos en la colección y son algo así como árboles sin el concepto de una raíz o una relación padre-hijo, de modo que todos los elementos de datos son pares. Ejemplos de operaciones en gráficos son recorridos y búsquedas que exploran las asociaciones de elementos de datos en busca de alguna propiedad específica. Los gráficos se utilizan con frecuencia para modelar situaciones del mundo real y para resolver problemas relacionados. Un ejemplo es el protocolo de árbol de expansión , que crea una representación gráfica (o en malla) de una red de datos y determina qué asociaciones entre los nodos de conmutación deben romperse para convertirlo en un árbol y así evitar que los datos circulen en bucles.

Árboles

En un árbol, que es un tipo especial de gráfico, un elemento de datos raíz tiene asociado cierto número de elementos de datos que, a su vez, tienen asociados algunos otros elementos de datos en lo que con frecuencia se considera una relación padre-hijo . Cada elemento de datos (que no sea la raíz) tiene un solo padre (la raíz no tiene padre) y algún número de hijos, posiblemente cero. Ejemplos de operaciones en árboles son la adición de elementos de datos para mantener una propiedad específica del árbol para realizar la clasificación, etc. y recorridos para visitar elementos de datos en una secuencia específica.

Las colecciones de árboles se pueden utilizar para almacenar datos jerárquicos de forma natural, que se presentan en forma de árbol, como sistemas de menús y archivos en directorios en un sistema de almacenamiento de datos.

Los árboles especializados se utilizan en varios algoritmos. Por ejemplo, el tipo de montón usa una especie de árbol llamado montón .

Concepto abstracto versus implementación

Como se describe aquí, una colección y los diversos tipos de colecciones son conceptos abstractos. Existe en la literatura una confusión considerable entre los conceptos abstractos de la informática y sus implementaciones específicas en varios lenguajes o clases de lenguajes. Las afirmaciones de que colecciones como listas, conjuntos, árboles, etc. son estructuras de datos, tipos de datos abstractos o clases deben leerse teniendo esto en cuenta. Las colecciones son ante todo abstracciones que son útiles para formular soluciones a problemas informáticos. Visto desde esta perspectiva, conservan vínculos importantes con los conceptos matemáticos subyacentes que pueden perderse cuando el foco está en la implementación.

Por ejemplo, una cola de prioridad a menudo se implementa como un montón, mientras que una matriz asociativa a menudo se implementa como una tabla hash, por lo que esta implementación preferida a menudo se refiere a estos tipos abstractos como un "montón" o un "hash", aunque esto no es estrictamente correcto.

Implementaciones

Algunas colecciones pueden ser tipos de datos primitivos en un lenguaje, como listas, mientras que las colecciones más complejas se implementan como tipos de datos compuestos en bibliotecas, a veces en la biblioteca estándar . Ejemplos incluyen:

Referencias

enlaces externos