Introducción

Una lista enlazada (linked list) es una estructura de datos lineal donde cada nodo contiene un valor y una referencia al siguiente nodo. A diferencia de los arrays, las listas enlazadas permiten inserciones y eliminaciones O(1) en cualquier posición, pero el acceso aleatorio es O(n).

En muchos escenarios –por ejemplo, al generar una salida en orden inverso o al implementar algoritmos como undo en editores de texto– es necesario recorrer la lista desde el último elemento hasta el primero sin alterar la estructura original.

Conceptos básicos

• Lista simplemente enlazada (Singly Linked List): Cada nodo apunta solo al siguiente.
• Lista doblemente enlazada (Doubly Linked List): Cada nodo mantiene referencias al next y al prev, facilitando el recorrido inverso nativo.

El algoritmo de recorrido inverso que describiremos está pensado para listas simplemente enlazadas, ya que en listas doblemente enlazadas basta con seguir los punteros prev.

Algoritmos de recorrido inverso

def reverse_print_recursive(node):
    if node is None:
        return
    reverse_print_recursive(node.next)  # Llamada profunda
    print(node.data)                    # Se ejecuta al regresar

def reverse_print_stack(head):
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next
    while stack:
        node = stack.pop()
        print(node.data)

def reverse_print_inplace(head):
    # Paso 1: invertir la lista
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    # prev es la nueva cabeza (último nodo original)
    # Paso 2: imprimir y restaurar
    new_head = prev
    prev = None
    while new_head:
        print(new_head.data)
        nxt = new_head.next
        new_head.next = prev
        prev = new_head
        new_head = nxt
    # Al salir, la lista queda como estaba

def reverse_print_doubly(tail):
    current = tail
    while current:
        print(current.data)
        current = current.prev

Comparativa de complejidad y uso de recursos

Implementación completa de una lista simplemente enlazada y ejemplos de recorrido inverso

class Node:
    """Nodo de una lista simplemente enlazada."""
    __slots__ = ('data', 'next')
    def __init__(self, data, nxt=None):
        self.data = data
        self.next = nxt
class SinglyLinkedList:
    def __init__(self):
        self.head = None
    def append(self, value):
        """Añade un nodo al final (O(n))."""
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.data
            cur = cur.next
    # ---------- Recorrido inverso ----------
    def reverse_print_recursive(self):
        def _rec(node):
            if not node:
                return
            _rec(node.next)
            print(node.data)
        _rec(self.head)
    def reverse_print_stack(self):
        stack = []
        cur = self.head
        while cur:
            stack.append(cur)
            cur = cur.next
        while stack:
            print(stack.pop().data)
    def reverse_print_inplace(self):
        # Invertir temporalmente
        prev = None
        cur = self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        # prev es la nueva cabeza (último nodo original)
        new_head = prev
        # Imprimir y restaurar
        prev = None
        while new_head:
            print(new_head.data)
            nxt = new_head.next
            new_head.next = prev
            prev = new_head
            new_head = nxt
        # Restablecer la referencia original
        self.head = prev

Uso típico:

if __name__ == '__main__':
    ll = SinglyLinkedList()
    for i in range(1, 8):
        ll.append(i)
    print('Recorrido normal:', list(ll))
    print('\nRecorrido inverso (recursivo):')
    ll.reverse_print_recursive()
    print('\nRecorrido inverso (pila):')
    ll.reverse_print_stack()
    print('\nRecorrido inverso (in‑place):')
    ll.reverse_print_inplace()

Buenas prácticas y solución de problemas

• Validar la lista antes de imprimir: comprueba if head is None para evitar AttributeError.
• Control de profundidad recursiva: si la lista puede superar los 10 000 elementos, prefiere la pila explícita o el algoritmo in‑place.
• Uso de __slots__ en la clase Node reduce la huella de memoria en listas muy largas.
• Testing automatizado: escribe pruebas unitarias con unittest o pytest que comparen la salida de los tres métodos.

  def capture_output(func):
      from io import StringIO
      import sys
      old = sys.stdout
      sys.stdout = StringIO()
      func()
      out = sys.stdout.getvalue()
      sys.stdout = old
      return out.strip().split('\n')
  

• Seguridad: al invertir la lista temporalmente, asegúrate de que ningún otro hilo esté accediendo a la estructura simultáneamente; utiliza bloqueos (threading.Lock) si trabajas en entornos multihilo.

¿Por qué no usar un list de Python?

Una list ya permite acceso aleatorio O(1) y recorrido inverso con reversed(). Sin embargo, la lista enlazada sigue siendo útil cuando:

• Se requiere inserción/eliminación frecuente en la cabeza o en medio de la colección.
• Se trabaja con flujos de datos potencialmente infinitos (p. ej., listas de nodos creados bajo demanda).

En la práctica, para la mayoría de los casos de uso en Python, una list es la opción más simple y eficiente. El algoritmo de recorrido inverso de una lista enlazada se vuelve relevante cuando se hereda de una API que obliga a usar nodos o cuando se implementan estructuras de bajo nivel (p. ej., en C extensions).

Conclusión

El recorrido inverso de una lista simplemente enlazada puede abordarse de múltiples maneras, cada una con trade‑offs de complejidad temporal, consumo de memoria y robustez. La recursión es elegante pero limitada por la pila del intérprete; la pila explícita es segura para listas grandes; la inversión in‑place ahorra memoria pero requiere una fase de restauración cuidadosa; y la lista doblemente enlazada ofrece la solución más natural cuando el diseño lo permite.

Elige el algoritmo que mejor se alinee con tus requisitos de rendimiento, tamaño de datos y arquitectura de la aplicación. Implementa pruebas unitarias y, si trabajas en entornos concurrentes, protege la estructura con bloqueos para evitar condiciones de carrera.