Crear una lista doblemente enlazada en Python

Este artículo demostrará la creación de una lista doblemente vinculada con el lenguaje de programación Python.

Crear una lista doblemente enlazada en Python

Una lista doblemente enlazada se refiere a una estructura de datos enlazados que consta de un conjunto de registros enlazados secuencialmente denominado nodo. Cada nodo contiene un puntero anterior, un puntero siguiente y un campo de datos.

Los punteros anterior y siguiente apuntan al nodo anterior y siguiente. El puntero anterior en el primer nodo y el siguiente puntero en el último nodo apuntan a Ninguno.

Podemos insertar un nuevo nodo antes y después de un nodo dado en la lista doblemente enlazada. Además, podemos recorrer la lista doblemente enlazada tanto hacia adelante como hacia atrás.

Sin embargo, cada nodo de lista doblemente vinculado requiere espacio adicional para un puntero anterior.

Una clase de nodo se crea de la siguiente manera. Los punteros y los valores de datos son Ninguno de forma predeterminada.

class Node:
    def __init__(self, next=None, previous=None, data=None):
        self.next = next
        self.previous = previous
        self.data = data

Luego, se crea la clase utilizada para la lista doblemente enlazada. El self.head indica el encabezado de la lista y es Ninguno al principio.

Usaremos la función add_to_end para agregar un nuevo nodo al final de la lista doblemente enlazada. Primero, creamos una instancia de la clase Node con la variable new_node.

Dado que el nuevo_nodo será el último valor de la lista, establecemos su siguiente puntero en Ninguno. Definimos la variable last para encontrar el nodo al que añadiremos el new_node.

Primero, esta variable es el encabezado de la lista doblemente enlazada (para el primer nodo agregado, este encabezado será Ninguno).

Comprobamos si el self.head es None en el bloque if. Si es así, no hay nodos en la lista y ahora el encabezado de la lista será el nodo recién agregado.

En el bloque while, comprobamos el puntero siguiente de la variable última para encontrar el último valor de la lista. Sustituimos la variable last por last.next hasta obtener Ninguno.

Terminamos la lista cuando encontramos el nodo cuyo valor last.next es Ninguno.

Configuramos el puntero siguiente del valor del nodo último que encontramos para que apunte al nuevo_nodo. Finalmente, colocamos el puntero anterior de la variable nuevo_nodo en la variable última.

Así, el nodo nuevo_nodo se añade al final de la lista doblemente enlazada.

Vea el código a continuación.

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while last.next is not None:
            last = last.next

        last.next = new_node
        new_node.previous = last

Podemos usar la función add_to_beginning para agregar un nodo al comienzo de la lista doblemente enlazada. Este proceso es más sencillo.

Primero, establecemos el puntero siguiente de la variable nuevo_nodo en self.head y el puntero anterior en Ninguno. Así que el valor principal, el primer valor de la lista anterior, se convierte en el siguiente valor donde apunta nuevo_nodo.

En el bloque if, comprobamos si el valor self.head es Ninguno si la lista está vacía. Si este valor está definido o hay un nodo correspondiente a la cabeza, cambiamos el puntero anterior de este nodo a nuevo_nodo.

Finalmente, cambiamos self.head a new_node. Así, el nuevo_nodo se añade al principio de la lista doblemente enlazada.

Vea la demostración del código a continuación.

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):
        # previous function
        pass

    def add_to_beginning(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

En el siguiente ejemplo, la variable doubly_linked_list se crea primero. Esta variable es una instancia de la clase DoublyLinkedList.

Luego añadimos 1 y 3 al final de la lista y 5 al principio, respectivamente. El estado final de la lista es 5 -> 1 -> 3 -> Ninguno.

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)