Lic. Carlos Enrique Loria Beeche.
Segundo artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”
Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que iremos recorriendo paso a paso.
En la entrega anterior estudiamos el array, el estacionamiento numerado de la memoria. Allí vimos una idea muy poderosa: cuando los datos están en posiciones consecutivas y conocemos el índice, podemos llegar directamente al elemento que queremos.
Ahora vamos a estudiar una estructura diferente: la linked list, o lista enlazada. Si el array se parece a un estacionamiento numerado, la lista enlazada se parece más a una búsqueda del tesoro: cada pista nos lleva a la siguiente.
Una lista enlazada nos enseña que no toda información necesita estar en una fila compacta; a veces basta con saber cuál es el siguiente paso.
¿Qué es una linked list?
Una linked list, o lista enlazada, es una estructura de datos formada por una secuencia de elementos llamados nodos.
Cada nodo guarda, al menos, dos cosas:
- El dato que queremos almacenar.
- Una referencia o enlace al siguiente nodo.
En lugar de depender de posiciones consecutivas de memoria, como ocurre en un array clásico, la lista enlazada depende de referencias. Un nodo apunta al siguiente, ese siguiente apunta al próximo, y así sucesivamente hasta llegar al final.
Por eso la analogía de la búsqueda del tesoro resulta tan útil. No tenemos un mapa completo con todas las posiciones numeradas. Tenemos una pista inicial, luego otra, luego otra, y cada una nos conduce al siguiente punto del recorrido.
El nodo: la pieza fundamental
El corazón de una lista enlazada es el nodo.
Un nodo puede imaginarse así:
+---------+-----------+
| DATO | SIGUIENTE |
+---------+-----------+
El campo DATO guarda el valor que nos interesa. El campo SIGUIENTE guarda la referencia al próximo nodo de la lista.
Una lista sencilla podría verse así:
INICIO
|
v
+---+------+ +---+------+ +---+------+
| A | *---+---> | B | *---+---> | C | NULL |
+---+------+ +---+------+ +---+------+
El primer nodo contiene A y apunta al nodo que contiene B. El nodo B apunta al nodo C. El nodo C no apunta a ningún otro nodo, por eso termina en NULL.
En una lista enlazada, cada nodo conoce el siguiente paso, pero no necesariamente conoce toda la ruta.
Diferencia principal con un array
La diferencia más importante entre un array y una lista enlazada está en la forma de llegar a los datos.
En un array, si conocemos el índice, podemos ir directamente al elemento:
array[4]Eso significa: vaya directamente a la posición 4.
En una lista enlazada, normalmente no podemos saltar directamente al nodo número 4. Debemos empezar en el primer nodo y avanzar paso a paso:
inicio -> nodo 1 -> nodo 2 -> nodo 3 -> nodo 4Esto significa que el acceso es secuencial. Para llegar a un nodo lejano, hay que recorrer los anteriores.
En cambio, insertar o eliminar elementos puede ser más flexible, porque muchas veces no es necesario mover todos los datos. Basta con cambiar referencias.
Ventaja principal: flexibilidad para insertar y eliminar
La gran ventaja de una lista enlazada es que puede insertar o eliminar nodos ajustando enlaces.
Supongamos esta lista:
A -> B -> C -> DSi queremos insertar una X entre B y C, no necesariamente tenemos que mover todos los elementos como podría ocurrir en un array. Basta con hacer que B apunte a X, y que X apunte a C:
A -> B -> X -> C -> DDe forma similar, si queremos eliminar C, podemos hacer que B apunte directamente a D:
A -> B -> DEl nodo C queda fuera de la cadena.
La lista enlazada no necesita mover toda la fila; muchas veces basta con cambiar el enlace correcto.
Limitación: no hay acceso directo por índice
La flexibilidad tiene un costo.
En una lista enlazada sencilla, si queremos encontrar el quinto elemento, normalmente debemos comenzar desde el inicio y avanzar nodo por nodo hasta llegar allí.
Acceso a una posición específica: O(n)Esto significa que, mientras más larga sea la lista, más pasos podríamos necesitar para llegar a un elemento concreto.
En un array, acceder por índice suele ser O(1). En una lista enlazada, acceder a una posición suele ser O(n).
Por eso no se puede decir que una estructura sea “mejor” que la otra en todos los casos. El array es excelente para acceso directo. La lista enlazada es útil cuando necesitamos insertar o eliminar elementos de forma flexible, especialmente si ya tenemos localizada la posición del cambio.
Tipos comunes de listas enlazadas
Existen varias formas de implementar listas enlazadas. Las más conocidas son:
Lista simplemente enlazada
Cada nodo apunta solamente al siguiente.
A -> B -> C -> NULLEs la forma más sencilla. Permite recorrer la lista hacia adelante.
Lista doblemente enlazada
Cada nodo apunta al siguiente y también al anterior.
NULL <- A <-> B <-> C -> NULLEsto permite recorrer la lista en ambos sentidos, pero requiere más memoria porque cada nodo guarda dos referencias.
Lista circular
El último nodo vuelve a apuntar al primero.
A -> B -> C
^ |
|_________|
Puede ser útil cuando necesitamos recorrer elementos en ciclo, como turnos, rondas o estructuras repetitivas.
Operaciones básicas de una lista enlazada
| Operación | Descripción | Costo típico |
|---|---|---|
| Acceder al primer nodo | Obtener el nodo inicial de la lista | O(1) |
| Recorrer la lista | Visitar los nodos uno por uno | O(n) |
| Buscar un valor | Comparar nodo por nodo hasta encontrarlo | O(n) |
| Insertar al inicio | Crear un nuevo nodo y hacerlo apuntar al antiguo inicio | O(1) |
| Insertar después de un nodo conocido | Ajustar referencias para colocar el nuevo nodo | O(1) |
| Eliminar después de un nodo conocido | Reenlazar el nodo anterior con el siguiente | O(1) |
| Acceder por posición | Avanzar desde el inicio hasta la posición deseada | O(n) |
Ejemplo en C++
En C++, una lista enlazada puede construirse definiendo una estructura para el nodo y usando punteros.
#include <iostream>
using namespace std;
struct Nodo {
int valor;
Nodo* siguiente;
};
void imprimirLista(Nodo* inicio) {
Nodo* actual = inicio;
while (actual != nullptr) {
cout << actual->valor << endl;
actual = actual->siguiente;
}
}
int main() {
Nodo* primero = new Nodo{10, nullptr};
Nodo* segundo = new Nodo{20, nullptr};
Nodo* tercero = new Nodo{30, nullptr};
primero->siguiente = segundo;
segundo->siguiente = tercero;
imprimirLista(primero);
delete primero;
delete segundo;
delete tercero;
return 0;
}
En este ejemplo, cada nodo guarda un valor entero y un puntero al siguiente nodo. La función imprimirLista comienza en el primer nodo y avanza hasta encontrar nullptr.
Ejemplo en C#
En C#, podemos representar un nodo mediante una clase. La referencia al siguiente nodo se guarda como una propiedad.
using System;
class Nodo
{
public int Valor { get; set; }
public Nodo? Siguiente { get; set; }
public Nodo(int valor)
{
Valor = valor;
Siguiente = null;
}
}
class Program
{
static void ImprimirLista(Nodo? inicio)
{
Nodo? actual = inicio;
while (actual != null)
{
Console.WriteLine(actual.Valor);
actual = actual.Siguiente;
}
}
static void Main()
{
Nodo primero = new Nodo(10);
Nodo segundo = new Nodo(20);
Nodo tercero = new Nodo(30);
primero.Siguiente = segundo;
segundo.Siguiente = tercero;
ImprimirLista(primero);
}
}
En este ejemplo, cada objeto Nodo guarda un valor y una referencia al siguiente. La lista se recorre comenzando desde el primer nodo.
Ejemplo en Python
En Python también podemos crear una lista enlazada definiendo una clase para representar cada nodo.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.siguiente = None
def imprimir_lista(inicio):
actual = inicio
while actual is not None:
print(actual.valor)
actual = actual.siguiente
primero = Nodo(10)
segundo = Nodo(20)
tercero = Nodo(30)
primero.siguiente = segundo
segundo.siguiente = tercero
imprimir_lista(primero)
Python ya trae listas dinámicas muy poderosas, pero construir una lista enlazada manualmente ayuda a entender cómo funcionan los nodos y las referencias.
¿Cuándo conviene usar una linked list?
Una lista enlazada puede convenir cuando:
- Necesitamos insertar o eliminar elementos con frecuencia.
- No sabemos de antemano cuántos elementos tendremos.
- Queremos evitar mover muchos elementos al insertar o borrar.
- Trabajamos con estructuras donde cada elemento conduce al siguiente.
- Queremos implementar otras estructuras, como pilas, colas o listas de adyacencia para grafos.
En cambio, si necesitamos acceso rápido por posición, probablemente un array o una lista dinámica sea más conveniente.
Aplicaciones reales
Las listas enlazadas aparecen en muchas áreas de la programación y de la informática:
- Implementación de pilas y colas.
- Listas de reproducción.
- Historiales de navegación.
- Administración de memoria.
- Estructuras internas de algunos sistemas operativos.
- Representación de grafos mediante listas de adyacencia.
- Procesamiento de datos donde las inserciones y eliminaciones son frecuentes.
Aunque en muchos lenguajes modernos usamos colecciones ya construidas, entender la lista enlazada sigue siendo fundamental. Nos obliga a pensar en referencias, enlaces, recorrido secuencial y manejo explícito de la relación entre elementos.
La lección de la lista enlazada
La lista enlazada enseña una idea diferente a la del array. El array confía en la posición. La lista enlazada confía en el enlace.
En el array preguntamos: ¿en qué índice está el dato?
En la lista enlazada preguntamos: ¿cuál es el siguiente nodo?
Ambas preguntas son importantes. Y cada una revela una forma distinta de organizar la memoria.
Cuando necesitamos acceso directo, el array suele ser más fuerte. Cuando necesitamos flexibilidad para insertar y eliminar, la lista enlazada puede ofrecer ventajas. La decisión depende del problema.
La lista enlazada nos recuerda que, en programación, muchas veces avanzar consiste simplemente en conservar bien la referencia al siguiente paso.
Próxima entrega
En el próximo artículo de esta saga estudiaremos la stack, o pila. Allí veremos una estructura basada en una regla muy sencilla y poderosa: el último elemento en entrar es el primero en salir.
Pasaremos de la búsqueda del tesoro a la lógica del Control Z, la recursividad y la pila de llamadas.