Estructuras de Datos
Prologo
Programa = Estructura de Datos + Algoritmo. Ya aprendimos como la CPU ejecuta instrucciones y como el sistema operativo gestiona recursos. Pero el objeto central que procesan los programas son los datos -- informacion de usuarios, listas de productos, relaciones sociales... Como se organizan estos datos en memoria determina directamente la velocidad del programa. La respuesta suele estar en la eleccion de la estructura de datos.
Que aprenderas en este articulo?
- Intuicion: ver un requerimiento y pensar automaticamente en que estructura de datos usar
- Perspectiva de rendimiento: diagnosticar si el cuello de botella es la estructura o el algoritmo
- Pensamiento de compromiso: entender "espacio por tiempo" y "tiempo por espacio"
- Lectura de codigo: HashMap, Stack, Queue ya no seran terminos extranos
| Capitulo | Contenido | Concepto clave |
|---|---|---|
| Capitulo 1 | Vision general | Cuatro categorias de estructuras de datos |
| Capitulo 2 | Estructuras lineales | Arrays, listas enlazadas, pilas, colas |
| Capitulo 3 | Tablas hash | Funcion hash, manejo de colisiones, busqueda O(1) |
| Capitulo 4 | Estructuras de arbol | Arboles binarios, sistema de archivos, DOM |
| Capitulo 5 | Estructuras de grafo | Grafos dirigidos, no dirigidos, algoritmos de recorrido |
| Capitulo 6 | Comparacion de rendimiento | Complejidad temporal y espacial |
| Capitulo 7 | Guia de seleccion | Analisis de escenarios, flujo de decision |
1. Vision general: Que son las estructuras de datos?
Imagina que quieres organizar un monton de libros:
- Amontonados en el suelo: buscar libro por libro -- almacenamiento primitivo
- Numerados en estanteria: ir directamente a la posicion -- array
- Clasificados en armarios: primero determinar el armario -- tabla hash
- Ordenados en estantes multinivel: eliminar la mitad cada vez -- arbol
Las estructuras de datos son la "forma de organizar" los datos -- determinan como se almacenan, buscan y modifican.
Data Structure OverviewChoose a data organization model for each scenario
Data structures are like ways to organize a room: clothes in a wardrobe, books on shelves, and small items in drawers.
Linear structures
Data arranged in order, like a row of books
ArrayLinked listStackQueue
Hash structures
Fast lookup through a key
Hash tableDictionarySet
Tree structures
Hierarchy, like a family tree
Binary treeB-treeHeap
Graph structures
Complex relationship networks
Directed graphUndirected graphNetwork graph
Linear structures
Features
One-to-one relationship between elements
A clear before-and-after order
Can use contiguous storage or linked storage
Use Cases
Arrays: list data
Store ordered data such as student scores or product prices
Stacks: undo operations
Text editor undo history, last in first out
Queues: task scheduling
Print queues and task queues, first in first out
Operation Complexity
OperationAverage time
Access elementO(1)
Insert/deleteO(n)
Everyday Analogy
Like train cars connected in order
To find car 5, count directly to it; to insert a new car, you need to break and reconnect links.
Todas las estructuras se clasifican en cuatro categorias:
| Tipo | Relacion | Representantes | Analogia |
|---|---|---|---|
| Lineal | Uno a uno | Array, lista, pila, cola | Vagones de tren |
| Hash | Clave→Valor | Tabla hash, diccionario | Fichas de biblioteca |
| Arbol | Uno a muchos | Arbol binario, B-tree | Arbol genealogico |
| Grafo | Muchos a muchos | Grafo dirigido, no dirigido | Mapa de metro |
2. Estructuras lineales: La organizacion mas basica
Four Forms of Linear StructuresHow arrays, linked lists, stacks, and queues differ
ArrayContiguous memory, indexed access
0
10
1
25
2
33
3
47
4
59
5
62
✓ Contiguous memory | ✓ Fast access (O(1)) | ✗ Slow insert/delete (O(n))
Operation Comparison
| Data structure | Access | Insert | Delete | Feature |
|---|---|---|---|---|
| 📊 Array | O(1) fast | O(n) slow | O(n) slow | Fixed size |
| 🔗 Linked list | O(n) slow | O(1) fast | O(1) fast | Variable size |
| 🥞 Stack | O(n) | O(1) fast | O(1) fast | One-end operations |
| 🚶 Queue | O(n) | O(1) fast | O(1) fast | Two-end operations |
Real-World Uses
List data
Student scores or product price lists
Image processing
Pixel matrix storage
Charts
Data ordered by time
2.1 Array vs Lista enlazada
| Dimension | Array | Lista enlazada |
|---|---|---|
| Memoria | Bloque continuo | Dispersa, unida por punteros |
| Acceder al n-esimo | Directo, O(1) | Desde el inicio, O(n) |
| Insertar en medio | Mover los de atras, O(n) | Cambiar punteros, O(1) |
| Tamano | Fijo al crear | Crece dinamicamente |
2.2 Pila y Cola
| Estructura | Regla | Analogia | Donde aparece? |
|---|---|---|---|
| Pila | LIFO (ultimo en entrar, primero en salir) | Pila de platos | Pila de llamadas, atras del navegador, Ctrl+Z |
| Cola | FIFO (primero en entrar, primero en salir) | Fila para comprar | Cola de tareas, cola de mensajes |
3. Tabla Hash: La busqueda mas rapida
Las busquedas lineales no son suficientemente rapidas. La tabla hash logra O(1) directamente.
Hash Tables: Super-Fast LookupFind data directly through a key
A hash table is like a library index card: instead of searching shelf by shelf, you use the index to find the book location directly.
Store data
Hashing process
Input key
apple
↓
Hash function
hash(key) % 10
↓
Array index
0
Hash table
0
apple: apple
1
Empty
2
Empty
3
Empty
4
Empty
5
Empty
6
orange: orange
7
Empty
8
Empty
9
banana: banana
Performance Comparison
Hash table lookup
O(1)
Found instantly
Array lookup
O(n)
Requires traversal
Binary search
O(log n)
Requires sorted data
Common Uses
User table (user ID → profile)
Shopping cart (product ID → quantity)
Cache system (URL → page content)
Dictionary (word → definition)
3.1 Principio
- Das una clave (ej: "apple")
- La funcion hash calcula un numero (ej:
hash("apple") = 3) - Vas directamente a la posicion 3 -- sin recorrer
3.2 Colisiones hash
Dos claves pueden producir el mismo indice -- esto es una colision hash.
| Solucion | Principio |
|---|---|
| Encadenamiento | Lista enlazada en la misma posicion |
| Direccion abierta | Buscar la siguiente posicion vacia |
4. Estructuras de Arbol: Expresar jerarquias
Tree Structures: Representing HierarchiesAn organization model like a family tree
Choose a tree type:
Tree Structure Features
Hierarchy
Nodes have one-to-many parent-child relationships
Single root node
Except for the root, each node has exactly one parent
Efficient lookup
Binary search tree lookup is O(log n)
Multiple traversals
Preorder, inorder, postorder, and level-order traversal
Use Cases
File systems
Hierarchical organization of folders and files
HTML DOM
Nested structure of web page elements
Organization charts
Company management hierarchy
Decision trees
Classification algorithms in machine learning
4.1 Arbol binario de busqueda
Regla simple: menores a la izquierda, mayores a la derecha. Busqueda O(log n).
4.2 Arboles balanceados
| Tipo | Estrategia | Aplicacion |
|---|---|---|
| AVL | Balance estricto | Busquedas frecuentes |
| Rojo-Negro | Balance aproximado | Java TreeMap, Linux kernel |
| B-tree | Multi-via balanceado | Indices de bases de datos |
5. Estructuras de Grafo: Redes de relaciones complejas
Graph Structures: Representing Complex RelationshipsA network of nodes and edges
Graph properties
Vertices (V)
5
Edges (E)
6
Degree
2.4
Use Cases
Map navigation (shortest path)
Social networks (friend relationships)
Web links (PageRank)
Dependencies (package management)
| Tipo | Caracteristica | Analogia |
|---|---|---|
| No dirigido | A→B igual que B→A | Amigos de WeChat |
| Dirigido | A→B no es B→A | Seguidores de Weibo |
| Ponderado | Las aristas tienen peso | Carreteras entre ciudades |
6. Comparacion de rendimiento
Data Structures: Containers for DataChoose different storage models for different scenarios
ArrayContiguous memory and fast indexed access
010
120
230
340
450
560
670
780
Access arr[2] = O(1), insert/delete = O(n)
Time Complexity Comparison
| Operation | Array | Linked list | Hash table | Tree |
|---|---|---|---|---|
| Access | O(1) | O(n) | O(1) | O(log n) |
| Search | O(n) | O(n) | O(1) | O(log n) |
| Insert | O(n) | O(1) | O(1) | O(log n) |
| Delete | O(n) | O(1) | O(1) | O(log n) |
Core idea:Data structures are containers for data. Different containers have different tradeoffs. Choosing the right data structure can improve program efficiency by orders of magnitude.
| Estructura | Acceso | Busqueda | Insercion | Eliminacion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Lista | O(n) | O(n) | O(1) | O(1) |
| Pila/Cola | O(n) | O(n) | O(1) | O(1) |
| Tabla Hash | -- | O(1) | O(1) | O(1) |
| Arbol BST | -- | O(log n) | O(log n) | O(log n) |
7. Guia de seleccion
| Necesidad | Estructura | Razon |
|---|---|---|
| Acceso por posicion | Array | O(1) acceso aleatorio |
| Insercion/eliminacion frecuente | Lista | O(1) sin mover elementos |
| LIFO (deshacer, recursion) | Pila | Semantica LIFO natural |
| FIFO (cola de tareas) | Cola | Semantica FIFO natural |
| Busqueda rapida por clave | Tabla hash | O(1) busqueda promedio |
| Datos ordenados + busqueda rapida | BST | O(log n) y ordenado |
| Relaciones muchos a muchos | Grafo | Expresa conexiones arbitrarias |
Regla practica
- 80% de los escenarios: arrays y tablas hash son suficientes
- Necesitas orden: considera arboles
- Relaciones complejas: considera grafos
- No estas seguro? Usa lo mas simple primero
Lectura adicional
| Tema | Recurso |
|---|---|
| Visualizacion | VisuAlgo |
| Libro introductorio | "Grokking Algorithms" - Aditya Bhargava |
| Profundizacion | "Data Structures and Algorithm Analysis" - Mark Allen Weiss |
| Practica | LeetCode |
Proximos pasos
- Pensamiento Algoritmico: Aprender a resolver problemas con algoritmos
- Lenguajes de Programacion: Como implementan estas estructuras