Estructuras de datos a mano
Listas enlazadas, pilas y colas, tablas hash, árboles, BST, heaps, grafos y tries, construidos nodo por nodo y dibujados en vivo.
14 aulas · 13 horas de práctica · en el navegador, sin instalar nada
Temario
- La lista enlazada — Un tren de carga: cada vagón sabe solamente cuál viene detrás. Con un struct y un puntero armás la estructura de datos más vieja de todas, y la recorrés de la locomotora a la cola.
- Insertar y borrar nodos — Meter un vagón en el medio es cambiar dos flechas, en el orden justo. Sacar uno es hacer que el de adelante lo saltee... y devolverlo con delete, o queda perdido en el heap.
- La lista doble — Con una flecha más por vagón, el tren se camina para los dos lados y la cola se alcanza en un paso. A cambio, cada enganche se hace dos veces, y olvidarse de una se ve en cuanto volvés.
- Pila y cola sobre una lista — La cola del restaurante y el pinche de comandas, hechos con nodos: una cola es una lista que entra por el fondo y sale por el frente; una pila, una que entra y sale por arriba. Así son por dentro queue y stack.
- Tabla hash a mano — El guardarropa del boliche: cada nombre se convierte en un número de perchero, y buscar una campera es ir derecho a ese perchero. Cuando dos nombres caen en el mismo, se cuelgan en cadena. Así es un unordered_map por dentro.
- Árbol binario — Un nodo con dos punteros en vez de uno, y la lista se abre en ramas. Raíz, hijos, hojas y altura, y la herramienta que hace fácil todo lo de árboles: la recursión, porque cada hijo es otro árbol.
- BST: insertar y buscar — Una regla y el árbol se vuelve un buscador: los menores a la izquierda, los mayores a la derecha. Para encontrar algo bajás eligiendo un lado por nodo, como en la búsqueda binaria. Y el orden en que llegan los datos decide si el árbol queda frondoso o es una lista disfrazada.
- Recorridos in-, pre- y post-orden — Tres líneas, en tres órdenes distintos, y el mismo árbol se recorre de tres maneras: in-orden lo lee ordenado, pre-orden lo copia y post-orden lo libera. Y una cuarta, por niveles, con una cola.
- Borrar en un BST — Sacar un nodo sin romper la regla del árbol. Una hoja se va sola; un nodo con un hijo deja que el hijo ocupe su lugar; uno con dos hijos le pide prestado el valor a su sucesor. Tres casos, una función recursiva.
- Heap binario — El restaurante se prende fuego y hay que rescatar primero lo que más se quema. Un heap es un árbol guardado en un vector, sin un solo puntero: el padre de i está en (i-1)/2. Subir al meter, bajar al sacar, y así es por dentro priority_queue.
- Grafos con listas de adyacencia — Ciudades y rutas: un grafo es eso, y se guarda con un vector de vecinos por ciudad. Con él se recorre en profundidad (DFS) o por niveles (BFS), se respetan las calles de una mano y se arma el camino con menos rutas.
- Trie: autocompletar — El teclado del celular que adivina la palabra: un árbol donde cada nodo es una letra y las palabras que empiezan igual comparten el camino. Insertar, buscar, preguntar por un prefijo y autocompletar, para salir de la sala de escape.
- Taller: El tren de carga — Una lista doble completa, como clase: agregar por las dos puntas, meter un vagón en cualquier posición, sacar uno de donde esté, dar vuelta el tren entero y que el destructor no deje nada tirado. Es std::list hecha a mano.
- Taller: Diccionario con un BST — Un diccionario de lunfardo guardado en un árbol de búsqueda: agregar y corregir palabras, buscar bajando, listar en orden alfabético, pedir las de un rango sin mirar todo y borrar. Es un std::map<string, string> hecho a mano.