Listas Ligadas

Estructura de Nodos, lista ligada con agregar/obtener/insertar, e iteración con __iter__ y __next__.

Creado por

SebastianZ28

Valoración0 votos

-.-

data_object

El Nodo

Un nodo es la unidad base de las estructuras de datos. Contiene dos atributos:

valor — el dato almacenado en el nodo
siguiente — una referencia al siguiente nodo en la secuencia (o None si es el último)

Un conjunto de nodos conectados mediante referencias forma una lista ligada: una cadena donde cada nodo apunta al siguiente.

python

class Nodo:
    def __init__(self, valor=None):
        self.valor = valor
        self.siguiente = None  # ningún sucesor al crearse
 
    def __repr__(self):
        return f'Nodo[{self.valor}]'
 
# Crear nodos y enlazarlos manualmente
n1 = Nodo(10)
n2 = Nodo(20)
n3 = Nodo(30)
 
n1.siguiente = n2   # 10 → 20
n2.siguiente = n3   # 20 → 30
# n3.siguiente = None (ya por defecto)
 
print(n1)                    # Nodo[10]
print(n1.siguiente)          # Nodo[20]
print(n1.siguiente.siguiente) # Nodo[30]

Cargando Quiz...

hub

Lista Ligada: agregar y obtener

La ListaLigada mantiene solo dos referencias:

cabeza — el primer nodo de la lista
cola — el último nodo (facilita el agregar eficiente al final)

agregar(valor) crea un nodo y lo enlaza al final. Si la lista está vacía, el nuevo nodo es tanto cabeza como cola.

obtener(posicion) recorre la lista desde la cabeza siguiendo los siguiente, hasta llegar a la posición pedida. No hay acceso por índice directo — hay que caminar nodo a nodo.

python

class ListaLigada:
    def __init__(self):
        self.cabeza = None
        self.cola = None
        self.largo = 0
 
    def agregar(self, valor):
        nuevo = Nodo(valor)
        if self.cabeza is None:        # lista vacía
            self.cabeza = nuevo

tune

Insertar en posición arbitraria

insertar(valor, posicion) agrega un nodo nuevo en la posición indicada. La clave está en actualizar los punteros en el orden correcto para no perder referencias:

Llegar al nodo predecesor (el que quedará antes del nuevo)
Asignar nodo_nuevo.siguiente = predecesor.siguiente (primero)
Asignar predecesor.siguiente = nodo_nuevo (después)

Caso especial: insertar en posición 0 (nueva cabeza) — no hay predecesor, se actualiza directamente self.cabeza.

python

def insertar(self, valor, posicion):
    if posicion < 0:
        return None
    nodo_nuevo = Nodo(valor)
    nodo_actual = self.cabeza
 
    # Caso especial: insertar como nueva cabeza
    if posicion == 0:
        nodo_nuevo.siguiente = self.cabeza
        self.cabeza = nodo_nuevo
        if nodo_nuevo.siguiente is None:  # lista estaba vacía

code

Hacer la lista iterable

Para poder usar for nodo in lista_ligada:, la lista debe ser iterable. Aplicando el patrón iterable/iterador:

IteradorListaLigada: recibe la cabeza y avanza usando .siguiente en cada __next__()
IterableListaLigada: hereda de ListaLigada y sobreescribe __iter__() para retornar un nuevo iterador

python

class IteradorListaLigada:
    def __init__(self, cabeza):
        self.nodo_actual = cabeza
 
    def __iter__(self):
        return self
 
    def __next__(self):
        if self.nodo_actual is None:
            raise StopIteration('Llegamos al final')
        nodo = self.nodo_actual