Estructuras encadenadas en Python — LinkedList desde cero sin misterio
Las estructuras encadenadas en Python son el último bloque de FP2 y el que más peso tiene en el segundo parcial. La mayoría de la gente llega aquí con el concepto de nodo sin terminar de cuajar, entiende las palabras por separado pero no consigue visualizar cómo funciona la cadena entera.
En este artículo vamos desde el principio absoluto: qué son las LinkedList en Python, qué es un nodo de verdad, cómo se conectan, y cómo se implementa cada operación con su diagrama paso a paso.
Tabla de Contenidos
Antes de empezar — qué problema resuelven las estructuras encadenadas
Cuando usas una lista de Python [1, 2, 3, 4, 5], Python guarda todos los elementos en posiciones de memoria consecutivas, como una fila de casillas numeradas:
Posición: [0] [1] [2] [3] [4] Valor: 1 2 3 4 5
Eso tiene una ventaja enorme: acceder al elemento 3 es instantáneo porque Python calcula directamente su posición en memoria. Pero tiene un coste oculto: insertar o eliminar en el medio es caro, Python tiene que desplazar todos los elementos que vienen después.
Insertar 99 en posición 2:
Antes: [1] [2] [3] [4] [5]
← desplazar todo →
Después: [1] [2] [99] [3] [4] [5]
Con un millón de elementos, insertar al principio significa mover un millón de valores en memoria.
Las estructuras encadenadas resuelven exactamente ese problema, insertar y eliminar en cualquier posición es siempre igual de rápido, sin mover nada. El coste que pagan por eso es que acceder a un elemento concreto requiere recorrer la lista desde el principio.
Lista de Python: acceso por índice rápido, inserción/borrado en medio lento LinkedList: acceso por índice lento, inserción/borrado en cualquier punto rápido
En FP2 no usamos LinkedList porque sea siempre mejor, la usamos para entender cómo se gestionan las referencias en memoria, que es la base de las estructuras de datos complejas.
Qué es un nodo — la unidad básica
Un nodo es la pieza más pequeña de una estructura encadenada. Cada nodo contiene exactamente dos cosas:
- El valor que guarda (un número, una cadena, cualquier objeto)
- Una referencia al siguiente nodo — o
Nonesi es el último
Nada más. Un nodo no sabe cuántos elementos hay en la lista. No sabe en qué posición está. Solo sabe su valor y quién viene después de él.
┌──────────┬──────────┐ │ valor │siguiente │ │ 10 │ ──────► │ → (apunta al siguiente nodo) └──────────┴──────────┘
┌──────────┬──────────┐ │ valor │siguiente │ │ 10 │ None │ (último nodo — no hay siguiente) └──────────┴──────────┘
Por qué necesita su propia clase: porque es un objeto con dos atributos propios que tiene que existir de forma independiente en memoria. No es un número, no es una tupla, es un objeto que guarda un valor y sabe a quién apunta.
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
Solo eso. La clase Nodo tiene dos atributos: valor y siguiente. El parámetro siguiente tiene valor por defecto None porque cuando creas un nodo nuevo normalmente todavía no sabes quién viene después.
Puedes crear nodos y encadenarlos manualmente para ver cómo funciona:
# Crear tres nodos sueltos nodo1 = Nodo(10) nodo2 = Nodo(20) nodo3 = Nodo(30) # Encadenarlos a mano nodo1.siguiente = nodo2 nodo2.siguiente = nodo3 # nodo3.siguiente sigue siendo None — es el último print(nodo1.valor) # → 10 print(nodo1.siguiente.valor) # → 20 print(nodo1.siguiente.siguiente.valor) # → 30 print(nodo1.siguiente.siguiente.siguiente) # → None
nodo1 nodo2 nodo3 ┌────┬────────┐ ┌────┬────────┐ ┌────┬──────┐ │ 10 │ ──────► │ 20 │ ──────► │ 30 │ None │ └────┴────────┘ └────┴────────┘ └────┴──────┘
Eso ya es una lista encadenada, tres nodos conectados en cadena. Solo falta envolverlos en una clase que gestione el conjunto.
Cómo se enlazan los nodos en memoria
Lo que en el diagrama ves como una flecha ──► es en realidad una referencia, la dirección de memoria donde está el siguiente nodo. Cuando haces nodo1.siguiente = nodo2 no estás copiando nodo2 dentro de nodo1, estás guardando en nodo1.siguiente la dirección donde está nodo2 en la memoria de Python.
Esto tiene una consecuencia importante: los nodos pueden estar en cualquier parte de la memoria, no tienen que ser posiciones consecutivas como en una lista de Python. Por eso insertar en el medio es tan barato: solo cambias a qué apuntan dos referencias, sin mover ningún dato.
Memoria RAM (ejemplo): posición 0x1000: nodo con valor 10, siguiente → 0x2500 posición 0x2500: nodo con valor 20, siguiente → 0x0800 posición 0x0800: nodo con valor 30, siguiente → None Los nodos están dispersos en memoria — la cadena los une con referencias
La clase LinkedList — qué necesita
La clase LinkedList no guarda los elementos directamente, guarda una referencia al primer nodo de la cadena. A ese primer nodo se le llama cabeza (head o primero). Con esa sola referencia puedes llegar a cualquier elemento, siguiendo la cadena de siguiente en siguiente.
LinkedList
┌──────────┐
│ primero ─────► ┌────┬───┐ ┌────┬───┐ ┌────┬──────┐
└──────────┘ │ 10 │ ──────► 20 │ ──────► 30 │ None │
└────┴───┘ └────┴───┘ └────┴──────┘
Si la lista está vacía, primero vale None:
LinkedList ┌──────────┐ │ primero │ → None └──────────┘
class LinkedList:
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
def __init__(self):
self.__primero = None
self.__longitud = 0
Fíjate en que Nodo está dentro de LinkedList como clase anidada, en FP2 así es como aparece en el PDF. Es una clase interna porque los nodos son un detalle de implementación que no debería usarse desde fuera de la lista.
Operación 1 — Insertar al principio
Insertar al principio es la operación más sencilla y la más rápida. El proceso tiene siempre dos pasos:
- Crear el nuevo nodo apuntando al actual primero
- El nuevo nodo pasa a ser el primero
Antes de insertar 5: primero ──► [10] ──► [20] ──► [30] ──► None Paso 1 — crear nodo con siguiente = primero actual: nuevo ──► [5] ──► [10] ──► [20] ──► [30] ──► None Paso 2 — primero ahora apunta al nuevo nodo: primero ──► [5] ──► [10] ──► [20] ──► [30] ──► None
El orden de los pasos importa mucho. Si primero actualizas primero y luego intentas conectar el nuevo nodo al siguiente, pierdes la referencia al resto de la lista. Primero conectas, luego actualizas.
def insertar_delante(self, valor):
nuevo = self.Nodo(valor, self.__primero) # paso 1: conectar al actual primero
self.__primero = nuevo # paso 2: el nuevo es el primero
self.__longitud += 1
O en una sola línea:
def insertar_delante(self, valor):
self.__primero = self.Nodo(valor, self.__primero)
self.__longitud += 1
Operación 2 — Insertar al final
Insertar al final requiere recorrer toda la lista hasta llegar al último nodo, el que tiene siguiente = None, y conectar el nuevo nodo ahí.
Antes de insertar 40 al final:
primero ──► [10] ──► [20] ──► [30] ──► None
Recorremos hasta el último nodo (el que tiene siguiente=None):
actual
primero ──► [10] ──► [20] ──► [30] ──► None
Conectamos el nuevo nodo:
primero ──► [10] ──► [20] ──► [30] ──► [40] ──► None
Hay un caso especial: si la lista está vacía, el nuevo nodo es directamente el primero.
def insertar_detras(self, valor):
nuevo = self.Nodo(valor)
if self.__primero is None: # lista vacía — caso especial
self.__primero = nuevo
else:
actual = self.__primero
while actual.siguiente is not None: # avanzar hasta el último
actual = actual.siguiente
actual.siguiente = nuevo # conectar el nuevo al final
self.__longitud += 1
El while actual.siguiente is not None es el patrón de recorrido más importante de LinkedList, memorízalo porque aparece en casi todas las operaciones.
Operación 3 — Recorrer la lista
Recorrer la lista nodo a nodo siempre sigue el mismo patrón: empiezas en primero y avanzas con actual = actual.siguiente hasta que actual sea None.
primero ──► [10] ──► [20] ──► [30] ──► None actual=10 → actual=20 → actual=30 → actual=None → STOP
def __str__(self):
"""Muestra la lista como: 10 → 20 → 30 → None"""
elementos = []
actual = self.__primero
while actual is not None:
elementos.append(str(actual.valor))
actual = actual.siguiente
return ' → '.join(elementos) + ' → None'
def __len__(self):
return self.__longitud
def __iter__(self):
"""Permite usar la lista en un for."""
actual = self.__primero
while actual is not None:
valor = actual.valor
actual = actual.siguiente
yield valor
Fíjate en __iter__, guardamos actual.siguiente antes del yield porque el generador se pausa en yield y si alguien modifica la lista mientras la recorre podría haber problemas. Es el patrón seguro.
Operación 4 — Buscar un elemento
La búsqueda recorre la lista comparando cada valor hasta encontrar el elemento o llegar al final.
Buscar 20 en: [10] ──► [20] ──► [30] ──► None actual=[10] → 10 != 20 → avanzar actual=[20] → 20 == 20 → encontrado → devolver True (o el nodo)
def contiene(self, valor):
"""Devuelve True si el valor está en la lista."""
actual = self.__primero
while actual is not None:
if actual.valor == valor:
return True
actual = actual.siguiente
return False # llegamos al final sin encontrarlo
Operación 5 — Eliminar un elemento
Eliminar es la operación que más cuesta visualizar. La clave es entender que para eliminar un nodo no necesitas borrarlo — solo necesitas que el nodo anterior deje de apuntar a él y apunte directamente al siguiente.
Eliminar 20 de: [10] ──► [20] ──► [30] ──► None Antes: [10].siguiente ──► [20] [20].siguiente ──► [30] Después de eliminar [20]: [10].siguiente ──► [30] ← saltamos el nodo 20 El nodo [20] sigue existiendo en memoria pero ya nadie apunta a él Python lo eliminará automáticamente (garbage collector)
Hay tres casos que manejar:
Caso 1 — Eliminar el primero:
primero ──► [10] ──► [20] ──► [30] ──► None
↑
eliminar este
primero ──► [20] ──► [30] ──► None
Caso 2 — Eliminar un nodo en el medio:
[10] ──► [20] ──► [30] ──► None
↑
eliminar este
[10] ──► [30] ──► None
Caso 3 — Eliminar el último:
[10] ──► [20] ──► [30] ──► None
↑
eliminar este
[10] ──► [20] ──► None
def eliminar(self, valor):
"""Elimina la primera ocurrencia del valor. Lanza ValueError si no existe."""
if self.__primero is None:
raise ValueError(f"{valor} no está en la lista")
# Caso 1 — el valor está en el primer nodo
if self.__primero.valor == valor:
self.__primero = self.__primero.siguiente # primero apunta al segundo
self.__longitud -= 1
return
# Casos 2 y 3 — buscar el nodo ANTERIOR al que queremos eliminar
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor == valor:
anterior.siguiente = actual.siguiente # saltamos el nodo actual
self.__longitud -= 1
return
anterior = actual
actual = actual.siguiente
raise ValueError(f"{valor} no está en la lista")
El patrón anterior / actual que avanza en pareja es la clave de la eliminación:
anterior ──► actual ──► siguiente [10] ──► [20] ──► [30] Si queremos eliminar actual (20): anterior.siguiente = actual.siguiente [10].siguiente = [30] Resultado: [10] ──► [30] (el [20] queda aislado)
La clase completa
class LinkedList:
"""Lista simplemente encadenada."""
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
def __init__(self):
self.__primero = None
self.__longitud = 0
def insertar_delante(self, valor):
"""Inserta al principio en O(1)."""
self.__primero = self.Nodo(valor, self.__primero)
self.__longitud += 1
def insertar_detras(self, valor):
"""Inserta al final en O(n)."""
nuevo = self.Nodo(valor)
if self.__primero is None:
self.__primero = nuevo
else:
actual = self.__primero
while actual.siguiente is not None:
actual = actual.siguiente
actual.siguiente = nuevo
self.__longitud += 1
def eliminar(self, valor):
"""Elimina la primera ocurrencia. Lanza ValueError si no existe."""
if self.__primero is None:
raise ValueError(f"{valor} no está en la lista")
if self.__primero.valor == valor:
self.__primero = self.__primero.siguiente
self.__longitud -= 1
return
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor == valor:
anterior.siguiente = actual.siguiente
self.__longitud -= 1
return
anterior = actual
actual = actual.siguiente
raise ValueError(f"{valor} no está en la lista")
def contiene(self, valor):
"""Devuelve True si el valor está en la lista."""
actual = self.__primero
while actual is not None:
if actual.valor == valor:
return True
actual = actual.siguiente
return False
def es_vacia(self):
return self.__primero is None
def __len__(self):
return self.__longitud
def __iter__(self):
actual = self.__primero
while actual is not None:
valor = actual.valor
actual = actual.siguiente
yield valor
def __str__(self):
return ' → '.join(str(v) for v in self) + ' → None'
def __repr__(self):
return f'LinkedList({list(self)})'
def __contains__(self, valor):
return self.contiene(valor)
LinkedList vs lista de Python — cuándo usar cada una
Lista Python LinkedList ───────────────────────────────────────────── Acceso por índice: O(1) ✓ O(n) ✗ Insertar al principio: O(n) ✗ O(1) ✓ Insertar al final: O(1) ✓ O(n) ✗ Insertar en el medio: O(n) ✗ O(1) ✓ (si ya tienes el nodo anterior) Buscar un elemento: O(n) O(n) Memoria: más eficiente menos eficiente (cada nodo tiene el puntero)
En FP2 la LinkedList no se usa porque sea mejor en todo, se usa para aprender a gestionar referencias y punteros, que es la base de árboles, grafos y otras estructuras que veremos en cursos posteriores.
Visualízalo con Python Tutor
Las LinkedList son donde Python Tutor más brilla de todo el curso, puedes ver exactamente cómo cada nodo apunta al siguiente y cómo las referencias cambian al insertar o eliminar. Ve a pythontutor.com y pega:
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
# Construir una lista de 3 nodos manualmente
n1 = Nodo(10)
n2 = Nodo(20)
n3 = Nodo(30)
n1.siguiente = n2
n2.siguiente = n3
# Recorrer
actual = n1
while actual is not None:
print(actual.valor)
actual = actual.siguiente
Ejecuta paso a paso y observa cómo actual va saltando de nodo en nodo siguiendo las flechas. Luego modifica el código para insertar un nodo nuevo entre n1 y n2, verás exactamente qué referencias cambian.
Resumen rápido
# NODO — la unidad básica
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor # el dato
self.siguiente = siguiente # referencia al siguiente nodo o None
# ESTRUCTURA DE UNA LISTA ENCADENADA
# primero ──► [v1] ──► [v2] ──► [v3] ──► None
# Solo se guarda una referencia al primer nodo
# Para llegar a cualquier elemento hay que recorrer desde el principio
# INSERTAR AL PRINCIPIO — O(1)
nuevo = Nodo(valor, primero) # conectar al actual primero
primero = nuevo # el nuevo es ahora el primero
# INSERTAR AL FINAL — O(n)
actual = primero
while actual.siguiente is not None: # avanzar hasta el último
actual = actual.siguiente
actual.siguiente = Nodo(valor) # conectar al final
# RECORRER — O(n)
actual = primero
while actual is not None:
print(actual.valor)
actual = actual.siguiente # avanzar al siguiente
# ELIMINAR — O(n)
# Caso especial: eliminar el primero
primero = primero.siguiente
# Caso general: usar pareja anterior/actual
anterior = primero
actual = primero.siguiente
while actual is not None:
if actual.valor == buscado:
anterior.siguiente = actual.siguiente # saltar el nodo
break
anterior = actual
actual = actual.siguiente
# CUÁNDO USAR LinkedList vs lista de Python
# Lista Python → acceso por índice, inserción al final, secuencias estables
# LinkedList → muchas inserciones/borrados al principio, aprender estructuras
# ERRORES TÍPICOS
# 1. Actualizar primero antes de conectar el nuevo nodo → pierdes la lista
# 2. Olvidar el caso especial de lista vacía en insertar_detras
# 3. Olvidar el caso especial de eliminar el primer nodo
# 4. No guardar actual.siguiente antes de modificar anterior.siguiente
En el próximo artículo practicamos la LinkedList con programas reales, incluyendo cómo invertir una lista encadenada y cómo ordenar sus elementos.
Siguiente paso: prácticaLinkedList en Python — 3 programas reales que consolidan la estructura¿Te ha servido este artículo? Así puedes apoyar SergioLearns →
2 comentarios