Al terminar esta nota
- Entender referencias
- Insertar sin desplazar elementos
- Comparar con arrays
El nodo mínimo
La lista conoce su cabeza. Desde allí, cada referencia conduce al siguiente nodo hasta llegar a null.
ts
type Node<T> = { value: T; next: Node<T> | null };
const head: Node<number> = {
value: 10,
next: { value: 20, next: null }
};Insertar al frente es constante
Crear un nodo que apunte a la cabeza actual y reemplazar la cabeza cuesta O(1). Buscar la posición veinte sigue costando O(n).
js
function prepend(list, value) {
return { value, next: list };
}Cuándo usarla
Es útil cuando insertás o eliminás con frecuencia y ya tenés la referencia correcta. Para acceso aleatorio, un array es generalmente mejor y más amigable con la caché.
Constructor de listas enlazadas● interactivo
clientepedidopagoNULL
Invertí una lista
Recorré una lista y cambiá cada referencia para invertir el orden sin crear otro array.
Mostrar una pista
Necesitás conservar previous, current y next.