Las listas enlazadas simples almacenan datos en nodos conectados por referencias. Son útiles cuando necesitas insertar o eliminar elementos eficientemente.

En este artículo, aprenderás cómo implementar una lista enlazada simple en Python, incluyendo sus operaciones y características principales.

Puedes encontrar el código Python de este artículo en el repositorio de ejemplos de Python Scouts. ¡Te agradeceríamos mucho si nos dejas una estrella (⭐) en el repositorio!

Contenidos

¿Qué es una lista enlazada simple?

Una lista enlazada es una colección lineal de datos donde cada elemento se almacena en un nodo independiente. Cada nodo almacena dos piezas de información: un dato y una referencia al siguiente nodo de la lista, habitualmente llamada .next.

Las características fundamentales de una lista enlazada simple incluyen las siguientes:

  • Nodos enlazados: Cada nodo contiene un dato y un puntero al siguiente nodo.
  • Sin memoria contigua: Los nodos no ocupan posiciones consecutivas en memoria, sino que se enlazan formando una cadena.
  • Inserción y eliminación eficientes: Añadir o quitar nodos no requiere reorganizar los demás elementos.
  • Acceso secuencial: Para llegar a un nodo, debes recorrer la lista desde el principio.

En Python, las listas enlazadas no están integradas como una estructura de datos primitiva. Sin embargo, puedes implementarlas usando clases para representar los nodos y la propia lista.

Operaciones comunes en una lista enlazada simple

A continuación, un resumen de las operaciones que soportará tu lista enlazada:

Operación Descripción
llist = LinkedList() Construye una lista enlazada vacía.
llist = LinkedList(iterable) Construye una lista enlazada con elementos de iterable.
llist.append_left(value) Añade un nodo con value al inicio de la lista.
llist.append(value) Añade un nodo con value al final de la lista.
llist.insert(index, value) Inserta un nodo con value en la posición index.
llist.remove(value) Elimina el nodo que contiene value.
llist.reverse() Invierte la lista en su lugar.
len(llist) Devuelve el número de nodos en la lista.
for node in llist: ... Itera sobre los nodos de la lista.

Implementación de una lista enlazada simple en Python

A continuación encontrarás la implementación de la lista enlazada simple en Python:

Python - linked_list.py
from typing import Any, Iterable, Iterator, Optional

class Node:
    """Node of a linked list."""

    def __init__(self, data: Any) -> None:
        self.next: Optional["Node"] = None
        self.data = data

    def __repr__(self) -> str:
        return str(self.data)

class LinkedList:
    """Implement a singly linked list abstract data type."""

    def __init__(self, data: Optional[Iterable[Any]] = None, /) -> None:
        self.head: Optional[Node] = None
        self._length: int = 0
        if data is not None:
            data_as_list = list(data)
            if (length := len(data_as_list)) > 0:
                head, *rest = data_as_list
                self._length = length
                self.head = Node(data=head)
                node = self.head
                for value in rest:
                    node.next = Node(data=value)
                    node = node.next

    def append_left(self, value: Any) -> None:
        """Add a node holding value to the left end of the linked list."""
        node = Node(data=value)
        node.next = self.head
        self.head = node
        self._length += 1

    def append(self, value: Any) -> None:
        """Add a node holding value to the right end of the linked list."""
        node = Node(data=value)
        if self.head is None:
            self.head = node
        else:
            # Traverse the list to reach the last node
            for last_node in self:
                pass
            last_node.next = node
        self._length += 1

    def insert(self, index: int, value: Any) -> None:
        """Insert a node holding value at index."""
        if self.head is None or index == 0:
            self.append_left(value)
            return
        previous_node = self.head
        for i, current_node in enumerate(self):
            if i == index:
                node = Node(data=value)
                previous_node.next = node
                node.next = current_node
                self._length += 1
                return
            previous_node = current_node
        raise IndexError("index out of range")

    def remove(self, value: Any) -> None:
        """Remove the node holding value."""
        if self.head is None:
            return
        if self.head.data == value:
            self.head = self.head.next
            self._length -= 1
            return
        previous_node = self.head
        for current_node in self:
            if current_node.data == value:
                previous_node.next = current_node.next
                self._length -= 1
                return
            previous_node = current_node
        raise IndexError(f"{value} doesn't exist")

    def reverse(self) -> None:
        """Reverse the list in place."""
        if self.head is None:
            return
        previous: Optional[Node] = None
        current: Optional[Node] = self.head
        next_node: Optional[Node] = current.next
        while current:
            current.next = previous
            previous = current
            current = next_node
            if next_node:
                next_node = next_node.next
        self.head = previous

    def __iter__(self) -> Iterator:
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def __repr__(self) -> str:
        data = [node.data for node in self]
        return f"{self.__class__.__name__}({data})"

    def __str__(self) -> str:
        data = [str(node.data) for node in self]
        data.append("None")
        if len(data) == 1:
            return f"HEAD({data[0]})"
        return f"HEAD({data[0]}) -> " + " -> ".join(data[1:])

    def __len__(self) -> int:
        return self._length

La implementación consta de dos clases. La clase Node representa un nodo individual con un atributo .data para el dato y un atributo .next que apunta al siguiente nodo. La clase LinkedList gestiona la cadena de nodos a través de los atributos .head (referencia al primer nodo) y ._length (número total de nodos).

Los métodos principales te permiten ofrecer las siguientes funcionalidades:

  • .append_left(): añade un nodo al inicio de la lista, desplazando el nodo actual de la cabeza.
  • .append(): añade un nodo al final de la lista, recorriendo todos los nodos hasta llegar al último.
  • .insert(): inserta un nodo en una posición específica. Si la posición es 0 o la lista está vacía, delega en .append_left().
  • .remove(): elimina el primer nodo que contiene el valor indicado. Lanza IndexError si el valor no existe.
  • .reverse(): invierte el orden de los nodos en la lista, reasignando las referencias .next.

Los métodos especiales te permiten ofrecer las siguientes funcionalidades:

  • .__iter__(): permite iterar sobre los nodos de la lista recorriendo las referencias .next.
  • .__len__(): devuelve el número de nodos en la lista.
  • .__repr__(): devuelve una representación que muestra los datos como una lista.
  • .__str__(): devuelve una representación visual que muestra la dirección de los enlaces entre nodos.

Ejemplo de uso de la lista enlazada simple

En esta sección verás ejemplos prácticos de cómo crear y manipular instancias de tu clase LinkedList.

Inicialización

Para crear una LinkedList, puedes hacerlo sin argumentos o pasando una lista de datos:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList()
>>> llist
LinkedList([])

>>> llist = LinkedList([1, 2, 3])
>>> llist
LinkedList([1, 2, 3])
>>> print(llist)
HEAD(1) -> 2 -> 3 -> None

Añadir elementos

Puedes añadir elementos al inicio o al final de la lista:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([2, 3])

>>> llist.append_left(1)
>>> llist
LinkedList([1, 2, 3])

>>> llist.append(4)
>>> llist
LinkedList([1, 2, 3, 4])
>>> print(llist)
HEAD(1) -> 2 -> 3 -> 4 -> None

Insertar en una posición específica

El método .insert() permite colocar un nodo en una posición determinada:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 3])
>>> llist.insert(1, 2)
>>> llist
LinkedList([1, 2, 3])

Si el índice está fuera de rango, obtendrás un error:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 2])
>>> llist.insert(2, 3)
Traceback (most recent call last):
    ...
IndexError: index out of range

Eliminar elementos

El método .remove() elimina el primer nodo que contiene el valor indicado:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 2, 3])

>>> llist.remove(2)
>>> llist
LinkedList([1, 3])

>>> llist.remove(1)
>>> llist
LinkedList([3])

Si el valor no existe, obtendrás un error:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 2])
>>> llist.remove(99)
Traceback (most recent call last):
    ...
IndexError: 99 doesn't exist

Invertir la lista

El método .reverse() invierte el orden de los nodos en su lugar:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 2, 3])
>>> llist.reverse()
>>> llist
LinkedList([3, 2, 1])
>>> print(llist)
HEAD(3) -> 2 -> 1 -> None

Longitud e iteración

Puedes consultar la longitud de la lista e iterar sobre sus nodos:

Python REPL
>>> from linked_list import LinkedList

>>> llist = LinkedList([1, 2, 3])

>>> len(llist)
3

>>> for node in llist:
...     print(node)
...
1
2
3

Conclusión

Has aprendido cómo implementar una lista enlazada simple que proporciona operaciones esenciales como añadir, insertar, eliminar e invertir nodos.

Este conocimiento te sirve de base para comprender cómo funcionan las estructuras de datos que no dependen de memoria contigua y cuándo es preferible usarlas frente a arreglos o listas de Python.

Puedes encontrar el código Python de este artículo en el repositorio de ejemplos de Python Scouts. ¡Te agradeceríamos mucho si nos dejas una estrella (⭐) en el repositorio!