GUÍA DE ESTUDIO · UNOS 12 MIN DE LECTURA

Estructuras de datos

Cómo guardas los datos decide qué es rápido y qué es lento. Elige una tarea cotidiana para ver qué estructura usaría un programador.

PilaCada edición se apila encima; Deshacer quita primero la más reciente. Último en entrar, primero en salir.

Qué es una estructura de datos, en resumen

Una estructura de datos es una forma de organizar los datos en memoria para que ciertas operaciones, como buscar algo, añadirlo o eliminarlo, sean eficientes. Elegir una es un compromiso: una estructura que hace las búsquedas instantáneas puede hacer lentas las inserciones, o usar más memoria.

Niklaus Wirth resumió su importancia en el título de su libro de 1976: Algoritmos + Estructuras de datos = Programas.

LinealesElementos en secuencia: arrays, listas enlazadas, pilas, colas.
JerárquicasPadres e hijos: árboles y montículos.
En redCualquier cosa puede enlazar con cualquier otra: grafos.
Por claveBuscar por nombre, no por posición: tablas hash y mapas.
ESTRUCTURAS LINEALES

Entran los mismos elementos, sale uno distinto

Añade elementos a las dos y luego quita uno. Una pila devuelve el más reciente (último en entrar, primero en salir); una cola devuelve el más antiguo (primero en entrar, primero en salir).

PILA · LIFOpush / pop
ABCCIMA · sale después
El historial de deshacer, el botón Atrás del navegador y la pila de llamadas que registra qué función llamó a cuál.
COLA · FIFOenqueue / dequeue
SALE ←
Asale despuésBC
← ENTRA
QUITADOS HASTA AHORA
Pila:-Cola:-
Trabajos de impresión, mensajes esperando a un servidor y la búsqueda en anchura en un grafo.
TABLAS HASH

Ir directo al cajón correcto

Una función hash convierte una clave en un número de cubeta, así que puedes encontrarla sin buscar. La nuestra suma los códigos de las letras y se queda con el resto de dividir entre 8. Añade nombres y fíjate en las colisiones.

N(78) + o(111) + a(97) = 286 → 286 mod 8 = cubeta 6
cubeta 0
Ana
cubeta 1
cubeta 2
cubeta 3
cubeta 4
cubeta 5
Ben
cubeta 6
Noa
cubeta 7
Aún no hay colisiones. Sigue añadiendo nombres: con solo 8 cubetas, dos pronto compartirán una.
ÁRBOLES

A la izquierda, menor; a la derecha, mayor

En un árbol binario de búsqueda, la rama izquierda de cada nodo contiene valores menores y la derecha, mayores. Cada comparación descarta la mitad de lo que queda. Elige un valor para buscarlo.

503070204060801025354555657590
RECORRIDO DE BÚSQUEDA
1. 45 < 50 → ir a la izquierda2. 45 > 30 → ir a la derecha3. 45 > 40 → ir a la derecha4. 45 = 45 ✓ encontrado
4pasos en el árbol
7pasos en la lista (en orden)
COMPROMISOS

La chuleta

rápidoaceptablelento
ESTRUCTURAACCESO POR POSICIÓNBÚSQUEDAINSERCIÓNBORRADO
Array
O(1)O(n)O(n)O(n)
Lista enlazada
O(n)O(n)O(1)O(1)
Pila
n/aO(n)O(1) solo la cimaO(1) solo la cima
Cola
n/aO(n)O(1) solo la cimaO(1) solo la cima
Tabla hash
n/aO(1)O(1)O(1)
ABB equilibrado
O(log n)O(log n)O(log n)O(log n)
Montículo
n/aO(n)O(log n)O(log n)
Casos típicos o medios. Las tablas hash pueden degradarse a O(n) con muchas colisiones; la fila del árbol supone que se mantiene equilibrado. «Inserción» en un array significa en el medio; añadir al final suele ser O(1).

Hitos

1945Programas almacenados.El diseño de Von Neumann puso datos e instrucciones en la misma memoria, lo que hizo posibles las estructuras.
1953Hashing.Hans Peter Luhn, en IBM, describió el hashing para búsquedas rápidas.
1955Listas enlazadas.Newell, Shaw y Simon las usaron en el Logic Theorist, uno de los primeros programas de IA.
1962Árboles equilibrados.Adelson-Velsky y Landis inventaron el árbol AVL, que se reequilibra solo para seguir siendo rápido.
1964El montículo.J. W. J. Williams presentó el montículo binario, junto con el heapsort.

Sigue adelante

Algoritmos + Estructuras de datos = ProgramasNiklaus Wirth · 1976
Introduction to AlgorithmsCormen, Leiserson, Rivest y Stein · 1990
Grokking AlgorithmsAditya Bhargava · 2016

Datos ordenados, mente ordenada. Pon a prueba tu razonamiento.

Nuestro test de CI completo abarca el razonamiento lógico, numérico, verbal y espacial: 60 preguntas, unos 30 minutos.

Hacer el test de CI completo