Caso real

Las listas del kernel de Linux

El kernel de Linux usa listas enlazadas en muchos sitios, por ejemplo para los procesos que esperan un recurso. Cada estructura lleva dentro sus propios enlaces («listas intrusivas»): un proceso puede salir de una lista y entrar en otra cambiando unos pocos enlaces, sin reservar memoria y sin recorrer nada, porque el kernel ya tiene el proceso.

Aplica la misma condición a un caso parecido: una operación que parte de un nodo que ya tienes.

Un planificador mantiene procesos en una lista doble. Un temporizador vence y tiene que pasar al proceso P de la lista «esperando» a la lista «listos»; el temporizador guarda una referencia al nodo de P. ¿Cuánto cuesta y de qué depende?O(n): hay que buscar a P en la lista de espera antes de poder quitarlo, y la lista puede ser largaO(1): cambia unos pocos enlaces porque ya tiene el nodo de P, sin importar cuántos esperanO(1) siempre, tenga el nodo de P o solo su número de proceso, porque quitar es cambiar enlacesO(log n): la lista de espera está ordenada y se busca a P con búsqueda binaria sobre los nodos