Estructuras de Datos: Tipos, Clasificación y Organización

¿Qué es una estructura de datos?

Una estructura de datos es un conjunto de elementos de información dotado de una organización.

Tipos de estructuras de datos según sus elementos:

• Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
• Heterogéneas: Cuando son de tipos diferentes.

Elementos Individuales: Nodos

Los componentes de una estructura de datos reciben el nombre de nodos. El nodo es la unidad de referencia básica de la estructura. Conceptualmente, un nodo puede ser desde un elemento muy simple a uno muy complejo, con una elaborada estructura interna.

Ejemplo: Una página web puede ser un nodo de un hipertexto.

Clasificación de Estructuras de Datos por Componentes

Por el tipo de sus elementos, las estructuras de datos pueden ser:

• Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
• Heterogéneas: Cuando son de tipos diferentes.

Estructura Lógica vs. Estructura de Representación

La estructura lógica se refiere a cómo se relacionan los datos desde el punto de vista conceptual.

La estructura de representación trata de los mecanismos de implementación en un ordenador.

La estructura de representación influye fuertemente en la eficiencia de los algoritmos que manipulen la estructura de datos.

Ambos mecanismos de estructuración se pueden mezclar para formar conglomerados cada vez más complejos (arrays de records, record con campos array). A un nivel lógico superior se encuentra el concepto de encadenamiento, con el que se pueden formar estructuras más complejas al permitir que cada nodo pueda indicar su relación lógica con otros.

Las estructuras encadenadas como los arrays pueden representar colecciones de elementos de un mismo tipo, con la ventaja de que se puede añadir o quitar un nodo en cualquier punto de la estructura sólo con modificar algunos enlaces, sin que los demás nodos tengan que cambiar su ubicación física.

Criterios de Clasificación de Estructuras de Datos

Las estructuras de datos se clasifican según varios criterios:

Por el tipo de sus elementos:

• Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
• Heterogéneas: Cuando son de tipos diferentes.

Por el modo de organización y relación entre sus elementos:

• Estructura Lineal: Cuando la relación entre sus componentes es de 1:1. Los elementos se encuentran “alineados”, cada uno tiene un sucesor que es único y un predecesor también único. Las relaciones sucesor y predecesor no están definidas para el último y el primer elemento. Ejemplos: Un vector, una lista encadenada.
• Estructuras Jerárquicas: Generalmente conocidas como árboles. Las relaciones son 1:n (de uno a muchos). Cuando no están vacías, existe un nodo que es el punto de inicio o raíz de la jerarquía. El resto de los nodos se agrupan con respecto a él en subconjuntos que son a su vez árboles. Este tipo de estructura es típica del organigrama de muchas organizaciones.
• Estructuras Multirelacionales: Las relaciones son n:n (de muchos a muchos). Cada nodo de la estructura se puede relacionar libremente con cualquier otro elemento, incluso consigo mismo. Es un tipo de estructura que se da frecuentemente en todo tipo de redes de comunicaciones.

Clasificación según la Enciclopedia of Computer Science:

• ED Estáticas: Formada por un número fijo de elementos contiguos. Ej: array.
• ED Dinámicas: Formada por un número variable de elementos no contiguos relacionados mediante encadenamiento.

Según la memoria utilizada:

• Estructuras de datos en memoria interna.
• Estructuras de datos en memoria externa, diseñadas teniendo en cuenta la lentitud de acceso a dispositivos externos --como, por ejemplo, un disco--, tratan de optimizar la transferencia de información.

Estas consideraciones conducen a la utilización de mecanismos como la paginación de la estructura, consistentes en agrupar varios elementos en una unidad de acceso -la página- de tamaño aproximado al de la unidad de transferencia con el disco.