Listas enlazadas en Python: Guía completa y ejemplos prácticos

Aprende desde los conceptos básicos hasta las mejores prácticas para implementar, depurar y optimizar listas enlazadas (singly, doubly y circulares) usando Python 3.10+.

Índice

• Conceptos fundamentales
• Implementación paso a paso
• Operaciones comunes
• Complejidad y rendimiento
• Comparativa con list y deque
• Mejores prácticas y patrones de diseño
• Testing y depuración
• Casos de uso del mundo real
• Referencias y lecturas recomendadas

Conceptos fundamentales

Una lista enlazada es una estructura de datos lineal donde cada elemento (nodo) contiene un valor y una referencia (puntero) al siguiente nodo. A diferencia de los arrays, su tamaño es dinámico y la inserción/eliminación de nodos es O(1) una vez que se tiene una referencia al nodo objetivo.

Tipos de listas enlazadas

Implementación paso a paso

1️⃣ Nodo base con dataclass

Usar dataclasses simplifica la definición y aporta __repr__ automático.

from __future__ import annotations
from dataclasses import dataclass, field
from typing import Any, Optional
@dataclass
class Node:
    """Representa un nodo de una lista enlazada simple."""
    value: Any
    next: Optional[Node] = field(default=None, repr=False)

2️⃣ Clase SinglyLinkedList completa

Incluye métodos esenciales, anotaciones de tipo y manejo de errores explícitos.

class SinglyLinkedList:
    """Lista enlazada simple con API tipo Pythonic."""
    def __init__(self) -> None:
        self.head: Optional[Node] = None
        self._size: int = 0
    # --------------------------------------------------------------
    # Métodos de inspección
    # --------------------------------------------------------------
    def __len__(self) -> int:
        return self._size
    def is_empty(self) -> bool:
        return self._size == 0
    def __iter__(self):
        current = self.head
        while current:
            yield current.value
            current = current.next
    def __repr__(self) -> str:
        values = ', '.join(repr(v) for v in self)
        return f"SinglyLinkedList([{values}])"
    # --------------------------------------------------------------
    # Operaciones de inserción
    # --------------------------------------------------------------
    def prepend(self, value: Any) -> None:
        """Inserta al inicio (O(1))."""
        self.head = Node(value, next=self.head)
        self._size += 1
    def append(self, value: Any) -> None:
        """Inserta al final (O(n) en lista simple)."""
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = new_node
        self._size += 1
    def insert(self, index: int, value: Any) -> None:
        """Inserta en posición arbitraria (O(min(i, n‑i)))."""
        if not 0 <= index <= self._size:
            raise IndexError('Índice fuera de rango')
        if index == 0:
            self.prepend(value)
            return
        cur = self.head
        for _ in range(index - 1):
            cur = cur.next  # type: ignore[arg-type]
        cur.next = Node(value, next=cur.next)
        self._size += 1
    # --------------------------------------------------------------
    # Operaciones de eliminación
    # --------------------------------------------------------------
    def pop(self, index: int = -1) -> Any:
        """Elimina y devuelve el nodo en index (por defecto último)."""
        if self.is_empty():
            raise IndexError('pop de lista vacía')
        # Normalizar índices negativos
        if index < 0:
            index = self._size + index
        if not 0 <= index < self._size:
            raise IndexError('Índice fuera de rango')
        if index == 0:
            value = self.head.value  # type: ignore[assignment]
            self.head = self.head.next  # type: ignore[assignment]
        else:
            prev = self.head
            for _ in range(index - 1):
                prev = prev.next  # type: ignore[arg-type]
            target = prev.next  # type: ignore[arg-type]
            value = target.value
            prev.next = target.next
        self._size -= 1
        return value
    # --------------------------------------------------------------
    # Búsqueda y utilidades
    # --------------------------------------------------------------
    def find(self, value: Any) -> int:
        """Devuelve la posición del primer nodo con value o -1."""
        for i, v in enumerate(self):
            if v == value:
                return i
        return -1
    def reverse(self) -> None:
        """Invierte la lista in‑place (O(n))."""
        prev = None
        current = self.head
        while current:
            nxt = current.next
            current.next = prev
            prev = current
            current = nxt
        self.head = prev

3️⃣ Variante doblemente enlazada

El siguiente fragmento muestra sólo las diferencias clave respecto a la versión simple.

@dataclass
class DNode:
    value: Any
    prev: Optional[DNode] = field(default=None, repr=False)
    next: Optional[DNode] = field(default=None, repr=False)
class DoublyLinkedList:
    def __init__(self) -> None:
        self.head: Optional[DNode] = None
        self.tail: Optional[DNode] = None
        self._size = 0
    def prepend(self, value: Any) -> None:
        node = DNode(value, next=self.head)
        if self.head:
            self.head.prev = node
        else:               # lista vacía
            self.tail = node
        self.head = node
        self._size += 1
    def append(self, value: Any) -> None:
        node = DNode(value, prev=self.tail)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self._size += 1
    # Eliminación en O(1) cuando se conoce el nodo:
    def delete_node(self, node: DNode) -> None:
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._size -= 1

💡 Tip: Usa __slots__ en Node para reducir la sobrecarga de memoria cuando manejas millones de nodos.

Operaciones comunes y ejemplos de uso

>>> lst = SinglyLinkedList()
>>> lst.append(10)
>>> lst.append(20)
>>> lst.prepend(5)
>>> list(lst)
[5, 10, 20]
>>> len(lst)
3

>>> lst.insert(1, 7)       # [5, 7, 10, 20]
>>> lst.pop(2)              # elimina 10
20
>>> list(lst)
[5, 7, 20]

Operación de reversión

>>> lst.reverse()
>>> list(lst)
[20, 7, 5]

Búsqueda y manejo de errores

>>> lst.find(7)
1
>>> lst.find(99)
-1
>>> try:
...     lst.pop(10)
... except IndexError as e:
...     print(e)
Índice fuera de rango

Complejidad y rendimiento

Benchmark rápido (Python 3.11)

import timeit, random
def bench_append_linked(n=100_000):
    lst = SinglyLinkedList()
    for i in range(n):
        lst.append(i)
def bench_append_array(n=100_000):
    arr = []
    for i in range(n):
        arr.append(i)
print('Linked:', timeit.timeit(lambda: bench_append_linked(100_000), number=1))
print('Array :', timeit.timeit(lambda: bench_append_array(100_000), number=1))

En máquinas modernas, list.append suele ser 2‑3× más rápido gracias a la pre‑asignación de bloques de memoria, pero la diferencia se vuelve irrelevante cuando la aplicación necesita inserciones frecuentes al inicio.

Comparativa con list y collections.deque

• list: estructura basada en array dinámico. Ideal para acceso aleatorio y operaciones de “push‑back”. No permite inserciones O(1) al inicio sin copiar todo el array.
• deque (de collections): implementado como una lista doblemente enlazada de bloques. appendleft y popleft son O(1). Excelente para colas y pilas, pero carece de capacidad de indexado arbitrario sin recorrer.
• lista enlazada propia: mayor control sobre la estructura, útil para algoritmos de bajo nivel (p.ej., listas de adyacencia en grafos) y para demostrar conceptos en entrevistas técnicas.

¿Cuándo elegir cada una?

Mejores prácticas y patrones de diseño

1. Usa __slots__ en los nodos para reducir la huella de memoria:

   class Node:
       __slots__ = ('value', 'next')
       def __init__(self, value, next=None):
           self.value = value
           self.next = next
   

2. Mantén referencia al último nodo (tail) cuando necesites append frecuente; evita recorridos O(n).
3. Valida índices antes de operar. Levanta IndexError con mensajes claros para evitar bugs silenciosos.
4. Implementa iteradores y __repr__ para que la lista sea “Pythonic” y facilite depuración.
5. Separación de responsabilidades: la clase Node solo almacena datos; la lógica de la lista reside en una clase distinta (SRP – Single Responsibility Principle).
6. Documenta el algoritmo de reversión y cualquier operación que modifique enlaces; esto ayuda a evitar ciclos inesperados.
7. Considera el uso de generadores si sólo necesitas iterar sin necesidad de mantener la lista completa en memoria:

   def iter_values(self):
       current = self.head
       while current:
           yield current.value
           current = current.next
   

Testing, depuración y troubleshooting

Pruebas unitarias con pytest

import pytest
@pytest.fixture
def lista():
    lst = SinglyLinkedList()
    for i in range(5):
        lst.append(i)
    return lst
def test_prepend(lista):
    lista.prepend(99)
    assert lista.head.value == 99
    assert len(lista) == 6
def test_pop_last(lista):
    val = lista.pop()
    assert val == 4
    assert len(lista) == 4
    assert lista.find(4) == -1
def test_reverse(lista):
    lista.reverse()
    assert list(lista) == [4, 3, 2, 1, 0]

Depuración con pdb o breakpoint()

Inserta breakpoint() dentro de insert para inspeccionar los enlaces:

def insert(self, index, value):
    ...
    cur = self.head
    for _ in range(index - 1):
        cur = cur.next
    breakpoint()   # ← inspecciona cur.value y cur.next
    cur.next = Node(value, next=cur.next)

Problemas habituales y sus soluciones

• Ciclo infinito al imprimir: ocurre al crear una lista circular sin condición de salida. Solución: limitar la iteración a self._size o usar un visited set.
• Memory leak por referencias cíclicas: en versiones de CPython < 3.4 los ciclos de referencia con __del__ podían quedar sin recolectar. Usar weakref o asegurarse de que los nodos no tengan __del__ pesado.
• IndexError inesperado: verifica siempre 0 <= index <= self._size y normaliza índices negativos antes de la lógica.

Casos de uso del mundo real

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [SinglyLinkedList() for _ in range(vertices)]
    def add_edge(self, src, dst):
        self.adj[src].append(dst)
        self.adj[dst].append(src)   # grafo no dirigido
    def neighbours(self, v):
        return list(self.adj[v])

class RingBuffer:
    def __init__(self, size):
        self.size = size
        self.buffer = DoublyLinkedList()
        self.count = 0
    def push(self, value):
        if self.count == self.size:
            # elimina el nodo más antiguo (head)
            self.buffer.delete_node(self.buffer.head)   # O(1)
            self.count -= 1
        self.buffer.append(value)
        self.count += 1
    def get_all(self):
        return list(self.buffer)

3️⃣ Simulación de una lista de “undo/redo” en editores de texto

Almacena cada operación como nodo, permite retroceder y avanzar rápidamente usando los punteros prev y next de una lista doblemente enlazada.

Referencias y lecturas recomendadas

• Guido van Rossum & Python Software Foundation, Data Model – docs.python.org
• Mark Allen Weiss, Data Structures & Algorithm Analysis in Python, 2ª edición, 2022.
• Python Docs – collections.deque: link
• Real‑World Python – Implementing a Linked List in Python
• GitHub – Linked list implementation in CPython (C)