Las listas doblemente enlazadas conectan nodos en ambas direcciones, permitiendo recorrer la lista hacia adelante y hacia atrás de manera eficiente.

Verás cómo modelar esta estructura paso a paso, cómo mantener sincronizadas las referencias entre nodos vecinos y en qué situaciones puede resultarte más útil que una lista enlazada simple.

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 doblemente enlazada?

Una lista doblemente enlazada es una colección lineal de datos donde cada elemento se almacena en un nodo independiente. A diferencia de una lista enlazada simple, cada nodo almacena tres piezas de información: un dato, una referencia al siguiente nodo (.next) y una referencia al nodo anterior (.previous).

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

  • Doble enlace: Cada nodo tiene referencias tanto al siguiente como al anterior.
  • Cabeza y cola: La lista mantiene referencias al primer nodo (.head) y al último (.tail).
  • Recorrido bidireccional: Puedes recorrer la lista en ambas direcciones, hacia adelante y hacia atrás.
  • Inserción y eliminación eficientes: Igual que en la lista enlazada simple, no necesitas reorganizar los demás nodos.

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

Operaciones comunes en una lista doblemente enlazada

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

Operación Descripción
dllist = DoublyLinkedList() Construye una lista doblemente enlazada vacía.
dllist = DoublyLinkedList(iterable) Construye una lista doblemente enlazada con elementos de iterable.
dllist.append_left(value) Añade un nodo con value al inicio de la lista.
dllist.append(value) Añade un nodo con value al final de la lista.
dllist.insert(index, value) Inserta un nodo con value en la posición index.
dllist.remove(value) Elimina el nodo que contiene value.
len(dllist) Devuelve el número de nodos en la lista.
for node in dllist: ... Itera sobre los nodos hacia adelante.
for node in reversed(dllist): ... Itera sobre los nodos hacia atrás.

Implementación de una lista doblemente enlazada en Python

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

Python - doubly_linked_list.py
from typing import Any, Iterator, Optional, Sequence

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

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

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}(data={self.data})"

    def __eq__(self, other: "Node") -> bool:
        if other.__class__ is not self.__class__:
            raise TypeError("Node object expected")
        return self.data == other.data

class DoublyLinkedList:
    """Implement a doubly linked list abstract data type."""

    def __init__(self, iterable: Optional[Sequence[Any]] = None, /) -> None:
        self.head: Optional[Node] = None
        self.tail: Optional[Node] = None
        self._length: int = 0
        if iterable is not None and (length := len(iterable)) > 0:
            head, *rest = iterable
            self._length = length
            self.head = Node(data=head)
            current = self.head
            for value in rest:
                current.next = Node(data=value)
                previous = current
                current = current.next
                current.previous = previous
            self.tail = current

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

    def append(self, value: Any) -> None:
        """Add a node holding value to the right end of the list."""
        node = Node(data=value)
        if self.tail is not None:
            node.previous = self.tail
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self._length += 1

    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
            if self.head is not None:
                self.head.previous = None
            else:
                self.tail = None
            self._length -= 1
            return
        if self.tail.data == value:
            self.tail = self.tail.previous
            if self.tail is not None:
                self.tail.next = None
            self._length -= 1
            return
        previous_node = self.head
        for node in self:
            if node.data == value:
                next_node = node.next
                previous_node.next = next_node
                if next_node is not None:
                    next_node.previous = previous_node
                self._length -= 1
                return
            previous_node = node
        raise IndexError(f"{value} doesn't exist")

    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 in enumerate(self):
            if i == index:
                node = Node(data=value)
                previous_node.next = node
                node.next = current
                node.previous = previous_node
                current.previous = node
                self._length += 1
                return
            previous_node = current
        raise IndexError("index out of range")

    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 __iter__(self) -> Iterator:
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def __reversed__(self) -> Iterator:
        node = self.tail
        while node is not None:
            yield node
            node = node.previous

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

La implementación consta de dos clases. La clase Node representa un nodo individual con atributos .data, .next y .previous. La clase DoublyLinkedList gestiona la cadena de nodos a través de .head (primer nodo), .tail (último 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. Si la lista está vacía, el nuevo nodo se convierte tanto en cabeza como en cola.
  • .append(): añade un nodo al final de la lista. Si la lista está vacía, el nuevo nodo se convierte tanto en cabeza como en cola.
  • .insert(): inserta un nodo en una posición específica, actualizando las referencias .next y .previous de los nodos vecinos.
  • .remove(): elimina el primer nodo que contiene el valor indicado. Maneja correctamente la eliminación de la cabeza, la cola y nodos intermedios.

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

  • .__iter__(): permite iterar hacia adelante recorriendo las referencias .next desde la cabeza.
  • .__reversed__(): permite iterar hacia atrás recorriendo las referencias .previous desde la cola.
  • .__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 los dobles enlaces entre nodos con <->.

Ejemplo de uso de la lista doblemente enlazada

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

Inicialización

Para crear una DoublyLinkedList, puedes hacerlo sin argumentos o pasando una secuencia de datos:

Python REPL
>>> from doubly_linked_list import DoublyLinkedList

>>> dllist = DoublyLinkedList()
>>> dllist
DoublyLinkedList([])

>>> dllist = DoublyLinkedList([1, 2, 3])
>>> dllist
DoublyLinkedList([1, 2, 3])
>>> print(dllist)
HEAD(1) <-> 2 <-> 3 <-> None

Acceder a la cabeza y la cola

La lista mantiene referencias directas al primer y último nodo:

Python REPL
>>> from doubly_linked_list import DoublyLinkedList

>>> dllist = DoublyLinkedList([1, 2, 3])

>>> dllist.head
Node(data=1)
>>> dllist.tail
Node(data=3)

Añadir elementos

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

Python REPL
>>> from doubly_linked_list import DoublyLinkedList

>>> dllist = DoublyLinkedList([2, 3])

>>> dllist.append_left(1)
>>> dllist
DoublyLinkedList([1, 2, 3])

>>> dllist.append(4)
>>> dllist
DoublyLinkedList([1, 2, 3, 4])
>>> print(dllist)
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 doubly_linked_list import DoublyLinkedList

>>> dllist = DoublyLinkedList([1, 3])
>>> dllist.insert(1, 2)
>>> dllist
DoublyLinkedList([1, 2, 3])
>>> len(dllist)
3

Eliminar elementos

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

Python REPL
>>> dllist = DoublyLinkedList([1, 2, 3])

>>> dllist.remove(2)
>>> dllist
DoublyLinkedList([1, 3])

>>> dllist.remove(1)
>>> dllist
DoublyLinkedList([3])

>>> dllist.remove(3)
>>> dllist
DoublyLinkedList([])

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

Python REPL
>>> from doubly_linked_list import DoublyLinkedList

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

Longitud e iteración

Puedes consultar la longitud de la lista e iterar en ambas direcciones:

Python REPL
>>> from doubly_linked_list import DoublyLinkedList

>>> dllist = DoublyLinkedList([1, 2, 3])

>>> len(dllist)
3

>>> for node in dllist:
...     print(node)
...
Node(data=1)
Node(data=2)
Node(data=3)

>>> for node in reversed(dllist):
...     print(node)
...
Node(data=3)
Node(data=2)
Node(data=1)

Conclusión

Has aprendido cómo implementar una lista doblemente enlazada que proporciona enlaces bidireccionales y operaciones esenciales como añadir, insertar y eliminar nodos.

Este conocimiento te permite comprender las ventajas de las listas doblemente enlazadas frente a las listas enlazadas simples, especialmente cuando necesitas recorrer los datos en ambas direcciones o acceder eficientemente al último elemento.

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!