Programación · conceptos · estructuras de datos

¿Qué es una lista enlazada?

Una lista enlazada (linked list) es una estructura de datos que almacena una secuencia de valores como una cadena de nodos. Cada nodo contiene dos cosas: un valor y un puntero (una referencia) al siguiente nodo de la cadena. Los nodos no están dispuestos uno junto a otro en un solo bloque de memoria como lo están los elementos de un array; en cambio, cada uno simplemente apunta a donde vive el siguiente. Sigue los punteros desde el primer nodo, la cabeza, y podrás recorrer toda la secuencia un eslabón a la vez.

Cómo se construye la cadena

Piénsalo como una búsqueda del tesoro donde cada pista te dice dónde encontrar la siguiente pista. La lista guarda una referencia al nodo cabeza. El puntero de ese nodo lleva al segundo nodo, cuyo puntero lleva al tercero, y así sucesivamente hasta que el puntero de un nodo esté vacío (a menudo llamado null o None), lo que marca el final de la lista.

[ valor | siguiente ] -> [ valor | siguiente ] -> [ valor | null ]

Como las conexiones son solo punteros, los nodos pueden estar en cualquier lugar de la memoria. Para hacer crecer la lista, reservas un nodo nuevo y ajustas un puntero hacia él; nada más tiene que moverse.

Simple vs doblemente enlazada

Hay dos formas comunes, y la diferencia está en cuántos punteros lleva cada nodo:

• Lista simplemente enlazada: cada nodo apunta solo al nodo siguiente. Puedes avanzar por la lista pero no retroceder, y solo pagas un puntero por nodo.
• Lista doblemente enlazada: cada nodo apunta tanto al nodo siguiente como al anterior. Eso te permite recorrerla en ambas direcciones y facilita algunas eliminaciones, a costa de un puntero adicional por nodo.

Lista enlazada vs array

La forma más clara de entender una lista enlazada es ponerla junto a un array, porque hacen compromisos opuestos. Un array almacena sus elementos en un bloque contiguo con un índice, así que puede saltar a cualquier posición al instante. Una lista enlazada renuncia a eso a cambio de cambios baratos en los extremos.

• Acceso aleatorio. Un array lee cualquier elemento por su índice en O(1). Una lista enlazada no tiene índice: para llegar al décimo nodo debes empezar en la cabeza y seguir nueve punteros, así que el acceso es O(n).
• Insertar y eliminar. Si ya tienes una referencia al nodo correcto, una lista enlazada puede insertar o eliminar ahí recableando un par de punteros, una operación O(1) - sin desplazar los demás elementos. En un array, insertar o eliminar en el medio implica desplazar los elementos siguientes, lo que es O(n).
• Memoria y caché. Un array empaqueta sus valores juntos, lo que es amigable con la caché de la CPU. Una lista enlazada dispersa sus nodos y almacena un puntero adicional por nodo, así que usa más memoria por elemento y suele tener peor localidad de caché.

Ninguna es "mejor"; sirven para trabajos distintos. Si necesitas búsquedas rápidas por posición, un array (o un array dinámico como una list o un vector) suele ganar. Si tus datos cambian mucho de tamaño y sobre todo añades o quitas en los extremos, una lista enlazada puede encajar bien. Para un repaso de cómo se describen estos costes, consulta nuestra guía sobre la notación Big O.

Las complejidades, con honestidad

Estos son los costes estándar de una lista enlazada, con la advertencia que siempre importa:

• Acceso y búsqueda: O(n). No hay índice, así que encontrar un valor significa recorrer la cadena desde la cabeza.
• Inserción y eliminación: O(1) cuando ya tienes una referencia al nodo (por ejemplo, justo en la cabeza). Si primero tienes que encontrar el sitio, esa búsqueda es O(n), y el total refleja ambas partes.

Esa condición de "cuando tienes el nodo" es la parte que la gente suele omitir. Insertar en la cabeza de una lista simplemente enlazada es realmente tiempo constante; insertar después de algún valor que aún tienes que localizar no lo es.

Dónde se usan las listas enlazadas

Las listas enlazadas son un bloque de construcción más que un contenedor de uso diario. Son una forma natural de implementar una pila (stack) o una cola (queue), ya que estas solo añaden y quitan en los extremos. Encajan en situaciones donde el tamaño de la colección cambia mucho y no necesitas acceso rápido por posición. Algunas estructuras usan nodos enlazados internamente; por ejemplo, una forma común de gestionar las colisiones en una tabla hash es encadenar las entradas en colisión en una pequeña lista enlazada por bucket.

Los compromisos

• Sin acceso aleatorio. Llegar a una posición arbitraria cuesta O(n) porque sigues los punteros desde la cabeza; no hay índice con el que saltar.
• Memoria adicional por elemento. Cada nodo almacena al menos un puntero (dos en una lista doblemente enlazada) además de su valor.
• Peor localidad de caché. Los nodos dispersos son menos amigables con la caché que un array contiguo, lo que puede hacer el recorrido más lento en la práctica aunque el Big O sea el mismo.
• Ediciones baratas en un nodo conocido. La ventaja: insertar o quitar en un nodo que ya tienes es O(1), sin desplazar el resto de los datos.

FAQ

¿Cuál es la diferencia entre una lista enlazada y un array? Un array almacena los elementos en un bloque contiguo con un índice, así que lee cualquier posición en O(1) pero desplazar elementos para insertar o eliminar en el medio cuesta O(n). Una lista enlazada almacena nodos separados unidos por punteros, así que no tiene acceso aleatorio (O(n) para llegar a una posición) pero puede insertar o eliminar en un nodo conocido en O(1).

¿Por qué acceder a un elemento es O(n)? Porque una lista enlazada no tiene índice. Para llegar al nodo n empiezas en la cabeza y sigues la cadena de punteros n veces, así que el coste crece con la posición que quieres.

¿Cuál es la diferencia entre simple y doblemente enlazada? En una lista simplemente enlazada cada nodo apunta solo al nodo siguiente, así que solo puedes avanzar hacia adelante. En una lista doblemente enlazada cada nodo también apunta al nodo anterior, así que puedes moverte en ambas direcciones, a costa de un puntero adicional por nodo.

¿Cuándo debería usar una lista enlazada? Cuando la colección cambia mucho de tamaño y sobre todo añades o quitas en los extremos, o como base de una pila o una cola. Si necesitas acceso rápido por posición, un array suele ser la mejor opción.

Guías relacionadas: tablas hash, notación Big O, recursividad.