LinkedList en Python — 3 programas reales que consolidan la estructura
La LinkedList en Python práctica real es lo que toca ahora. En el artículo anterior vimos la teoría, qué es un nodo, cómo se enlazan, cómo insertar, recorrer y eliminar. Ahora construimos tres programas que van más allá de las operaciones básicas y que son exactamente el tipo de ejercicio que aparece en el segundo parcial de FP2. Cada operación viene con su diagrama para que puedas ver qué pasa en la cadena en cada paso.
Partimos de la clase LinkedList completa del artículo de teoría, la copiamos en un archivo linked_list.py y la importamos en cada programa.
Tabla de Contenidos
LinkedList en Python práctica — Programa 1: Buscar y contar elementos con condiciones
Este programa extiende la LinkedList con métodos de búsqueda que van más allá del simple contiene(). En FP2 se pide operaciones como contar cuántos elementos cumplen una condición, encontrar el máximo o el mínimo, o devolver todos los elementos que pasen un filtro.
La clave de todos estos métodos es siempre el mismo patrón de recorrido: actual = primero, avanzar mientras actual is not None. Lo que cambia es lo que haces con cada nodo.
from linked_list import LinkedList
class LinkedListBusqueda(LinkedList):
"""LinkedList extendida con operaciones de búsqueda."""
def contar(self, condicion=None):
"""
Cuenta los elementos que cumplen la condición.
Si no se pasa condición cuenta todos.
"""
contador = 0
for valor in self:
if condicion is None or condicion(valor):
contador += 1
return contador
def maximo(self):
"""Devuelve el valor máximo. Lanza ValueError si la lista está vacía."""
if self.es_vacia():
raise ValueError("La lista está vacía")
maximo = None
for valor in self:
if maximo is None or valor > maximo:
maximo = valor
return maximo
def minimo(self):
"""Devuelve el valor mínimo. Lanza ValueError si la lista está vacía."""
if self.es_vacia():
raise ValueError("La lista está vacía")
minimo = None
for valor in self:
if minimo is None or valor < minimo:
minimo = valor
return minimo
def filtrar(self, condicion):
"""Devuelve una nueva LinkedList con los elementos que cumplen la condición."""
resultado = LinkedListBusqueda()
for valor in self:
if condicion(valor):
resultado.insertar_detras(valor)
return resultado
def suma(self):
"""Devuelve la suma de todos los elementos."""
return sum(self)
def media(self):
"""Devuelve la media. Lanza ValueError si la lista está vacía."""
if self.es_vacia():
raise ValueError("La lista está vacía")
return self.suma() / len(self)
Ahora construimos la lista y probamos cada operación con su estado:
# Construimos la lista con estos valores
lista = LinkedListBusqueda()
for v in [15, 8, 42, 3, 27, 19, 8, 11, 35, 8]:
lista.insertar_detras(v)
print("Lista inicial:")
print(lista)
# → 15 → 8 → 42 → 3 → 27 → 19 → 8 → 11 → 35 → 8 → None
print(f"\nLongitud: {len(lista)}") # → 10
print(f"Suma: {lista.suma()}") # → 176
print(f"Media: {lista.media():.2f}") # → 17.60
print(f"Máximo: {lista.maximo()}") # → 42
print(f"Mínimo: {lista.minimo()}") # → 3
# Contar con condiciones
print(f"\nMayores que 15: {lista.contar(lambda x: x > 15)}") # → 4
print(f"Pares: {lista.contar(lambda x: x % 2 == 0)}") # → 4
print(f"Cuántos valen 8: {lista.contar(lambda x: x == 8)}") # → 3
print(f"Total elementos: {lista.contar()}") # → 10
# Filtrar — devuelve nueva lista
mayores = lista.filtrar(lambda x: x > 15)
print(f"\nMayores que 15:")
print(mayores)
# → 42 → 27 → 19 → 35 → None
pares = lista.filtrar(lambda x: x % 2 == 0)
print(f"\nSolo pares:")
print(pares)
# → 8 → 42 → 8 → 8 → None
# La lista original no se modifica
print(f"\nLista original intacta:")
print(lista)
# → 15 → 8 → 42 → 3 → 27 → 19 → 8 → 11 → 35 → 8 → None
Fíjate en que filtrar usa insertar_detras para construir la lista resultado, así mantiene el orden original. Si hubiera usado insertar_delante los elementos habrían salido en orden inverso.
LinkedList en Python práctica — Programa 2: Invertir una lista encadenada
Invertir una LinkedList es uno de los ejercicios clásicos de FP2 . La idea parece sencilla, dar la vuelta a la lista, pero la implementación requiere pensar con cuidado qué referencias cambias y en qué orden, porque si lo haces mal puedes perder parte de la lista.
Hay dos estrategias. La primera crea una lista nueva insertando cada elemento al principio, simple y fácil de visualizar. La segunda invierte la lista en su propio espacio, más eficiente pero más difícil de ver.
Estrategia 1 — Crear lista nueva (fácil de entender)
def invertir_nueva(self):
"""Devuelve una nueva LinkedList con los elementos en orden inverso."""
resultado = LinkedList()
for valor in self: # recorre de izquierda a derecha
resultado.insertar_delante(valor) # inserta al principio cada vez
return resultado
El truco es que insertar al principio invierte el orden automáticamente:
Lista original: 10 → 20 → 30 → None Recorremos: 10, 20, 30 Insertamos al principio cada uno: Después de insertar 10: 10 → None Después de insertar 20: 20 → 10 → None Después de insertar 30: 30 → 20 → 10 → None ← invertida
Estrategia 2 — Invertir en el mismo lugar (in-place)
Esta estrategia no crea una lista nueva, reusa los mismos nodos cambiando a quién apunta cada uno. Es la que más confunde y la que más vale entender con el diagrama.
La idea es recorrer la lista con tres variables: anterior, actual y siguiente. En cada paso invertimos el puntero de actual, en vez de apuntar hacia adelante, lo hacemos apuntar hacia atrás.
Estado inicial: anterior=None actual=[10] siguiente=[20] None ← [10] → [20] → [30] → None Paso 1: actual=[10], invertimos su puntero [10].siguiente = anterior (None) ┌─────────────────────────────────┐ │ None ← [10] [20] → [30] → None│ └─────────────────────────────────┘ Avanzamos: anterior=[10], actual=[20], siguiente=[30] Paso 2: actual=[20], invertimos su puntero [20].siguiente = anterior ([10]) ┌─────────────────────────────────┐ │ None ← [10] ← [20] [30] → None│ └─────────────────────────────────┘ Avanzamos: anterior=[20], actual=[30], siguiente=None Paso 3: actual=[30], invertimos su puntero [30].siguiente = anterior ([20]) ┌─────────────────────────────────┐ │ None ← [10] ← [20] ← [30] │ └─────────────────────────────────┘ actual=None → terminamos primero = anterior = [30] Resultado: [30] → [20] → [10] → None ✓
def invertir_inplace(self):
"""Invierte la lista en el mismo lugar, sin crear una nueva."""
anterior = None
actual = self._LinkedList__primero # acceso al atributo privado
while actual is not None:
siguiente = actual.siguiente # guardamos el siguiente ANTES de modificar
actual.siguiente = anterior # invertimos el puntero
anterior = actual # avanzamos anterior
actual = siguiente # avanzamos actual
self._LinkedList__primero = anterior # el nuevo primero es el último original
Veamos ambas en acción:
lista = LinkedList()
for v in [10, 20, 30, 40, 50]:
lista.insertar_detras(v)
print("Lista original:")
print(lista)
# → 10 → 20 → 30 → 40 → 50 → None
# Estrategia 1 — nueva lista
invertida = lista.invertir_nueva()
print("\nInvertida (nueva lista):")
print(invertida)
# → 50 → 40 → 30 → 20 → 10 → None
print("\nOriginal intacta:")
print(lista)
# → 10 → 20 → 30 → 40 → 50 → None
# Estrategia 2 — in-place
lista.invertir_inplace()
print("\nLista después de invertir_inplace:")
print(lista)
# → 50 → 40 → 30 → 20 → 10 → None
# Casos especiales
lista_vacia = LinkedList()
lista_vacia.invertir_inplace()
print("\nLista vacía invertida:")
print(lista_vacia)
# → None
lista_un_elemento = LinkedList()
lista_un_elemento.insertar_delante(42)
lista_un_elemento.invertir_inplace()
print("\nLista de un elemento invertida:")
print(lista_un_elemento)
# → 42 → None
El error más común al implementar la inversión in-place es olvidar guardar siguiente antes de modificar actual.siguiente. Si modificas el puntero primero, pierdes la referencia al resto de la lista y no puedes avanzar.
# MAL — perdemos la lista actual.siguiente = anterior # ← ya no podemos llegar al siguiente nodo siguiente = actual.siguiente # ← esto ahora da anterior, no el siguiente real # BIEN — guardamos el siguiente ANTES de modificar siguiente = actual.siguiente # ← guardamos primero actual.siguiente = anterior # ← luego modificamos
LinkedList en Python práctica — Programa 3: Ordenar una LinkedList por inserción
La ordenación por inserción en una LinkedList es el algoritmo de ordenación más natural para esta estructura. La idea: recorres la lista de izquierda a derecha y, para cada elemento, lo insertas en la posición correcta dentro de la parte ya ordenada.
Hay dos implementaciones. La primera construye una lista nueva ordenada. La segunda ordena en el mismo lugar.
Implementación — construir lista ordenada nueva
Para cada valor de la lista original, lo insertamos en la posición correcta dentro de la lista resultado:
def insertar_ordenado(self, valor):
"""
Inserta el valor en la posición correcta manteniendo el orden ascendente.
Método auxiliar para la ordenación.
"""
nuevo = self.Nodo(valor)
# Caso 1 — lista vacía o valor menor que el primero
if self.__primero is None or valor <= self.__primero.valor:
nuevo.siguiente = self.__primero
self.__primero = nuevo
self.__longitud += 1
return
# Caso 2 — buscar la posición correcta
actual = self.__primero
while actual.siguiente is not None and actual.siguiente.valor < valor:
actual = actual.siguiente
# Insertar después de actual
nuevo.siguiente = actual.siguiente
actual.siguiente = nuevo
self.__longitud += 1
def ordenar(self):
"""Devuelve una nueva LinkedList con los elementos ordenados."""
resultado = LinkedList()
for valor in self:
resultado.insertar_ordenado(valor)
return resultado
Veamos cómo funciona el insertar_ordenado paso a paso con la lista [3, 1, 4, 1, 5]:
Insertamos 3: [] → insertar 3 → lista vacía, es el primero 3 → None Insertamos 1: 3 → None → insertar 1 1 < 3 → va antes del primero 1 → 3 → None Insertamos 4: 1 → 3 → None → insertar 4 4 > 1, 4 > 3, fin de lista → va al final 1 → 3 → 4 → None Insertamos 1: 1 → 3 → 4 → None → insertar 1 1 <= 1 → va antes del primero 1 → 1 → 3 → 4 → None Insertamos 5: 1 → 1 → 3 → 4 → None → insertar 5 5 > todos → va al final 1 → 1 → 3 → 4 → 5 → None ✓
lista = LinkedList()
for v in [15, 3, 42, 8, 27, 1, 19]:
lista.insertar_detras(v)
print("Lista original:")
print(lista)
# → 15 → 3 → 42 → 8 → 27 → 1 → 19 → None
ordenada = lista.ordenar()
print("\nLista ordenada:")
print(ordenada)
# → 1 → 3 → 8 → 15 → 19 → 27 → 42 → None
print("\nOriginal intacta:")
print(lista)
# → 15 → 3 → 42 → 8 → 27 → 1 → 19 → None
# Casos especiales
lista_vacia = LinkedList()
print(f"\nLista vacía ordenada: {lista_vacia.ordenar()}")
# → None
lista_un_elemento = LinkedList()
lista_un_elemento.insertar_delante(42)
print(f"Lista de un elemento ordenada: {lista_un_elemento.ordenar()}")
# → 42 → None
lista_iguales = LinkedList()
for v in [5, 5, 5, 5]:
lista_iguales.insertar_detras(v)
print(f"Lista de iguales ordenada: {lista_iguales.ordenar()}")
# → 5 → 5 → 5 → 5 → None
# Demostración completa con insertar_ordenado
print("\nInsertar_ordenado paso a paso:")
resultado = LinkedList()
for v in [15, 3, 42, 8, 27]:
resultado.insertar_ordenado(v)
print(f"Después de insertar {v:2d}: {resultado}")
Salida del paso a paso:
Después de insertar 15: 15 → None Después de insertar 3: 3 → 15 → None Después de insertar 42: 3 → 15 → 42 → None Después de insertar 8: 3 → 8 → 15 → 42 → None Después de insertar 27: 3 → 8 → 15 → 27 → 42 → None
El patrón que debes llevarte
De los tres programas hay tres patrones que se repiten en todos los ejercicios de FP2 con LinkedList:
# PATRÓN 1 — recorrido con acumulador
# Para contar, sumar, buscar máximo/mínimo
acumulador = valor_inicial
actual = primero
while actual is not None:
acumulador = operacion(acumulador, actual.valor)
actual = actual.siguiente
return acumulador
# PATRÓN 2 — tres variables para invertir
# Para cualquier operación que invierta punteros
anterior = None
actual = primero
while actual is not None:
siguiente = actual.siguiente # guardar ANTES de modificar
actual.siguiente = anterior # invertir
anterior = actual # avanzar
actual = siguiente # avanzar
primero = anterior
# PATRÓN 3 — inserción en posición correcta
# Para cualquier inserción que mantenga orden
actual = primero
while actual.siguiente is not None and condicion(actual.siguiente.valor):
actual = actual.siguiente
nuevo.siguiente = actual.siguiente # conectar al resto
actual.siguiente = nuevo # conectar al nuevo
Visualízalo con Python Tutor
La inversión in-place es donde Python Tutor más brilla para LinkedList, puedes ver exactamente cómo las flechas cambian de dirección en cada paso. Ve a pythontutor.com y pega:
class Nodo:
def __init__(self, valor, siguiente=None):
self.valor = valor
self.siguiente = siguiente
# Lista: 1 → 2 → 3 → None
n1 = Nodo(1)
n2 = Nodo(2)
n3 = Nodo(3)
n1.siguiente = n2
n2.siguiente = n3
primero = n1
anterior = None
actual = primero
while actual is not None:
siguiente = actual.siguiente
actual.siguiente = anterior
anterior = actual
actual = siguiente
primero = anterior # nuevo primero: n3
Ejecuta paso a paso y observa cómo en cada iteración una flecha cambia de dirección. Cuando el bucle termina todas las flechas apuntan hacia la izquierda en vez de hacia la derecha.
Resumen y siguiente paso
En este artículo practicaste la LinkedList con tres programas reales. El programa de búsqueda demuestra que el patrón de recorrido es siempre el mismo, lo que cambia es la lógica dentro del bucle. La inversión muestra el patrón de tres variables que aparece en muchos algoritmos de LinkedList. La ordenación por inserción demuestra cómo insertar en la posición correcta manteniendo el orden.
En el siguiente artículo encontrarás ejercicios propuestos con solución para practicar por tu cuenta.
Python LinkedList — 3 real programs that consolidate the structure
In the previous article we covered the theory. Now we build three programs that go beyond basic operations, exactly the kind of exercise that appears in FP2 exams. Each operation comes with its diagram so you can see what happens in the chain at each step.
Program 1 — Search and count with conditions
from linked_list import LinkedList
class SearchLinkedList(LinkedList):
def count(self, condition=None):
"""Count elements matching condition. Counts all if no condition."""
counter = 0
for value in self:
if condition is None or condition(value):
counter += 1
return counter
def maximum(self):
if self.is_empty():
raise ValueError("List is empty")
max_val = None
for value in self:
if max_val is None or value > max_val:
max_val = value
return max_val
def minimum(self):
if self.is_empty():
raise ValueError("List is empty")
min_val = None
for value in self:
if min_val is None or value < min_val:
min_val = value
return min_val
def filter(self, condition):
"""Returns new LinkedList with elements matching condition."""
result = SearchLinkedList()
for value in self:
if condition(value):
result.insert_back(value)
return result
def total(self):
return sum(self)
def average(self):
if self.is_empty():
raise ValueError("List is empty")
return self.total() / len(self)
lst = SearchLinkedList()
for v in [15, 8, 42, 3, 27, 19, 8, 11, 35, 8]:
lst.insert_back(v)
print(lst)
# → 15 → 8 → 42 → 3 → 27 → 19 → 8 → 11 → 35 → 8 → None
print(f"Sum: {lst.total()}") # → 176
print(f"Average: {lst.average():.2f}") # → 17.60
print(f"Max: {lst.maximum()}") # → 42
print(f"Min: {lst.minimum()}") # → 3
print(f"Greater than 15: {lst.count(lambda x: x > 15)}") # → 4
print(f"Even numbers: {lst.count(lambda x: x % 2 == 0)}")# → 4
print(f"Count of 8s: {lst.count(lambda x: x == 8)}") # → 3
greater = lst.filter(lambda x: x > 15)
print(f"Greater than 15: {greater}")
# → 42 → 27 → 19 → 35 → None
evens = lst.filter(lambda x: x % 2 == 0)
print(f"Even only: {evens}")
# → 8 → 42 → 8 → 8 → None
Program 2 — Reverse a linked list
Two strategies:
Strategy 1 — New list (easy to understand)
def reverse_new(self):
result = LinkedList()
for value in self:
result.insert_front(value) # insert at front reverses order
return result
Original: 10 → 20 → 30 → 40 → 50 → None Insert 10 at front: 10 → None Insert 20 at front: 20 → 10 → None Insert 30 at front: 30 → 20 → 10 → None Insert 40 at front: 40 → 30 → 20 → 10 → None Insert 50 at front: 50 → 40 → 30 → 20 → 10 → None ✓
Strategy 2 — In-place (more efficient)
Initial state: previous=None current=[10] next_node=[20] None ← [10] → [20] → [30] → None Step 1: reverse [10]'s pointer [10].next = None (previous) None ← [10] [20] → [30] → None Advance: previous=[10], current=[20], next_node=[30] Step 2: reverse [20]'s pointer [20].next = [10] (previous) None ← [10] ← [20] [30] → None Advance: previous=[20], current=[30], next_node=None Step 3: reverse [30]'s pointer [30].next = [20] (previous) None ← [10] ← [20] ← [30] current=None → done first = previous = [30] Result: 30 → 20 → 10 → None ✓
def reverse_inplace(self):
previous = None
current = self._LinkedList__first
while current is not None:
next_node = current.next_node # save BEFORE modifying
current.next_node = previous # reverse pointer
previous = current # advance
current = next_node # advance
self._LinkedList__first = previous
lst = LinkedList()
for v in [10, 20, 30, 40, 50]:
lst.insert_back(v)
print(lst) # → 10 → 20 → 30 → 40 → 50 → None
reversed_new = lst.reverse_new()
print(reversed_new) # → 50 → 40 → 30 → 20 → 10 → None
print(lst) # → 10 → 20 → 30 → 40 → 50 → None (unchanged)
lst.reverse_inplace()
print(lst) # → 50 → 40 → 30 → 20 → 10 → None
Most common mistake: modifying current.next_node before saving next_node, you lose the rest of the list.
# WRONG current.next_node = previous # ← pointer now lost next_node = current.next_node # ← this now gives previous, not the real next # RIGHT next_node = current.next_node # ← save first current.next_node = previous # ← then modify
Program 3 — Sort by insertion
def insert_sorted(self, value):
"""Insert value in correct position maintaining ascending order."""
new = self.Node(value)
if self._LinkedList__first is None or value <= self._LinkedList__first.value:
new.next_node = self._LinkedList__first
self._LinkedList__first = new
self._LinkedList__length += 1
return
current = self._LinkedList__first
while current.next_node is not None and current.next_node.value < value:
current = current.next_node
new.next_node = current.next_node
current.next_node = new
self._LinkedList__length += 1
def sort(self):
"""Returns new sorted LinkedList."""
result = LinkedList()
for value in self:
result.insert_sorted(value)
return result
Step-by-step with [15, 3, 42, 8, 27]:
After inserting 15: 15 → None After inserting 3: 3 → 15 → None After inserting 42: 3 → 15 → 42 → None After inserting 8: 3 → 8 → 15 → 42 → None After inserting 27: 3 → 8 → 15 → 27 → 42 → None
lst = LinkedList()
for v in [15, 3, 42, 8, 27, 1, 19]:
lst.insert_back(v)
print(lst) # → 15 → 3 → 42 → 8 → 27 → 1 → 19 → None
sorted_lst = lst.sort()
print(sorted_lst) # → 1 → 3 → 8 → 15 → 19 → 27 → 42 → None
print(lst) # → 15 → 3 → 42 → 8 → 27 → 1 → 19 → None (unchanged)
The three patterns to take away
# PATTERN 1 — traversal with accumulator
# For count, sum, max, min, filter
accumulator = initial_value
current = first
while current is not None:
accumulator = operation(accumulator, current.value)
current = current.next_node
# PATTERN 2 — three variables for reversing
previous = None
current = first
while current is not None:
next_node = current.next_node # save BEFORE modifying
current.next_node = previous # reverse
previous = current # advance
current = next_node # advance
first = previous
# PATTERN 3 — insert in correct position
current = first
while current.next_node is not None and condition(current.next_node.value):
current = current.next_node
new.next_node = current.next_node # connect to rest
current.next_node = new # connect new node
Un comentario