Foundations
¿Qué es una estructura de datos?
En resumen, es una forma organizada de almacenar y organizar datos en la memoria de la computadora. El objetivo principal de mantenerlos en una estructura de datos es que puedas acceder y operar rapido con tus datos según cada caso o situación.
No hablamos solo de los datos, sino de como operarlos según cada situación.
Estructura de Datos vs ADT (Abstract Data Type)
Una estructura de datos es una implementación concreta de un tipo de dato abstracto (ADT).
Un ADT define un conjunto de operaciones y comportamientos sin especificar cómo se implementan, mientras que una estructura de datos es la implementación real que proporciona la funcionalidad definida por el ADT.
Imágen sacada
En otras palabras, el ADT es la idea o concepto de cómo debería funcionar una estructura de datos, mientras que la estructura de datos es la implementación específica que hace que esa idea funcione en la práctica.
Las ADT como tal son un pensamiento crítico dentro de el entendimiento de la ingeniería de software como tal, ya que más allá de como será la implementación, lo importante es entender el comportamiento que va a tener lo que necesitamos contruir.
Por ejemplo:
El ADT Stack define: push(x), pop(), peek(), isEmpty(). No dice nada de memoria.
Puede implementarse con un array o con una linked list. Ambas son válidas, con trade-offs distintos.
Este es un principio de diseño fundamental: programar contra la abstracción, no contra la implementación. En Java/Kotlin
lo ves constantemente con List<T> vs ArrayList<T> vs LinkedList<T>.
Clasificación de estructuras de datos
Existen muchas formas de clasificar las estructuras de datos, pero las dos formas documentadas que son interesantes de estudiar son la clasificación de organización lógica y por la naturaleza de gestión de la memoria.
Clasificarlos por organización Lógica
Dentro de esta clasificación, tenemos la clasificación por: Lineales y No Lineales.
Lineales
Los datos se organizan en una estructura secuencial, cada dato tiene un predecesor y un sucesor (salvo el caso del primero o el último, también conocidos como los extremos).
Los lineales son los más conocidos en la mayoría de los lenguajes de programación, algunos de los que tenemos aquí son los Array, las Listas, Stacks y Queues.
No Lineales
Los datos se organizan de forma jerárquica o en una estructura de red, no siguen un orden secuencial. En este tipo de estructuras, un dato puede tener múltiples predecesores y sucesores. Algunos ejemplos son los árboles (trees) y los grafos.
Lineal vs No Lineal
Las estructuras de datos lineales tienen dos caminos para tomar: “adelante” o “atras” hasta llegar al principio o fin del camino. Por otro lado, las estructuras no lineales tienen “varios caminos” que pueden tomarse y no solo adelante o atras, se representan mejor como “izquierda”, “derecha”, “arriba”, “abajo” y varios caminos más dependiendo de la cantidad de conexiones que tenga cada nodo.
Clasificarlos por la naturaleza de gestión de la memoria
Otra clasificación es por la naturaleza de gestión de la memoria, dentro de esta clasificación tenemos: Estáticas y Dinámicas.
Esto ya es hablando sobre la implementación, no sobre la organización lógica. Por ejemplo, un array es una estructura de datos lineal, pero puede ser implementada de forma estática o dinámica.
Estáticas
El tamaño se define una vez al momento de ser declarado (usualmente, en tiempo de compilación) y queda así durante todo el programa. No se puede cambiar el tamaño después de la creación. Ejemplo: Array en Java. Esto como tal permiten accesos garantizados a cualquier posición pero no permite hacer un crecimiento o decrecimiento de los mismos, simplemente no están hechos para ser modificados luego de haber sido creados.
Las estáticas al saber todos los datos que van a tener, simplemente los almacenan de forma contigua en la memoria, lo que hace que tengan un acceso de memoria muy eficiente y una buena localidad de caché.
Dinámicas
En las dinámicas la cosa cambia, el tamaño puede ser modificado durante la ejecución del programa. Esto permite agregar o eliminar elementos según sea necesario y es más flexible para manejar datos que pueden crecer o reducirse. Ejemplo: Linked List en Java.
Por otro lado, las estructuras de datos dinámicas suelen requerir más memoria debido a la necesidad de almacenar información adicional por lo que no tienen un acceso de memoria tan eficiente como las estructuras de datos estáticas.
Las dinámicas normalmente suelen tener una peor localidad de caché y un overhead de punteros para poder encontrar lo que necesitamos.