Disclaimer: En internet hay mucha cantidad de contenido sobre programación y tecnología. Mi intención es aprender de todo eso, y cuando pueda, pagar cursos para profundizar.
Siempre que sea posible voy a mencionar las fuentes de donde estoy aprendiendo, porque todo lo que comparto en estos capítulos nace del trabajo de otras personas que dedicaron su tiempo a enseñar.
Por otro lado, también soy humana y puedo equivocarme 😅. Si en algún momento explico algo de forma incorrecta, ¡las correcciones y sugerencias son más que bienvenidas!
BIG O
Para entender las estructuras de datos, tenemos primero que entender que es BIG O. BIG O es un medidor y lo que mide es → Qué tan bien están funcionando las estructuras de datos en diferentes escenarios (eficiencia y velocidad)
Para entender mejor esta medicion, podemos usar como ejemplo Google Maps. Si yo quisiera llegar a Cordoba puedo ver que:
- en auto son 12 horas
- en avion son 2 horas
- en moto son 11 horas
- en tren son 8 horas
Por lo tanto se que lo mas eficiente y lo mas rapido es el avion. Entonces sabemos que hay transportes “mejores” para distintos escenarios, en este caso para llegar mas rapido a un lugar. Lo mismo ocurre con las estructuras de datos, estan mejoradas para distintos escenarios.
Entonces para medir cuan rapido es un auto lo hacemos por kilometros por hora y para medir las estructuras de datos lo hacemos con BIG O.
Time Complexity
Para medir el tiempo tenemos las siguientes medidas:
O(1) → Que seria lo MAS rapido que un algoritmo puede funcionar (hablamos de velocidad de la luz) → Significa que la operacion va a tardar lo mismo sin importar la data que haya.
Por ejemplo si tenemos una lista de supermercado y queremos buscar el PRIMERO, no nos importa la cantidad de elementos que tengamos en la lista, podemos tener 20 o 100, la operacion es sacar el primero.
O(n) → N seria la cantidad de datos que tenemos (hablamos de un tiempo lineal) → Si la cantidad de datos aumenta, aumenta la cantidad de tiempo de la operacion.
Por ejemplo si tenemos una lista de nombres y estamos buscando “Paula Alvarez”, tenemos que recorrer toda la lista hasta encontrar el nombre. Cuantos mas nombres tengamos en nuestra lista, mas va a tardar nuestra operacion.
O(n2) → Cuando cada item de nuestra data tiene que interactuar con otros items (lo mas lento de lo mas lento) → Por ejemplo si tenemos una clase con alumnos y cada uno tiene que saludarse con su compañero, cuantos mas alumnos tengamos, mas va a tardar la operacion, ya que todos tienen que saludarse con todos 🤝
O(log n) → Buscamos una palabra en el diccionario, entonces vamos al medio donde hay una palabra que esta cerca de la que buscamos, entonces pensamos “esta palabra esta antes o despues?” y ese proceso lo repetimos hasta que encontramos nuestra palabra.
Ahora que sabemos nuestras medidas de tiempo podemos empezar a ver algunas estructuras de datos y como funcionan al hacer tareas como agregar, eliminar, acceder a un dato etc...
Array
Tambien conocidos como Vectores (unidimensionales), son una coleccion ordenada de datos, a los cuales podemos acceder de forma directa usando un indice.
En la mayoría de los lenguajes (como Java o C), los arrays tienen un tamaño definido al momento de su creación. Esto se debe a que se almacenan en posiciones contiguas de memoria, por lo que no pueden redimensionarse dinámicamente sin crear una nueva estructura.
- Para acceder a cada elemento se hace por el indice que comienza en 0, cada elemento esta uno al lado del otro. Por lo tanto para acceder a los datos o un elemento en particular → es super rapido O(1)
- Si queremos agregar un elemento pisando a otro → es super rapido O(1)
- Ahora si queremos por ejemplo agregar un elemento sin pisar uno existente, ahi ya tenemos que crear una copia de nuestro array original y en esa copia agregar este nuevo valor, ya hablamos de un tiempo de O(n)
- Eliminar un elemento es O(n) porque si eliminamos un elemento del medio, se tiene que volver a formar (re-size) todo el array, es decir a partir del elemento que eliminamos los indices cambian.
- Si eliminamos el ultimo elemento del array, es O(1) porque simplemente se elimina el ultimo indice y listo
Ejemplo → Los casilleros en las universidades → Si vos queres agregar un casillero en medio de los que estan, no podes y si queres agregar uno al final por ejemplo tendrias que romper la pared para que entren mas, pero por otro lado si quisieras que el casillero 2 sea ahora el 5, podemos pisar ese valor.
Linked List
Una Linked List es una estructura de datos donde los elementos (llamados nodos) están conectados entre sí mediante referencias o punteros.
Cada nodo guarda un valor y una referencia al siguiente nodo, formando una cadena.
Hay que pensar las Linked list como un tren, para ir a un vagon tenemos que pasar por los otros, no podemos teletransportarnos.
- Cada elemento se guarda en un nodo, y cada nodo contiene un valor y un puntero (o referencia) al siguiente nodo.
- Agregar o eliminar un elemento cuando ya tenemos la referencia del nodo es O(1), porque no necesitamos rearmar toda la estructura (a diferencia de los arrays). Sin embargo, si primero tenemos que buscar el nodo de referencia, esa búsqueda tiene un costo de O(n).
- Buscar o acceder a un elemento también es O(n), ya que debemos recorrer los nodos uno a uno desde el principio hasta llegar al que buscamos, porque en esta estructura no existen los índices.
Ejemplo → Imaginemos que cada vagón del tren está conectado con un gancho al siguiente. Si querés agregar un nuevo vagón en el medio, solo tenés que abrir un gancho y enganchar el nuevo. Pero si querés encontrar un vagón específico, tenés que recorrerlos desde el primero hasta llegar a él.
En resumen, las Linked Lists son más flexibles que los arrays para agregar o eliminar elementos, pero más lentas cuando necesitamos acceder a posiciones específicas.
Stack / Pila
Una Stack o Pila es una estructura de datos donde los elementos se organizan siguiendo el principio LIFO (Last In, First Out), es decir: el último elemento en entrar es el primero en salir.
Podemos pensarla como un tubo de Papas Pringles: la última papa que metés es la primera que sacás.
- Acceder o buscar un elemento específico: Es O(n), porque no existe un índice y tenemos que recorrer la pila elemento por elemento.
- Agregar un elemento: Es O(1), ya que se agrega directamente “encima” de la pila, sin afectar el resto de la estructura.
- Eliminar el ultimo elemento: También es O(1), porque simplemente se retira el elemento de arriba de todo, sin necesidad de reacomodar nada.
Ejemplo → Una pila de platos. Solo podés sacar o agregar el plato que está arriba. Si querés acceder a uno del medio, primero tenés que quitar todos los que están encima.
Queue / Cola
Una Queue o Cola es una estructura de datos que sigue el principio FIFO (First In, First Out), es decir: el primer elemento en entrar es el primero en salir.
Podemos pensarla como una fila en el supermercado: la primera persona que llega es la primera que paga y se va.
- Agregar un elemento: Es O(1), porque se agrega directamente al final de la cola.
- Eliminar un elemento: También es O(1), ya que se remueve el primer elemento sin necesidad de reestructurar la cola.
- Acceder o buscar un elemento específico: Es O(n), porque no existe un índice y hay que recorrer los elementos desde el principio hasta encontrar el que buscamos.
Ejemplo → Como en la fila del súper, si querés atender al que está en el medio, primero tenés que atenedr a todos los que están adelante.
Para practicar un poco estas estructuras, creé un repositorio en GitHub
con distintos ejercicios → https://github.com/paula-m-alvarez/estructuras-de-datos-JAVA
Ahí van a encontrar los links a cada ejercicio junto con su solución.
Están pensados para resolverse en Java, pero pueden tomarlos como referencia y adaptarlos al lenguaje que más les guste :)
En la parte 2 vamos a continuar con mas estructuras de datos como Hashmap, Binary Search Tree, Heap or Priority Queue etc.
Top comments (0)