En programación de computadoras , 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 deben operarse juntos de alguna manera controlada. Generalmente, los elementos de datos serán del mismo tipo o, en los idiomas que soportan la herencia, se derivarán de algún tipo de ancestro común. Una colección es un concepto aplicable a 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 (consulte Contenedor para una discusión sobre la teoría de tipos ).
Ejemplos de colecciones incluyen listas , conjuntos , multiconjuntos , á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 desempeñan un papel en la implementación de las colecciones. Las matrices de tamaño variable generalmente se consideran colecciones. [ cita necesaria ]
Muchas colecciones definen un ordenamiento lineal particular, con acceso a uno o ambos extremos. La estructura de datos real que implementa dicha colección no tiene por qué 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:
En una lista, el orden de los elementos de datos es importante. 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. Si el principal Las operaciones en la lista deben consistir en agregar elementos de datos en un extremo y eliminar 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 llamará 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) y, por lo tanto, 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.
Una pila es una estructura de datos LIFO con dos operaciones principales: push , que agrega un elemento a la "parte superior" de la colección, y pop , que elimina el elemento superior.
En una cola de prioridad, las pistas del elemento de datos mínimo o máximo de la colección se mantienen, según algún criterio de ordenación, y el orden de los demás elementos de datos no importa. Se puede pensar en una cola de prioridad como una lista que siempre mantiene el mínimo o el máximo al principio, mientras que los elementos restantes se guardan en una bolsa.
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 multiconjunto especializado, que a su vez es una matriz asociativa especializada, en cada caso limitando los valores posibles, considerando un conjunto representado por su función indicadora .
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 pueden implementarse mediante una tabla hash con valores ficticios; sólo las claves se utilizan para representar el conjunto.
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.
En una matriz asociativa (o mapa, diccionario, tabla de búsqueda), como en un diccionario, una búsqueda de una clave (como una palabra) proporciona un valor (como una definición). El valor podría 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".
En un gráfico, los elementos de datos tienen asociaciones con uno o más elementos de datos de la colección y son algo así como árboles sin el concepto de raíz o 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 resolver problemas relacionados. Un ejemplo es el protocolo de árbol de expansión , que crea una representación gráfica (o malla) de una red de datos y determina qué asociaciones entre los nodos de conmutación deben romperse para convertirla en un árbol y así evitar que los datos circulen en bucles.
En un árbol, que es un tipo especial de gráfico, un elemento de datos raíz tiene asociado un cierto número de elementos de datos que, a su vez, tienen asociados otros elementos de datos en lo que frecuentemente 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 un cierto 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 de forma natural datos jerárquicos, que se presentan en forma de árbol, como sistemas de menús y archivos en directorios de un sistema de almacenamiento de datos.
Se utilizan árboles especializados en varios algoritmos. Por ejemplo, la clasificación del montón utiliza una especie de árbol llamado montón .
Como se describe aquí, una colección y los distintos 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 tipos 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 resultan útiles para formular soluciones a problemas informáticos. Vistos desde esta perspectiva, conservan vínculos importantes con conceptos matemáticos subyacentes que pueden perderse cuando la atención se centra 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 "montón" o "hash". esto no es estrictamente correcto.
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:
Las colecciones se implementan como TIPO. Como ocurre con cualquier tipo definido por el programador, primero debe definir el tipo; entonces puedes declarar instancias de ese tipo.