5 - Operaciones en listas simplemente enlazadas
Flujo general
Una lista simplemente enlazada en Python se apoya en referencias: cada nodo solo conoce a su sucesor mediante sig. Las operaciones esenciales son insertar, eliminar, buscar, recorrer e imprimir. A continuación se muestra cada una con ejemplos en Python.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.sig = None
class Lista:
def __init__(self):
self.cabeza = None
5.1 Insertar al inicio
Operación O(1): enlaza el nuevo nodo con la antigua cabeza y actualiza la referencia principal.
class Lista:
# ...
def insertar_inicio(self, valor):
nuevo = Nodo(valor)
nuevo.sig = self.cabeza
self.cabeza = nuevo
5.2 Insertar al final
Si no guardamos una referencia a la cola, se recorre hasta el último nodo para enlazar el nuevo.
class Lista:
# ...
def insertar_final(self, valor):
nuevo = Nodo(valor)
if self.cabeza is None:
self.cabeza = nuevo
return
reco = self.cabeza
while reco.sig:
reco = reco.sig
reco.sig = nuevo
5.3 Insertar en posicion especifica
Recorre hasta el nodo previo a la posición deseada y reacomoda los enlaces. Si la posición es 0 o la lista está vacía, reutiliza la inserción al inicio.
class Lista:
# ...
def insertar_en(self, posicion, valor):
if posicion <= 0 or self.cabeza is None:
return self.insertar_inicio(valor)
reco = self.cabeza
for _ in range(posicion - 1):
if reco is None:
return
reco = reco.sig
if reco is None:
return
nuevo = Nodo(valor)
nuevo.sig = reco.sig
reco.sig = nuevo
5.4 Eliminar primer nodo
Mueve la cabeza al segundo nodo y corta el enlace del primero.
class Lista:
# ...
def eliminar_primero(self):
if self.cabeza is None:
return None
victima = self.cabeza
self.cabeza = victima.sig
victima.sig = None
return victima.valor
5.5 Eliminar ultimo nodo
Recorre hasta el penúltimo nodo, corta el enlace y devuelve el valor eliminado.
class Lista:
# ...
def eliminar_ultimo(self):
if self.cabeza is None:
return None
if self.cabeza.sig is None:
valor = self.cabeza.valor
self.cabeza = None
return valor
reco = self.cabeza
while reco.sig and reco.sig.sig:
reco = reco.sig
valor = reco.sig.valor
reco.sig = None
return valor
5.6 Eliminar nodo especifico
Busca el nodo previo al que contiene el valor y reajusta el enlace. Si el valor está en cabeza, usa la operación anterior.
class Lista:
# ...
def eliminar_valor(self, valor):
if self.cabeza is None:
return False
if self.cabeza.valor == valor:
self.eliminar_primero()
return True
reco = self.cabeza
while reco.sig and reco.sig.valor != valor:
reco = reco.sig
if reco.sig is None:
return False
victima = reco.sig
reco.sig = victima.sig
victima.sig = None
return True
5.7 Buscar un elemento
Recorre secuencialmente y devuelve el nodo encontrado o None.
class Lista:
# ...
def buscar(self, valor):
reco = self.cabeza
while reco:
if reco.valor == valor:
return reco
reco = reco.sig
return None
5.8 Recorrer e imprimir
Imprime cada valor seguido de una flecha para depuración rápida.
class Lista:
# ...
def imprimir(self):
reco = self.cabeza
while reco:
print(reco.valor, end=" -> ")
reco = reco.sig
print("None")
5.9 Manejo de memoria y liberacion correcta
Aunque Python tiene recolector de basura, conviene romper referencias para liberar nodos cuanto antes.
class Lista:
# ...
def limpiar(self):
while self.cabeza:
siguiente = self.cabeza.sig
self.cabeza.sig = None
self.cabeza = siguiente
El método corta cada enlace y mueve la cabeza, dejando que el recolector libere los nodos sin referencias activas.
5.10 Codigo completo listo para ejecutar
Script auto contenido para practicar en consola con python listas_simple.py.
# listas_simple.py
class Nodo:
def __init__(self, valor):
self.valor = valor
self.sig = None
class Lista:
def __init__(self):
self.cabeza = None
def insertar_inicio(self, valor):
nuevo = Nodo(valor)
nuevo.sig = self.cabeza
self.cabeza = nuevo
def insertar_final(self, valor):
nuevo = Nodo(valor)
if self.cabeza is None:
self.cabeza = nuevo
return
reco = self.cabeza
while reco.sig:
reco = reco.sig
reco.sig = nuevo
def insertar_en(self, posicion, valor):
if posicion <= 0 or self.cabeza is None:
return self.insertar_inicio(valor)
reco = self.cabeza
for _ in range(posicion - 1):
if reco is None:
return
reco = reco.sig
if reco is None:
return
nuevo = Nodo(valor)
nuevo.sig = reco.sig
reco.sig = nuevo
def eliminar_primero(self):
if self.cabeza is None:
return None
victima = self.cabeza
self.cabeza = victima.sig
victima.sig = None
return victima.valor
def eliminar_ultimo(self):
if self.cabeza is None:
return None
if self.cabeza.sig is None:
valor = self.cabeza.valor
self.cabeza = None
return valor
reco = self.cabeza
while reco.sig and reco.sig.sig:
reco = reco.sig
valor = reco.sig.valor
reco.sig = None
return valor
def eliminar_valor(self, valor):
if self.cabeza is None:
return False
if self.cabeza.valor == valor:
self.eliminar_primero()
return True
reco = self.cabeza
while reco.sig and reco.sig.valor != valor:
reco = reco.sig
if reco.sig is None:
return False
victima = reco.sig
reco.sig = victima.sig
victima.sig = None
return True
def buscar(self, valor):
reco = self.cabeza
while reco:
if reco.valor == valor:
return reco
reco = reco.sig
return None
def imprimir(self):
reco = self.cabeza
while reco:
print(reco.valor, end=" -> ")
reco = reco.sig
print("None")
def limpiar(self):
while self.cabeza:
siguiente = self.cabeza.sig
self.cabeza.sig = None
self.cabeza = siguiente
def main():
lista = Lista()
lista.insertar_inicio(10)
lista.insertar_final(20)
lista.insertar_en(1, 15)
print("Lista despues de insertar 10, 20 y 15 en el medio:")
lista.imprimir()
lista.eliminar_valor(15)
lista.eliminar_ultimo()
print("Lista despues de eliminar 15 y el ultimo:")
lista.imprimir()
lista.limpiar()
if __name__ == "__main__":
main()
Copia el script, ejecútalo y experimenta agregando más operaciones para reforzar el flujo de referencias en listas simplemente enlazadas.