La lista enlazada

La lista enlazada (en inglés, linked list) guarda una serie de datos en celdas que pueden estar en cualquier sitio de la memoria, porque cada celda lleva, junto al dato, la dirección de la siguiente. Esa dirección es un puntero (pointer), y la lista entera no es más que la dirección de la primera celda, la cabeza. Para leer la lista se empieza por ella y se va saltando de puntero en puntero hasta la última, que apunta a nada. Es lo contrario del vector (array), que pone todos los datos seguidos en memoria y encuentra el elemento k multiplicando: la dirección del primero más k veces el tamaño de cada uno.

La figura de esta página pone las dos estructuras una encima de otra, con los mismos números, y permite hacerles las dos cosas que las separan. Insertar un dato en la posición k obliga al vector a desplazar una celda a la derecha todos los elementos que vienen después, y a la lista solo a recorrer k celdas y recolocar dos punteros. Leer el elemento de la posición k le cuesta al vector un paso, y a la lista, k. La figura cuenta las operaciones de cada uno en cada jugada.

Lo que la figura resume es un intercambio sin trampa. Lo que a uno le cuesta un paso, al otro le cuesta tantos como elementos haya, y al revés. Por eso la elección depende de qué se va a hacer más: un programa que lee posiciones al azar quiere un vector, y uno que inserta y quita constantemente por el medio, mientras recorre, quiere una lista. Hay variantes para afinar: la lista doblemente enlazada (doubly linked list), en la que cada celda apunta también a la anterior y se puede recorrer en los dos sentidos, y la lista circular, en la que la última vuelve a la primera. En todas ellas, borrar una celda que ya se tiene a mano cuesta un paso, porque basta con que la anterior apunte a la siguiente, y en el vector cuesta desplazar el resto.

La idea nació con la inteligencia artificial. Allen Newell, Cliff Shaw y Herbert Simon la inventaron en 1956 para el Logic Theorist, el programa que demostraba teoremas de lógica, y la hicieron el centro de su lenguaje IPL: necesitaban guardar fórmulas cuya longitud no se sabía de antemano y que crecían y se partían mientras el programa razonaba, algo que un vector de tamaño fijo hace muy mal. John McCarthy la tomó para Lisp, el lenguaje que presentó en 1960 y cuyo nombre viene de list processing. En Lisp todo es una lista de celdas de dos punteros, llamados car y cdr por los nombres de dos partes de la palabra de memoria del IBM 704 en el que se escribió, y hasta el propio programa es una lista, que es lo que hacen visible sus paréntesis. Como las celdas se creaban y abandonaban sin parar, McCarthy tuvo que inventar también quién las recogiera, y así nació el recolector de basura.

Hoy la lista enlazada está debajo de cosas que no la nombran. La pila y la cola se construyen sobre ella con naturalidad. Cada casilla de una tabla hash suele ser una lista corta con las claves que han caído en ella. El historial de deshacer de un editor, la lista de ventanas abiertas de un sistema operativo, los bloques libres de un disco o los procesos que esperan turno son listas enlazadas, y el núcleo de Linux lleva una pequeña cabeza de lista, con los punteros al anterior y al siguiente, dentro de casi todas sus estructuras. El motivo es siempre el mismo: no saber cuántos elementos habrá, ni en qué orden entrarán y saldrán.

El inconveniente moderno no se ve en la figura, porque la figura cuenta pasos y no tiempo. En un ordenador actual leer un dato que está en la memoria caché del procesador cuesta alrededor de un nanosegundo, y uno que hay que ir a buscar a la memoria principal, cerca de cien, como enseñan las latencias de un ordenador. Las celdas de un vector están juntas, así que cuando el procesador trae una trae también las vecinas; las de una lista están repartidas por donde cayeron al crearse, y cada salto de puntero puede ser un viaje a la memoria principal. Ulrich Drepper lo documentó en 2007 en un informe que se convirtió en lectura obligada. Bjarne Stroustrup, el autor de C++, llevaba a sus charlas una medición que incomoda a los manuales: para insertar números en orden en una secuencia de unos pocos miles de elementos, el vector gana a la lista aunque tenga que desplazar celdas, porque el tiempo se va en recorrer hasta el sitio y el vector recorre mucho más deprisa. La lista sigue ganando cuando los elementos son grandes, cuando ya se tiene la celda a mano o cuando nada puede moverse de sitio, pero ya no es la elección por defecto que fue durante cuarenta años.

Lo que queda de ella es la idea, que es más importante que la estructura: un dato puede guardar dónde está otro. Esa indirección es el átomo de todas las estructuras que vinieron después. Un árbol binario es una lista en la que cada celda apunta a dos, y un grafo, una en la que apunta a cuantas haga falta. Entender la lista enlazada es entender que la memoria no tiene por qué parecerse al orden de las cosas que guarda.

La pila y la cola – La tabla hash – El árbol binario de búsqueda – Las latencias de un ordenador – El recolector de basura