Fundamentos de Estructuras de Datos y Algoritmia

En una célebre frase, el informático Niklaus Wirth tituló su libro más influyente:
$\mathbf{\text{Algoritmos}} + \mathbf{\text{Estructuras de Datos}} = \mathbf{\text{Programas}}$

Cualquier sistema de software, desde un sistema operativo hasta una red social o un motor de videojuegos, consiste fundamentalmente en organizar datos en la memoria del ordenador (Estructuras de Datos) y procesar esos datos siguiendo secuencias lógicas optimizadas (Algoritmos).

1. ¿Qué es un Algoritmo? #

Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas, finitas y no ambiguas que permiten solucionar un problema o llevar a cabo una tarea de cómputo.

Propiedades Esenciales de un Algoritmo: #

Entrada y Salida: Recibe cero o más datos de entrada y produce un resultado concreto.
Finitud: Debe terminar obligatoriamente tras un número finito de pasos (no puede entrar en bucles infinitos no deseados).
Determinismo / Precisión: Para los mismos datos de entrada, cada paso debe estar definido sin ambigüedad y producir siempre el mismo resultado.
Eficacia: Cada instrucción debe ser lo suficientemente básica para poder ser ejecutada por la máquina en un tiempo razonable.

2. Estructuras de Datos Lineales #

1ARRAY (Memoria Contigua):            LISTA ENLAZADA (Nodos con Punteros):
2┌────┬────┬────┬────┐                ┌─────┬───┐    ┌─────┬───┐    ┌─────┬────┐
3│ 10 │ 20 │ 30 │ 40 │                │ 10  │ ──┼───►│ 20  │ ──┼───►│ 30  │null│
4└────┴────┴────┴────┘                └─────┴───┘    └─────┴───┘    └─────┴────┘
5Índice: 0    1    2    3
6
7PILA / STACK (LIFO - Último en entrar, primero en salir):
8Push ──► ┌─────┐
9         │  C  │ ◄── Top
10         ├─────┤
11         │  B  │
12         ├─────┤
13         │  A  │
14         └─────┘ ──► Pop
15
16COLA / QUEUE (FIFO - Primero en entrar, primero en salir):
17Enqueue (Entrada) ──► [ Elemento C ] [ Elemento B ] [ Elemento A ] ──► Dequeue (Salida)

Estructura	Principio de Organización	Acceso a Elementos	Caso de Uso Típico
Array (Vector)	Memoria contigua indexada.	Instantáneo $O(1)$ por índice (`arr[3]`).	Almacenar colecciones de tamaño conocido con lecturas frecuentes.
Lista Enlazada	Nodos dispersos enlazados con punteros.	Secuencial recorriendo enlaces.	Inserciones y borrados rápidos en mitad de la lista.
*Pila (Stack)*	LIFO (Last In, First Out).	Solo se accede a la cima (Top).	Pila de llamadas de funciones (Call Stack), Deshacer/Rehacer (Ctrl+Z), análisis de paréntesis.
*Cola (Queue)*	FIFO (First In, First Out).	Por el frente; inserción por el final.	Colas de impresión, buffers de streaming de vídeo, tareas asíncronas encoladas.

Modifica los enlaces de una lista #

Selecciona un nodo y observa cómo cambian las referencias al insertar o eliminar elementos. Los nodos conservan su identidad aunque cambie su posición en el recorrido.

Laboratorio interactivo

Enlaces de una lista

Selecciona un nodo, inserta otro o elimina el seleccionado. Los identificadores N1, N2… representan referencias, no posiciones contiguas en memoria.

Valor del nodo

head → N1 · 3/8 nodos

null

head apunta a N1. Cada nodo guarda un valor y una referencia next.

Últimos cambios de referencias

head apunta a N1. Cada nodo guarda un valor y una referencia next.

Aquí seleccionas el nodo directamente. En una lista real, localizarlo por posición exige recorrer sus enlaces; modificar un enlace ya localizado es una operación constante.

Experimenta: Inserta un nodo entre 10 y 20. Observa qué dos referencias cambian. Después borra la cabeza y finalmente vacía la lista.

Experimenta con pilas y colas #

Añade y retira elementos para comprobar qué dato sale primero en cada estructura:

Simulador interactivo

Simulador de pila (LIFO)

main

validar

guardar

La parte superior es el último elemento: será el primero en salir.

Simulador interactivo

Simulador de cola (FIFO)

tarea A

tarea B

tarea C

El elemento resaltado está al frente: será el primero en salir.

3. Estructuras de Datos Asociativas y Jerárquicas #

Tablas Hash / Diccionarios / Mapas (Hash Tables) #

Organizan la información en parejas de Clave $\rightarrow$ Valor ("usuario_123" -> {nombre: "Ana", edad: 28}).
Utilizan una Función Hash matemática que transforma la clave alfanumérica en un índice numérico de memoria de forma instantánea.
Ventaja: Búsqueda, inserción y borrado de coste medio $O(1)$ con una función hash y una ocupación adecuadas. Muchas colisiones pueden llevar al peor caso $O(n)$ .

Provoca una colisión y compara dos formas de resolverla: guardar varias claves en el mismo cubo o buscar otro hueco.

Laboratorio interactivo

Colisiones en una tabla hash

Esta función didáctica suma los puntos de código de la clave y calcula el resto entre 5. Compara encadenamiento con sondeo lineal.

ClaveValor

A y F colisionan: ambas empiezan en el cubo 0.

Resolver colisionesInspeccionar inserción

h(F) = (70) mod 5 = 0

[0]A: AnaF: Félix

[1]Vacío

[2]Vacío

[3]Vacío

[4]Vacío

La tabla muestra el estado final. Avanza para reconstruir dónde se insertó la clave seleccionada.

VelocidadPaso 0 de 1

Esta función simple permite provocar colisiones fácilmente. O(1) es un coste medio bajo condiciones adecuadas; muchas colisiones pueden degradar las operaciones a O(n).

Experimenta: Inserta K: A, F y K tienen el mismo hash. Cambia de estrategia y observa dónde se guarda cada clave. Después actualiza A con otro valor.

Árboles Binarios de Búsqueda (BST) #

Estructura no lineal formada por nodos jerárquicos (raíz, ramas y hojas).
Propiedad de orden: Para cualquier nodo, todos los elementos de su subárbol izquierdo son menores que él, y todos los de su subárbol derecho son mayores.

Inserta valores y reproduce los tres recorridos. Prueba también una inserción ordenada para observar que un árbol binario de búsqueda no siempre está equilibrado.

Laboratorio interactivo

Construye y recorre un árbol binario

Inserta números y observa la ruta de comparación. Recorre el árbol en inorden, preorden o postorden.

Número a insertar (0–99)

Menores a la izquierda; mayores a la derecha. (7/10 nodos)

Recorrido

Salida: —. Avanza para visitar el primer nodo.

Naranja: actual. Azul: visitado. Gris: pendiente.

VelocidadPaso 0 de 7

Experimenta: Compara el árbol inicial con uno construido en orden ascendente. ¿Sigue teniendo forma equilibrada? El recorrido inorden siempre devuelve los valores ordenados.

Grafos: conexiones sin jerarquía única #

Un grafo representa elementos (nodos) conectados por aristas. A diferencia de un árbol, puede contener ciclos y varios caminos entre dos nodos.

BFS (anchura): utiliza una cola y visita por niveles de distancia desde el origen.
DFS (profundidad): utiliza una pila, explícita o de llamadas, y profundiza antes de explorar alternativas.
Ambos necesitan registrar los nodos visitados para evitar repetirlos en los ciclos. Si hay componentes desconectados, un recorrido desde un único origen no alcanza todos los nodos.

Laboratorio interactivo

Explora un grafo con BFS y DFS

Activa o desactiva conexiones de este grafo no dirigido. BFS usa una cola y DFS una pila. Los vecinos se exploran en orden alfabético.

4. Algoritmos Clásicos: Búsqueda Lineal vs Búsqueda Binaria #

Supongamos que queremos encontrar si un número existe dentro de una lista de $1.000.000$ de elementos:

1BÚSQUEDA LINEAL: Comprueba uno por uno desde el principio
2[ 1 ][ 2 ][ 3 ][ 4 ] ... [ 999.999 ][ 1.000.000 ]  ──► Peor caso: 1.000.000 comparaciones
3
4BÚSQUEDA BINARIA: Divide el array ordenado por la mitad en cada paso
5Paso 1: Mira el elemento 500.000 ──► ¿Es mayor? Descarta los 500.000 inferiores
6Paso 2: Mira el elemento 750.000 ──► ¿Es menor? Descarta los 250.000 superiores
7...
8Máximo de pasos necesarios: log₂(1.000.000) ≈ 20 comparaciones

Búsqueda Lineal: No requiere que la lista esté ordenada, pero su coste crece proporcionalmente al tamaño ( $O(n)$ ).
Búsqueda Binaria: Requiere que la lista esté previamente ordenada, pero reduce el problema a una complejidad logarítmica ( $O(\log n)$ ), encontrando cualquier elemento entre un millón en un máximo de 20 preguntas.

Compara primero ambas búsquedas sobre la misma lista ordenada. Cambia el objetivo, avanza y contrasta el número de comparaciones:

Laboratorio interactivo

Búsqueda lineal frente a binaria

Las dos búsquedas usan la misma lista ordenada. Avanza para comparar cuántos elementos necesitan examinar.

Número a buscarElementos

Lineal · examina uno a uno

0 comparaciones

[0]0Candidato

[1]3Candidato

[2]6Candidato

[3]9Candidato

[4]12Candidato

[5]15Candidato

[6]18Candidato

[7]21Candidato

[8]24Candidato

[9]27Candidato

[10]30Candidato

[11]33Candidato

Listo para buscar.

Binaria · divide el intervalo

0 comparaciones

[0]0Candidato

[1]3Candidato

[2]6Candidato

[3]9Candidato

[4]12Candidato

[5]15Candidato

[6]18Candidato

[7]21Candidato

[8]24Candidato

[9]27Candidato

[10]30Candidato

[11]33Candidato

Listo para buscar.

La búsqueda binaria requiere datos ordenados. Cada paso realiza como máximo una comparación por método; el método que termina conserva su resultado.

VelocidadPaso 0 de 10

Experimenta: Busca el último número de la lista y después un número ausente. ¿La búsqueda binaria necesita revisar todos los elementos?

Observa una ordenación paso a paso #

Elige burbuja, inserción o selección y compara cómo cambia la lista en cada paso:

Simulador interactivo

Comparador de algoritmos de ordenación

Algoritmo

Estado inicial

Resumen del tema

Conceptos clave #

Algoritmo: secuencia finita, precisa y determinista de instrucciones computacionales.
Pilas (LIFO) y Colas (FIFO): las pilas apilan hacia arriba (Call Stack); las colas atienden en orden de llegada (buffers).
Arrays vs Listas Enlazadas: los arrays ofrecen acceso directo ultrarrápido por índice en memoria contigua; las listas enlazadas facilitan el crecimiento dinámico sin memoria contigua.
Tablas Hash: asocian claves a valores mediante funciones hash con búsquedas inmediatas en $O(1)$ .
Poder de la Búsqueda Binaria: descartar la mitad de los elementos en cada iteración permite localizar datos en colecciones gigantescas en una fracción de milisegundo.

Qué debes recordar #

La elección de la estructura de datos adecuada determina la velocidad, el consumo de memoria y la elegancia del algoritmo que la procesa.

Fundamentos de Estructuras de Datos y Algoritmia

En una célebre frase, el informático Niklaus Wirth tituló su libro más influyente:
$\mathbf{\text{Algoritmos}} + \mathbf{\text{Estructuras de Datos}} = \mathbf{\text{Programas}}$

1. ¿Qué es un Algoritmo? #

Un algoritmo es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas, finitas y no ambiguas que permiten solucionar un problema o llevar a cabo una tarea de cómputo.

Propiedades Esenciales de un Algoritmo: #

Entrada y Salida: Recibe cero o más datos de entrada y produce un resultado concreto.
Finitud: Debe terminar obligatoriamente tras un número finito de pasos (no puede entrar en bucles infinitos no deseados).
Determinismo / Precisión: Para los mismos datos de entrada, cada paso debe estar definido sin ambigüedad y producir siempre el mismo resultado.
Eficacia: Cada instrucción debe ser lo suficientemente básica para poder ser ejecutada por la máquina en un tiempo razonable.

2. Estructuras de Datos Lineales #

1ARRAY (Memoria Contigua):            LISTA ENLAZADA (Nodos con Punteros):
2┌────┬────┬────┬────┐                ┌─────┬───┐    ┌─────┬───┐    ┌─────┬────┐
3│ 10 │ 20 │ 30 │ 40 │                │ 10  │ ──┼───►│ 20  │ ──┼───►│ 30  │null│
4└────┴────┴────┴────┘                └─────┴───┘    └─────┴───┘    └─────┴────┘
5Índice: 0    1    2    3
6
7PILA / STACK (LIFO - Último en entrar, primero en salir):
8Push ──► ┌─────┐
9         │  C  │ ◄── Top
10         ├─────┤
11         │  B  │
12         ├─────┤
13         │  A  │
14         └─────┘ ──► Pop
15
16COLA / QUEUE (FIFO - Primero en entrar, primero en salir):
17Enqueue (Entrada) ──► [ Elemento C ] [ Elemento B ] [ Elemento A ] ──► Dequeue (Salida)

Estructura	Principio de Organización	Acceso a Elementos	Caso de Uso Típico
Array (Vector)	Memoria contigua indexada.	Instantáneo $O(1)$ por índice (`arr[3]`).	Almacenar colecciones de tamaño conocido con lecturas frecuentes.
Lista Enlazada	Nodos dispersos enlazados con punteros.	Secuencial recorriendo enlaces.	Inserciones y borrados rápidos en mitad de la lista.
*Pila (Stack)*	LIFO (Last In, First Out).	Solo se accede a la cima (Top).	Pila de llamadas de funciones (Call Stack), Deshacer/Rehacer (Ctrl+Z), análisis de paréntesis.
*Cola (Queue)*	FIFO (First In, First Out).	Por el frente; inserción por el final.	Colas de impresión, buffers de streaming de vídeo, tareas asíncronas encoladas.

Modifica los enlaces de una lista #

Selecciona un nodo y observa cómo cambian las referencias al insertar o eliminar elementos. Los nodos conservan su identidad aunque cambie su posición en el recorrido.

Laboratorio interactivo

Enlaces de una lista

Selecciona un nodo, inserta otro o elimina el seleccionado. Los identificadores N1, N2… representan referencias, no posiciones contiguas en memoria.

Valor del nodo

head → N1 · 3/8 nodos

null

head apunta a N1. Cada nodo guarda un valor y una referencia next.

Últimos cambios de referencias

head apunta a N1. Cada nodo guarda un valor y una referencia next.

Aquí seleccionas el nodo directamente. En una lista real, localizarlo por posición exige recorrer sus enlaces; modificar un enlace ya localizado es una operación constante.

Experimenta: Inserta un nodo entre 10 y 20. Observa qué dos referencias cambian. Después borra la cabeza y finalmente vacía la lista.

Experimenta con pilas y colas #

Añade y retira elementos para comprobar qué dato sale primero en cada estructura:

Simulador interactivo

Simulador de pila (LIFO)

main

validar

guardar

La parte superior es el último elemento: será el primero en salir.

Simulador interactivo

Simulador de cola (FIFO)

tarea A

tarea B

tarea C

El elemento resaltado está al frente: será el primero en salir.

3. Estructuras de Datos Asociativas y Jerárquicas #

Tablas Hash / Diccionarios / Mapas (Hash Tables) #

Organizan la información en parejas de Clave $\rightarrow$ Valor ("usuario_123" -> {nombre: "Ana", edad: 28}).
Utilizan una Función Hash matemática que transforma la clave alfanumérica en un índice numérico de memoria de forma instantánea.
Ventaja: Búsqueda, inserción y borrado de coste medio $O(1)$ con una función hash y una ocupación adecuadas. Muchas colisiones pueden llevar al peor caso $O(n)$ .

Provoca una colisión y compara dos formas de resolverla: guardar varias claves en el mismo cubo o buscar otro hueco.

Laboratorio interactivo

Colisiones en una tabla hash

Esta función didáctica suma los puntos de código de la clave y calcula el resto entre 5. Compara encadenamiento con sondeo lineal.

ClaveValor

A y F colisionan: ambas empiezan en el cubo 0.

Resolver colisionesInspeccionar inserción

h(F) = (70) mod 5 = 0

[0]A: AnaF: Félix

[1]Vacío

[2]Vacío

[3]Vacío

[4]Vacío

La tabla muestra el estado final. Avanza para reconstruir dónde se insertó la clave seleccionada.

VelocidadPaso 0 de 1

Esta función simple permite provocar colisiones fácilmente. O(1) es un coste medio bajo condiciones adecuadas; muchas colisiones pueden degradar las operaciones a O(n).

Experimenta: Inserta K: A, F y K tienen el mismo hash. Cambia de estrategia y observa dónde se guarda cada clave. Después actualiza A con otro valor.

Árboles Binarios de Búsqueda (BST) #

Estructura no lineal formada por nodos jerárquicos (raíz, ramas y hojas).
Propiedad de orden: Para cualquier nodo, todos los elementos de su subárbol izquierdo son menores que él, y todos los de su subárbol derecho son mayores.

Inserta valores y reproduce los tres recorridos. Prueba también una inserción ordenada para observar que un árbol binario de búsqueda no siempre está equilibrado.

Laboratorio interactivo

Construye y recorre un árbol binario

Inserta números y observa la ruta de comparación. Recorre el árbol en inorden, preorden o postorden.

Número a insertar (0–99)

Menores a la izquierda; mayores a la derecha. (7/10 nodos)

Recorrido

Salida: —. Avanza para visitar el primer nodo.

Naranja: actual. Azul: visitado. Gris: pendiente.

VelocidadPaso 0 de 7

Experimenta: Compara el árbol inicial con uno construido en orden ascendente. ¿Sigue teniendo forma equilibrada? El recorrido inorden siempre devuelve los valores ordenados.

Grafos: conexiones sin jerarquía única #

Un grafo representa elementos (nodos) conectados por aristas. A diferencia de un árbol, puede contener ciclos y varios caminos entre dos nodos.

BFS (anchura): utiliza una cola y visita por niveles de distancia desde el origen.
DFS (profundidad): utiliza una pila, explícita o de llamadas, y profundiza antes de explorar alternativas.
Ambos necesitan registrar los nodos visitados para evitar repetirlos en los ciclos. Si hay componentes desconectados, un recorrido desde un único origen no alcanza todos los nodos.

Laboratorio interactivo

Explora un grafo con BFS y DFS

Activa o desactiva conexiones de este grafo no dirigido. BFS usa una cola y DFS una pila. Los vecinos se exploran en orden alfabético.

4. Algoritmos Clásicos: Búsqueda Lineal vs Búsqueda Binaria #

Supongamos que queremos encontrar si un número existe dentro de una lista de $1.000.000$ de elementos:

1BÚSQUEDA LINEAL: Comprueba uno por uno desde el principio
2[ 1 ][ 2 ][ 3 ][ 4 ] ... [ 999.999 ][ 1.000.000 ]  ──► Peor caso: 1.000.000 comparaciones
3
4BÚSQUEDA BINARIA: Divide el array ordenado por la mitad en cada paso
5Paso 1: Mira el elemento 500.000 ──► ¿Es mayor? Descarta los 500.000 inferiores
6Paso 2: Mira el elemento 750.000 ──► ¿Es menor? Descarta los 250.000 superiores
7...
8Máximo de pasos necesarios: log₂(1.000.000) ≈ 20 comparaciones

Búsqueda Lineal: No requiere que la lista esté ordenada, pero su coste crece proporcionalmente al tamaño ( $O(n)$ ).
Búsqueda Binaria: Requiere que la lista esté previamente ordenada, pero reduce el problema a una complejidad logarítmica ( $O(\log n)$ ), encontrando cualquier elemento entre un millón en un máximo de 20 preguntas.

Compara primero ambas búsquedas sobre la misma lista ordenada. Cambia el objetivo, avanza y contrasta el número de comparaciones:

Laboratorio interactivo

Búsqueda lineal frente a binaria

Las dos búsquedas usan la misma lista ordenada. Avanza para comparar cuántos elementos necesitan examinar.

Número a buscarElementos

Lineal · examina uno a uno

0 comparaciones

[0]0Candidato

[1]3Candidato

[2]6Candidato

[3]9Candidato

[4]12Candidato

[5]15Candidato

[6]18Candidato

[7]21Candidato

[8]24Candidato

[9]27Candidato

[10]30Candidato

[11]33Candidato

Listo para buscar.

Binaria · divide el intervalo

0 comparaciones

[0]0Candidato

[1]3Candidato

[2]6Candidato

[3]9Candidato

[4]12Candidato

[5]15Candidato

[6]18Candidato

[7]21Candidato

[8]24Candidato

[9]27Candidato

[10]30Candidato

[11]33Candidato

Listo para buscar.

La búsqueda binaria requiere datos ordenados. Cada paso realiza como máximo una comparación por método; el método que termina conserva su resultado.

VelocidadPaso 0 de 10

Experimenta: Busca el último número de la lista y después un número ausente. ¿La búsqueda binaria necesita revisar todos los elementos?

Observa una ordenación paso a paso #

Elige burbuja, inserción o selección y compara cómo cambia la lista en cada paso:

Simulador interactivo

Comparador de algoritmos de ordenación

Algoritmo

Estado inicial

Resumen del tema

Conceptos clave #

Algoritmo: secuencia finita, precisa y determinista de instrucciones computacionales.
Pilas (LIFO) y Colas (FIFO): las pilas apilan hacia arriba (Call Stack); las colas atienden en orden de llegada (buffers).
Arrays vs Listas Enlazadas: los arrays ofrecen acceso directo ultrarrápido por índice en memoria contigua; las listas enlazadas facilitan el crecimiento dinámico sin memoria contigua.
Tablas Hash: asocian claves a valores mediante funciones hash con búsquedas inmediatas en $O(1)$ .
Poder de la Búsqueda Binaria: descartar la mitad de los elementos en cada iteración permite localizar datos en colecciones gigantescas en una fracción de milisegundo.

Qué debes recordar #

La elección de la estructura de datos adecuada determina la velocidad, el consumo de memoria y la elegancia del algoritmo que la procesa.