LinkedList en Python — ejercicios para dominar las estructuras encadenadas
La LinkedList en Python ejercicios con solución cierran este bloque y con él el temario completo de FP2. Ya viste la teoría y practicaste con programas reales. Ahora toca resolver por tu cuenta. Tres ejercicios en tres niveles, todos con su diagrama, sus pistas y su solución comentada. El hilo conductor es siempre el mismo: los dos errores que más destrozan una implementación de LinkedList son modificar un puntero antes de guardar el siguiente, y olvidar los casos especiales de lista vacía o de un solo elemento.
Como siempre: intenta resolverlo, usa la pista si llevas más de 10 minutos atascado, pega tu código en pythontutor.com y compara con la solución comentada al final.
Partimos de la clase LinkedList completa del artículo de teoría.
Tabla de Contenidos
LinkedList en Python ejercicios — Nivel Básico
Ejercicio 1 — Obtener el elemento en la posición N
Añade a la clase LinkedList un método obtener(posicion) que devuelva el valor del elemento en la posición dada (empezando desde 0). Si la posición no existe, lanza IndexError.
La salida debe ser:
Lista: 10 → 20 → 30 → 40 → 50 → None lista.obtener(0) → 10 (primer elemento) lista.obtener(2) → 30 (tercero) lista.obtener(4) → 50 (último) lista.obtener(5) → IndexError: posición 5 fuera de rango (longitud 5) lista.obtener(-1) → IndexError: posición -1 fuera de rango (longitud 5)
El reto adicional: implementa también obtener_desde_final(posicion) que devuelva el elemento contando desde el final, posición 0 es el último, posición 1 el penúltimo, etc. Sin conocer la longitud de la lista y en un solo recorrido.
lista.obtener_desde_final(0) → 50 (último) lista.obtener_desde_final(1) → 40 (penúltimo) lista.obtener_desde_final(4) → 10 (primero)
💡 Pista — el error de olvidar casos especiales:
# MAL — no valida la posición
def obtener(self, posicion):
actual = self.__primero
for i in range(posicion):
actual = actual.siguiente # si posicion > longitud → AttributeError en None.siguiente
return actual.valor # si lista vacía → AttributeError en None.valor
# BIEN — valida primero
def obtener(self, posicion):
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(f"posición {posicion} fuera de rango (longitud {self.__longitud})")
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
Para obtener_desde_final sin conocer la longitud, la técnica clásica usa dos punteros que avanzan a distinta velocidad, uno va N pasos por delante del otro:
Queremos el elemento en posición 1 desde el final (penúltimo) en lista: 10 → 20 → 30 → 40 → 50 → None Adelantamos el puntero rápido N+1 pasos: rapido avanza 2 pasos: apunta a [30] lento apunta a [10] Ahora avanzamos los dos juntos hasta que rápido llega a None: rapido=[30], lento=[10] → rapido=[40], lento=[20] rapido=[40], lento=[20] → rapido=[50], lento=[30] rapido=[50], lento=[30] → rapido=None, lento=[40] rapido=None → lento apunta al penúltimo → devolver lento.valor = 40 ✓
LinkedList en Python ejercicios — Nivel Intermedio
Ejercicio 2 — Eliminar duplicados de una LinkedList
Añade a la clase LinkedList un método eliminar_duplicados() que elimine todas las ocurrencias duplicadas dejando solo la primera aparición de cada valor. La lista original se modifica en su lugar.
La salida debe ser:
Lista original: 10 → 20 → 10 → 30 → 20 → 40 → 10 → None Después de eliminar_duplicados(): 10 → 20 → 30 → 40 → None Lista sin duplicados desde el principio: 5 → 8 → 3 → None Después de eliminar_duplicados(): 5 → 8 → 3 → None (no cambia) Lista con todos iguales: 7 → 7 → 7 → 7 → None Después de eliminar_duplicados(): 7 → None
La operación debe ser en el mismo lugar, sin crear una lista nueva. El método modifica self.
💡 Pistas:
El error de modificar primero antes de guardar siguiente aparece aquí de forma muy sutil. Cuando eliminas un nodo duplicado tienes que usar el patrón anterior / actual:
# MAL — pierdes el siguiente al duplicado
if actual.valor in vistos:
anterior.siguiente = actual.siguiente # ← bien hasta aquí
actual = actual.siguiente # ← también bien
# pero si no era duplicado:
anterior = actual # ← MAL: anterior NO debe avanzar cuando eliminas
actual = actual.siguiente
# BIEN — la clave está en cuándo avanzas anterior
if actual.valor in vistos:
anterior.siguiente = actual.siguiente # elimina el nodo
actual = actual.siguiente # avanza solo actual
# anterior NO avanza — sigue apuntando al mismo nodo
else:
vistos.add(actual.valor)
anterior = actual # avanza anterior solo si NO eliminaste
actual = actual.siguiente
El caso especial de lista vacía o de un solo elemento: si __primero es None o si no hay duplicados, el método debe funcionar sin hacer nada ni lanzar errores.
Para saber qué valores ya has visto usa un set, la estructura perfecta para comprobar pertenencia en O(1):
vistos = set() # si actual.valor in vistos → es duplicado → eliminar # si actual.valor not in vistos → primera vez → añadir a vistos
LinkedList en Python ejercicios — Desafío Final
Ejercicio 3 — Detectar si una LinkedList tiene un ciclo
Una LinkedList tiene un ciclo cuando uno de sus nodos apunta a un nodo anterior en vez de avanzar hacia None. Eso hace que la lista sea infinita, si intentas recorrerla con el patrón habitual nunca terminas.
Lista normal:
[10] → [20] → [30] → [40] → None
Lista con ciclo (el último apunta al segundo):
[10] → [20] → [30] → [40]
↑ |
└─────────┘
Implementa el método tiene_ciclo() que devuelva True si la lista tiene un ciclo y False si no. Sin modificar la lista y usando O(1) de memoria extra, es decir, sin guardar los nodos visitados en una lista o set.
La salida debe ser:
Lista normal (10 → 20 → 30 → None): tiene_ciclo() → False Lista con ciclo (40 apunta a 20): tiene_ciclo() → True Lista vacía: tiene_ciclo() → False Lista de un elemento sin ciclo: tiene_ciclo() → False Lista de un elemento con ciclo (apunta a sí mismo): tiene_ciclo() → True
💡 Pistas:
La solución clásica para detectar ciclos sin usar memoria extra es el algoritmo de Floyd, también llamado algoritmo de la liebre y la tortuga. Usa dos punteros que avanzan a distinta velocidad:
tortuga → avanza 1 nodo por iteración liebre → avanza 2 nodos por iteración Si no hay ciclo: liebre llegará a None antes que tortuga → False Si hay ciclo: liebre y tortuga se encontrarán en algún nodo → True
Lista con ciclo: [10] → [20] → [30] → [40] ──┐
↑ │
└────────────────────┘
Inicio: tortuga=[10], liebre=[10]
Paso 1: tortuga=[20], liebre=[30]
Paso 2: tortuga=[30], liebre=[20] ← liebre dio la vuelta por el ciclo
Paso 3: tortuga=[40], liebre=[40] ← ¡se encuentran! → hay ciclo
Los dos casos especiales críticos: lista vacía (__primero es None) y lista de un elemento. Si el único nodo apunta a sí mismo hay ciclo. Si apunta a None no lo hay. Compruébalos antes de entrar al bucle para evitar errores.
Para crear una lista con ciclo en las pruebas tendrás que acceder directamente a los nodos, la clase no expone ese nivel de detalle por diseño, así que en el ejercicio puedes crear los nodos manualmente:
# Crear lista con ciclo para probar
from linked_list import LinkedList
lista = LinkedList()
lista.insertar_detras(10)
lista.insertar_detras(20)
lista.insertar_detras(30)
lista.insertar_detras(40)
# Acceder al nodo interno para crear el ciclo (solo para la prueba)
nodo_actual = lista._LinkedList__primero
nodo_segundo = nodo_actual.siguiente
while nodo_actual.siguiente is not None:
nodo_actual = nodo_actual.siguiente
nodo_actual.siguiente = nodo_segundo # el último apunta al segundo → ciclo
Soluciones Comentadas
Solución Ejercicio 1:
def obtener(self, posicion):
"""Devuelve el valor en la posición dada (desde 0). Lanza IndexError si no existe."""
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(
f"posición {posicion} fuera de rango (longitud {self.__longitud})"
)
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
def obtener_desde_final(self, posicion):
"""
Devuelve el valor en la posición desde el final (0=último).
Usa dos punteros — un solo recorrido, sin conocer la longitud.
"""
if posicion < 0:
raise IndexError(f"posición {posicion} no puede ser negativa")
# Adelantar el puntero rápido posicion+1 pasos
rapido = self.__primero
for _ in range(posicion + 1):
if rapido is None:
raise IndexError(
f"posición {posicion} desde el final fuera de rango"
)
rapido = rapido.siguiente
# Avanzar los dos juntos hasta que rápido llegue a None
lento = self.__primero
while rapido is not None:
lento = lento.siguiente
rapido = rapido.siguiente
# lento apunta al nodo en la posición correcta desde el final
return lento.valor
# ── Pruebas ────────────────────────────────────────────────────────────
lista = LinkedList()
for v in [10, 20, 30, 40, 50]:
lista.insertar_detras(v)
print(f"Lista: {lista}")
# → 10 → 20 → 30 → 40 → 50 → None
print(f"\nobtener(0) → {lista.obtener(0)}") # → 10
print(f"obtener(2) → {lista.obtener(2)}") # → 30
print(f"obtener(4) → {lista.obtener(4)}") # → 50
try:
lista.obtener(5)
except IndexError as e:
print(f"obtener(5) → IndexError: {e}")
# → IndexError: posición 5 fuera de rango (longitud 5)
try:
lista.obtener(-1)
except IndexError as e:
print(f"obtener(-1) → IndexError: {e}")
print(f"\nobtener_desde_final(0) → {lista.obtener_desde_final(0)}") # → 50
print(f"obtener_desde_final(1) → {lista.obtener_desde_final(1)}") # → 40
print(f"obtener_desde_final(4) → {lista.obtener_desde_final(4)}") # → 10
try:
lista.obtener_desde_final(5)
except IndexError as e:
print(f"obtener_desde_final(5) → IndexError: {e}")
Solución Ejercicio 2:
def eliminar_duplicados(self):
"""
Elimina duplicados en el lugar, manteniendo la primera aparición.
Modifica self — no crea lista nueva.
"""
if self.__primero is None: # lista vacía — nada que hacer
return
vistos = set()
vistos.add(self.__primero.valor)
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor in vistos:
# Es duplicado — eliminar: anterior no avanza
anterior.siguiente = actual.siguiente
actual = actual.siguiente
self.__longitud -= 1
else:
# Primera aparición — guardar y avanzar ambos
vistos.add(actual.valor)
anterior = actual
actual = actual.siguiente
# ── Pruebas ────────────────────────────────────────────────────────────
# Lista con duplicados
lista = LinkedList()
for v in [10, 20, 10, 30, 20, 40, 10]:
lista.insertar_detras(v)
print(f"Antes: {lista}")
lista.eliminar_duplicados()
print(f"Después: {lista}")
# → 10 → 20 → 30 → 40 → None
print(f"Longitud: {len(lista)}") # → 4
# Lista sin duplicados — no debe cambiar
lista2 = LinkedList()
for v in [5, 8, 3]:
lista2.insertar_detras(v)
print(f"\nAntes: {lista2}")
lista2.eliminar_duplicados()
print(f"Después: {lista2}")
# → 5 → 8 → 3 → None
# Lista con todos iguales
lista3 = LinkedList()
for v in [7, 7, 7, 7]:
lista3.insertar_detras(v)
print(f"\nAntes: {lista3}")
lista3.eliminar_duplicados()
print(f"Después: {lista3}")
# → 7 → None
print(f"Longitud: {len(lista3)}") # → 1
# Lista vacía — no debe lanzar error
lista4 = LinkedList()
lista4.eliminar_duplicados()
print(f"\nLista vacía después: {lista4}")
# → None
# Lista de un elemento — no debe cambiar
lista5 = LinkedList()
lista5.insertar_delante(42)
lista5.eliminar_duplicados()
print(f"Un elemento después: {lista5}")
# → 42 → None
Solución Ejercicio 3:
def tiene_ciclo(self):
"""
Detecta si la lista tiene un ciclo usando el algoritmo de Floyd.
O(n) tiempo, O(1) espacio — no usa memoria extra.
"""
# Caso especial — lista vacía o un solo nodo sin ciclo
if self.__primero is None:
return False
if self.__primero.siguiente is None:
return False
tortuga = self.__primero # avanza 1 nodo por iteración
liebre = self.__primero.siguiente # avanza 2 nodos por iteración
while liebre is not None and liebre.siguiente is not None:
if tortuga is liebre: # se encontraron → hay ciclo
return True
tortuga = tortuga.siguiente
liebre = liebre.siguiente.siguiente
return False # liebre llegó a None → no hay ciclo
# ── Pruebas ────────────────────────────────────────────────────────────
# Lista normal sin ciclo
lista_normal = LinkedList()
for v in [10, 20, 30, 40]:
lista_normal.insertar_detras(v)
print(f"Lista normal: {lista_normal}")
print(f"tiene_ciclo() → {lista_normal.tiene_ciclo()}") # → False
# Lista vacía
lista_vacia = LinkedList()
print(f"\nLista vacía:")
print(f"tiene_ciclo() → {lista_vacia.tiene_ciclo()}") # → False
# Lista de un elemento sin ciclo
lista_uno = LinkedList()
lista_uno.insertar_delante(42)
print(f"\nUn elemento sin ciclo:")
print(f"tiene_ciclo() → {lista_uno.tiene_ciclo()}") # → False
# Lista de un elemento con ciclo (apunta a sí mismo)
lista_ciclo_uno = LinkedList()
lista_ciclo_uno.insertar_delante(42)
nodo = lista_ciclo_uno._LinkedList__primero
nodo.siguiente = nodo # apunta a sí mismo
print(f"\nUn elemento con ciclo:")
print(f"tiene_ciclo() → {lista_ciclo_uno.tiene_ciclo()}") # → True
# Lista con ciclo (el último apunta al segundo)
lista_ciclo = LinkedList()
for v in [10, 20, 30, 40]:
lista_ciclo.insertar_detras(v)
# Crear el ciclo manualmente: [40] → [20]
nodo_actual = lista_ciclo._LinkedList__primero
nodo_segundo = nodo_actual.siguiente
while nodo_actual.siguiente is not None:
nodo_actual = nodo_actual.siguiente
nodo_actual.siguiente = nodo_segundo # [40] → [20]
print(f"\nLista con ciclo (40 → 20):")
print(f"tiene_ciclo() → {lista_ciclo.tiene_ciclo()}") # → True
Chuletario — LinkedList y estructuras encadenadas en Python
# ============================================
# CHULETARIO — LinkedList en Python
# Sergio Learns · sergiolearns.com
# ============================================
# ── NODO ─────────────────────────────────────────────────────
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor # el dato
self.siguiente = siguiente # referencia al siguiente o None
# Diagrama: [valor | siguiente ──►] → [valor | siguiente ──►] → None
# ── ESTRUCTURA LinkedList ────────────────────────────────────
class LinkedList:
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
def __init__(self):
self.__primero = None # referencia al primer nodo
self.__longitud = 0 # número de elementos
# Lista vacía: primero → None
# Lista con datos: primero → [v1] → [v2] → [v3] → None
# ── OPERACIONES BÁSICAS ──────────────────────────────────────
# INSERTAR AL PRINCIPIO — O(1)
def insertar_delante(self, valor):
self.__primero = self.Nodo(valor, self.__primero)
self.__longitud += 1
# Diagrama:
# Antes: primero → [10] → [20] → None
# Después: primero → [5] → [10] → [20] → None
# INSERTAR AL FINAL — O(n)
def insertar_detras(self, valor):
nuevo = self.Nodo(valor)
if self.__primero is None: # caso especial: lista vacía
self.__primero = nuevo
else:
actual = self.__primero
while actual.siguiente is not None: # avanzar al último
actual = actual.siguiente
actual.siguiente = nuevo
self.__longitud += 1
# RECORRIDO — O(n) — el patrón más importante
actual = self.__primero
while actual is not None:
# hacer algo con actual.valor
actual = actual.siguiente # avanzar al siguiente
# ELIMINAR — O(n)
# Caso 1: eliminar el primero
self.__primero = self.__primero.siguiente
# Caso 2: eliminar cualquier otro (patrón anterior/actual)
anterior = self.__primero
actual = self.__primero.siguiente
while actual is not None:
if actual.valor == buscado:
anterior.siguiente = actual.siguiente # saltar el nodo
self.__longitud -= 1
break
anterior = actual # avanzar AMBOS cuando NO eliminas
actual = actual.siguiente
# BUSCAR — O(n)
actual = self.__primero
while actual is not None:
if actual.valor == buscado:
return True
actual = actual.siguiente
return False
# OBTENER POR POSICIÓN — O(n)
# Validar primero
if posicion < 0 or posicion >= self.__longitud:
raise IndexError(...)
actual = self.__primero
for _ in range(posicion):
actual = actual.siguiente
return actual.valor
# ── PATRONES AVANZADOS ───────────────────────────────────────
# PATRÓN 1 — acumulador en recorrido
# Para: contar, sumar, máximo, mínimo, filtrar
acumulador = valor_inicial
actual = primero
while actual is not None:
acumulador = operacion(acumulador, actual.valor)
actual = actual.siguiente
# PATRÓN 2 — tres variables para invertir punteros
# Para: invertir lista, operaciones que invierten referencias
anterior = None
actual = primero
while actual is not None:
siguiente = actual.siguiente # ← GUARDAR ANTES de modificar
actual.siguiente = anterior # ← invertir
anterior = actual # ← avanzar anterior
actual = siguiente # ← avanzar actual
primero = anterior # ← nuevo primero
# PATRÓN 3 — dos punteros a distinta velocidad
# Para: detectar ciclos (Floyd), encontrar elemento desde el final
tortuga = primero # avanza 1
liebre = primero # avanza 2
while liebre is not None and liebre.siguiente is not None:
if tortuga is liebre: # se encontraron → hay ciclo
return True
tortuga = tortuga.siguiente
liebre = liebre.siguiente.siguiente
return False
# PATRÓN 4 — inserción ordenada
# Para: mantener la lista ordenada al insertar
actual = primero
while actual.siguiente is not None and actual.siguiente.valor < nuevo_valor:
actual = actual.siguiente
nuevo.siguiente = actual.siguiente # conectar al resto
actual.siguiente = nuevo # conectar nuevo nodo
# PATRÓN 5 — anterior/actual para eliminar con condición
# Para: eliminar duplicados, eliminar todos los que cumplan algo
vistos = set()
anterior = primero
actual = primero.siguiente
while actual is not None:
if condicion(actual.valor):
anterior.siguiente = actual.siguiente # eliminar
actual = actual.siguiente
# anterior NO avanza cuando eliminas
else:
anterior = actual # avanzar AMBOS
actual = actual.siguiente # cuando NO eliminas
# ── MÉTODOS MÁGICOS ──────────────────────────────────────────
def __len__(self):
return self.__longitud
def __str__(self):
return ' → '.join(str(v) for v in self) + ' → None'
def __repr__(self):
return f'LinkedList({list(self)})'
def __iter__(self): # hace la lista iterable con for
actual = self.__primero
while actual is not None:
valor = actual.valor
actual = actual.siguiente # avanzar ANTES del yield
yield valor # pausa aquí
def __contains__(self, valor):
return self.contiene(valor)
# ── LinkedList vs LISTA DE PYTHON ────────────────────────────
# 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) ✓ (con nodo anterior)
# Buscar: O(n) O(n)
# Memoria: más eficiente menos eficiente
# ── ERRORES TÍPICOS ──────────────────────────────────────────
# ERROR 1 — modificar el puntero antes de guardar el siguiente
# PIERDE el resto de la lista
# MAL
actual.siguiente = anterior # ← ya no puedes llegar al siguiente
siguiente = actual.siguiente # ← esto ahora da anterior, no el real
# BIEN
siguiente = actual.siguiente # ← guardar PRIMERO
actual.siguiente = anterior # ← luego modificar
# ERROR 2 — olvidar el caso especial de lista vacía
# Siempre comprobar self.__primero is None antes de acceder a .valor o .siguiente
def metodo(self):
if self.__primero is None: # ← comprobar siempre
return None # o raise o lo que corresponda
# ... resto del método
# ERROR 3 — olvidar el caso especial de eliminar el primero
# El patrón anterior/actual empieza en el segundo nodo
# Si el elemento a eliminar ES el primero necesitas manejarlo aparte
if self.__primero.valor == buscado:
self.__primero = self.__primero.siguiente # caso especial
return
# ... el resto del código con anterior/actual
# ERROR 4 — avanzar anterior cuando eliminas un nodo
# Al eliminar, anterior NO avanza — sigue apuntando al mismo nodo
if duplicado:
anterior.siguiente = actual.siguiente # eliminar
actual = actual.siguiente # avanzar solo actual
# NO hacer: anterior = actual
else:
anterior = actual # avanzar ambos
actual = actual.siguiente # solo cuando NO eliminas
# ERROR 5 — recorrer una lista con ciclo sin detectarlo
# Un while actual is not None en una lista con ciclo → bucle infinito
# Detectar ciclo primero con el algoritmo de Floyd si no estás seguro
Sigue aprendiendoTodos los artículos de Python¿Te ha servido este artículo? Así puedes apoyar SergioLearns →
