• Cimiento: tres zonas (estática, pila de llamadas, montón); el nodo = registro con información + punteros; nulo = ausencia de enlace (su desreferencia, el error clásico). Gestión: manual (fugas, punteros colgantes, doble liberación) vs recolector de basura (alcanzabilidad; el conteo de referencias falla con ciclos) vs comprobación en compilación (Rust).
• Insertar N tras A: (1) siguiente de N = siguiente de A; (2) siguiente de A = N. Invertir el orden pierde el resto de la lista. Borrar el siguiente de A: siguiente de A = siguiente del siguiente; liberar el puenteado.
• Costes: insertar/eliminar en punto conocido O(1); acceso k-ésimo y búsqueda O(n); sin búsqueda binaria (no se puede saltar al medio).
• Variantes: doble (bidireccional, borrado con solo el nodo), circular (secuencias cíclicas), centinela (elimina casos límite).
• Vs vector: asintóticamente gana en mantenimiento y pierde en acceso; físicamente pierde localidad (nodos dispersos → fallos de caché) y paga punteros y gestor. En la práctica el array redimensionable gana casi siempre; la lista, para empalmes/particiones e inserciones interiores frecuentes.

• Pila (LIFO): apilar/desapilar por la cima, O(1); sobre vector o lista (cabeza). Aplicaciones: pila de llamadas y recursión, postfija (3 4 + 5 × = 35), deshacer. Cola (FIFO): encolar final/desencolar frente O(1); vector circular con aritmética modular o lista con puntero al último. Variantes: deque y cola de prioridad (mejor con montículo: raíz O(1), insertar/extraer O(log n), representado en vector con hijos de i en 2i+1 y 2i+2).
• ABB de 50,30,70,20,40: raíz 50; 30 izq; 70 der; 20 y 40 hijos izq/der del 30 (altura 2).
• Recorridos: preorden 50-30-20-40-70; inorden 20-30-40-50-70 (¡ordenado!); postorden 20-40-30-70-50.
• Borrado con dos hijos: sustituir por el sucesor inorden (mínimo del subárbol derecho); hoja se corta, un hijo se puentea.
• Degeneración: claves ordenadas → lista inclinada O(n). Remedio: AVL (estricto) y rojinegro (laxo, el de los mapas ordenados) con rotaciones → O(log n) garantizado. En disco: B/B+ (nodos-página, índices de BD).

• Matriz de adyacencia: n×n; arista en O(1); memoria n² → grafos densos. Listas de adyacencia: memoria proporcional a vértices+aristas; vecinos en O(grado) → grafos dispersos (los reales). Recorridos: DFS con pila/recursión, BFS con cola.
• Hash: calcular en vez de comparar. División: 4520 mod 101 = 76 (tamaño primo reparte mejor); cadenas → combinación polinómica de códigos.
• Colisiones (inevitables, palomar): encadenamiento (lista por casilla) o direccionamiento abierto (sondeo hacia otra casilla libre).
• Factor de carga: moderado → O(1) medio; alto → redimensionar y redispersar todo (coste amortizado).
• Criterio: hash = más rápida de media, sin orden (diccionarios de Python, mapas de Java, objetos de JavaScript); árbol equilibrado = orden mantenido (rangos, recorridos ordenados) y peor caso O(log n) garantizado.

Primero siguiente de N = siguiente de A; después siguiente de A = N. Al revés se pierde el resto de la lista.

Fuga: bloque sin liberar al que ya nadie apunta. Colgante: puntero a un bloque ya liberado (uso = corrupción).

Los ciclos (nodos que se apuntan mutuamente) nunca bajan de una referencia y no se liberan; hay que rastrear alcanzabilidad.

Se apilan 3 y 4; el + desapila y apila 7; se apila 5; el × desapila y da 35.

El inorden (izquierdo, raíz, derecho).

En las posiciones 2i+1 y 2i+2 (árbol completo linealizado, sin punteros).

DFS: pila (o recursión). BFS: cola.

Tabla de dispersión el diccionario; árbol rojinegro el mapa ordenado.