Estructuras de datos. Visión general y clasificación (A3C34B1D03)

Hasta ahora, todos los datos utilizados en la resolución de problemas se han caracterizado porque eran de un tipo elemental (numérico, alfanumérico o lógico), es decir, solo tenían un valor que representaba una característica determinada del dato; por ejemplo, la edad de una persona. Sin embargo, en la mayoría de las ocasiones, los problemas y sus datos no son tan simples, necesitándose procesar de forma conjunta varias características agrupadas de un mismo elemento; por ejemplo, los datos personales (nombre, apellidos y DNI), la dirección y la edad de una persona. En la práctica, sería extremadamente complicado definir datos independientes para cada uno de sus componentes, pues conllevaría la destrucción de la asociación de las distintas características con un mismo elemento.

Figura 1. Ejemplo de datos agrupados y organizados para representar una entidad.

Además, tan importante como la agrupación de los datos para su manejo es la estructura subyacente, es decir, la forma de relacionar las distintas partes: el nombre, los apellidos y el DNI se relacionan entre sí, para formar una entidad común que representa los datos personales. Gráficamente, lo podríamos representar como ilustra la Figura 1. Para poder procesar datos agrupados según una estructura u organización determinada, surgen las Estructuras de Datos.

Los lenguajes de programación de alto nivel proporcionan varios mecanismos para definir y procesar distintas estructuras de datos. Así, estas se pueden clasificar atendiendo a distintos criterios:

• Según su disposición, pueden ser:
  
  
  • Lineales, caracterizadas por estar organizadas de forma secuencial, unos elementos a continuación de otros. Entre estas destacan, entre otras, por su utilidad, los arrays, y las listas o los diccionarios.
  • No lineales, permitiendo cualquier tipo de disposición, como el caso de los árboles o los grafos.
    
    
• Según su variación en tamaño, pueden ser:
   
  • Estáticas, que se definen antes de la ejecución del programa y su tamaño permanece fijo e inalterable durante su funcionamiento. Las más comunes son los arrays, y los registros.
  • Dinámicas, en las que el número de elementos que las forman se puede modificar durante la ejecución del programa, ampliando o disminuyendo su tamaño. Las listas y los diccionarios son las más conocidas.
    
    
• Según el lugar de almacenamiento, pueden ser:
  
  
  • Volátiles, las que se almacenan en la memoria central. Su principal ventaja es que el tiempo de acceso a ellas es muy pequeño, pero el inconveniente es que desaparecen al finalizar el programa. Por ejemplo, los arrays.
  • Permanentes, las que se almacenan en dispositivos auxiliares, perdurando en el tiempo, como es el caso de los ficheros. El inconveniente es que el tiempo de acceso es mayor que las que se almacenan en memoria central.

La elección de una estructura de datos a la hora de diseñar un programa es una decisión importante, ya que determina las operaciones que se puedan realizar sobre ella. Además, no todas las estructuras son igual de eficientes a la hora de ocupar espacio en memoria ni a la de acceder a su contenido. Todo ello va a condicionar, por tanto, parte del algoritmo que las procesa. Tanto es así, que es famosa la ecuación que refleja la relevancia de las estructuras de datos en la construcción de un programa:

ESTRUCTURAS DE DATOS + ALGORITMOS = PROGRAMAS

A continuación, se describen las estructuras de datos más conocidas según su disposición.

1 |  Arrays o vectores

Un array o vector es una estructura estática que representa una colección homogénea de datos, es decir, que todos los datos son del mismo tipo. Resultan muy útiles para representar varios datos cuyo procesamiento vaya a realizarse de forma similar. Por ejemplo, calcular valores estadísticos sobre las notas de una asignatura de N alumnos de una clase u obtener el número de votos que obtienen los candidatos a unas elecciones. Gráficamente, un vector se puede representar como una colección de celdas numeradas, similar a una colección de contenedores numerados, como muestra la Figura 2. Esta estructura permite definir una colección de variables con un nombre común porque cada una se identifica por la posición que ocupa. En el contexto de la programación, podemos imaginar un array A de tamaño N como una variable con N “compartimentos” identificados cada uno por su posición. Por ejemplo, un array de tamaño 8 sería como ilustra la Figura 3. En él, la variable que ocupa la posición i se identifica por A[i].

Figura 2. Colección de taquillas, ilustrando el concepto de vector.

Figura 3. Ejemplo de array o vector de 8 componentes con posiciones del 1 al 8.

En general, conociendo el nombre del vector y la posición de cada variable, se puede acceder a cada una de ellas de forma directa, es decir, sin tener que “pasar” por las demás. Por tanto, es una estructura de datos muy eficiente que, siempre que se pueda, conviene usar. No obstante, al ser una estructura estática, exige estimar de antemano el número de componentes que tendrá. Esto supone el único inconveniente de los arrays, que nos podemos quedar cortos o, por el contrario, nos podemos pasar, lo que supondría un desperdicio de memoria.

2 |  Listas

Una lista es una secuencia de elementos, en general del mismo tipo, que representa una estructura dinámica, es decir, el número de datos que la forman puede variar durante la ejecución del programa. Esto permite añadir componentes cuando se necesite o liberarlos cuando no hagan falta, lo que supone una ventaja frente a los vectores. Sin embargo, ocupan más espacio en memoria y el acceso a sus elementos no es tan eficiente.

Es una estructura de datos muy útil porque aparecen con mucha frecuencia en la vida real: para almacenar las canciones que te gustan de tu reproductor de música online o los contactos de tu teléfono móvil, por ejemplo.

Las listas se caracterizan porque cada uno de sus elementos contiene un sucesor (salvo el último) y un predecesor (salvo el primero). Además, la posición que ocupa cada elemento en la lista es importante. Por ejemplo, en la lista que representa las clasificaciones de los participantes en una competición deportiva no es lo mismo aparecer en la primera posición que en la última. Respecto a las operaciones que se realizan sobre las listas, las más frecuentes son las que permiten añadir, consultar o eliminar elementos en una posición determinada. También es importante la operación de recorrido, que comienza en el primer elemento y va avanzando hasta el siguiente hasta que se llega al final (de forma similar a como se reproducen las listas de canciones de la Figura 4), y la de ordenación por algún criterio determinado (por ejemplo, por el tiempo que dura cada canción, por el nombre del artista o por la fecha de publicación).

Figura 4. Lista de canciones.

3 |  Pilas

Las pilas son otro tipo de estructuras dinámicas que representan colecciones de elementos también del mismo tipo, pero con la peculiaridad de que sólo se puede acceder al elemento que está “encima” de todos los demás. Basta imaginarse una pila de libros dispuestos como ilustra la Figura 5: si intentamos coger alguno de los que no está justo arriba, la pila se desmorona. Por la misma razón, al añadir un libro nuevo a la pila, hay que hacerlo justo encima de los demás. También son conocidas como estructuras LIFO (del inglés, Last In First Out): el último en entrar es el primero en salir. En programación se utilizan, entre otras cosas, para el tratamiento de expresiones aritméticas y para implementar las funcionalidades de deshacer o rehacer de los editores de texto.

Figura 5. Pila de libros.

4 |  Colas

Las colas son estructuras dinámicas para representar colecciones de elementos del mismo tipo, pero que se diferencian de las pilas en que su comportamiento es FIFO (del inglés, First In First Out): el primero en entrar es el primero en salir. En la vida real, se forma una cola cuando varias personas tienen que ser atendidas por un único dependiente. En el contexto de la programación las colas se utilizan para representar distintos elementos que deben ser atendidos en el orden de llegada: así, los nuevos elementos que llegan a la cola se añaden por el final y, en cada momento, solo se atiende al elemento que ocupa la primera posición. Por ejemplo, para representar los distintos trabajos de impresión que tiene que atender una única impresora compartida.

Figura 6. Cola de personas esperando a ser atendidas.

1 |  Árboles

En ocasiones, los datos que se desean procesar en un programa están relacionados entre sí de forma jerárquica, como ocurre con los empleados de una empresa que ilustra la Figura 7. En estos casos, se dispone de la estructura de datos árbol, que además es dinámica, y que permite representar los datos y sus relaciones en distintos niveles. En un árbol existe un elemento distinguido de los demás, en el nivel superior, que se denomina raíz, y el resto de los elementos se organizan en torno a varios subárboles hijos. En el árbol de la Figura 7, la raíz es el elemento coloreado en negro y los demás elementos están distribuidos en dos subárboles hijos: uno a su izquierda y otro a su derecha. Dependiendo del número de hijos que tenga cada nodo, los árboles pueden ser binarios, cuando todos los nodos tienen dos hijos; ternarios, cuando tienen tres, y así sucesivamente. Cuando el número de hijos de cada nodo no es el mismo se denominan árboles generales, como el de la Figura 7. Los árboles son estructuras muy útiles para representar elementos ordenados, ya que las búsquedas en ellos son muy eficientes. También se utilizan como base de los compiladores y, en los sistemas operativos, para la organización de los archivos.

Figura 7. Organización jerárquica de la plantilla de una empresa.

2 |  Grafo

Un grafo es una estructura de datos dinámica que sirve para representar una colección de datos y cualquier relación binaria no jerárquica que se pueda establecer entre ellos. Un ejemplo claro de grafo es una red social, como ilustra la Figura 8. En ella se aprecian los elementos que forman un grafo: los nodos, que definen los datos (usuarios de la red social), y las aristas o enlaces que conectan dos nodos y que definen la relación entre ellos (podría ser la de “ser seguido por” o la de “sigue a”). Los grafos son una de las estructuras más potentes que existen para representar la información del mundo en el que vivimos, ya que permite modelizar cualquier tipo de red, social o no (de comunicaciones, de transporte, de electricidad); pero además se usan para aplicaciones tan diferentes como la representación de estructuras químicas, la solución de problemas de genética o para el procesamiento del lenguaje natural, por citar algunas. Tanto es así que existe un campo científico dedicado a su estudio, la Teoría de Grafos, que explora conceptos, algoritmos y aplicaciones relacionados con esta estructura de datos.

Figura 8. Las redes sociales son un tipo de grafo.

3 |  Direcciones

Un diccionario es una estructura de datos dinámica que se utiliza para representar colecciones de pares de datos, de forma similar a como se hace en cualquier otro diccionario; por ejemplo, el de la RAE representa la colección de cada palabra de la lengua española junto con su significado; o de cualquier diccionario español-inglés, que asocia cada palabra en español con su equivalente en inglés. En el contexto de la programación, cada entrada en el diccionario lo forman una clave y su valor asociado. Por lo tanto, un diccionario se puede imaginar como una colección de pares (clave, valor). La principal ventaja de estas estructuras radica en que las búsquedas se realizan siempre por la clave y son muy eficientes. Una aplicación básica de los diccionarios podría ser el almacenamiento los usuarios de una aplicación, donde el nombre de usuario sería la clave y su información asociada (datos personales, correo electrónico, password, o fechas de login, entre otros) constituiría el valor vinculado a la clave.

Figura 9. Ejemplo de diccionario.