ᐉ Lista doblemente enlazada con ejemplos de Python

Este es el tercer artículo de la serie de artículos sobre la implementación de listas vinculadas con Python. En la Parte 1 y la Parte 2 de la serie, estudiamos en detalle la lista enlazada única. En este artículo, comenzaremos nuestra discusión sobre la lista de enlaces dobles, que en realidad es una extensión de la lista de enlaces únicos.

En una lista vinculada única, cada node de la lista tiene dos componentes, el valor real del node y la referencia al siguiente node de la lista vinculada. En la lista doblemente enlazada, cada node tiene tres componentes: el valor del node, la referencia al node anterior y la referencia al siguiente node. Para el node de inicio de la lista doblemente enlazada, la referencia al node anterior es nula. De manera similar, para el último node de la lista doblemente enlazada, la referencia al siguiente node es nula.

Pros y contras de una lista doblemente vinculada

A continuación se muestran algunos de los pros y los contras de una lista doblemente vinculada:

Pros

A diferencia de una única lista enlazada, la lista doblemente enlazada se puede recorrer y buscar en ambas direcciones. La referencia al siguiente node ayuda a atravesar el node en la dirección de avance, mientras que las referencias a los nodes anteriores permiten el cruce en la dirección de retroceso.
Las operaciones básicas como la inserción y el borrado son más fáciles de implementar en las listas doblemente enlazadas ya que, a diferencia de las listas enlazadas simples, no necesitamos atravesar el node predecesor y almacenar su referencia. Más bien, en una lista doblemente enlazada, la referencia del node predecesor se puede recuperar del node que queremos eliminar.

Contras

Uno de los principales inconvenientes de la lista doblemente enlazada es que necesita más espacio de memoria para almacenar una referencia adicional para cada node.
Es necesario realizar algunos pasos adicionales para realizar operaciones de inserción y eliminación.

Implementando la lista doblemente vinculada con Python

En esta sección, veremos cómo podemos crear una lista doblemente enlazada muy simple en Python. Si ha leído la Parte 1 y la Parte 2 de esta serie de artículos, el código debería ser bastante sencillo.

Como siempre, primero creemos una clase para el único node de la lista. Agrega el siguiente código a tu archivo:

class Node:
    def __init__(self, data):
        self.item = data
        self.nref = None
        self.pref = None

Se puede ver en el código anterior, creamos una Nodeclase con tres variables miembro: item, nref, y pref. La itemvariable almacenará los datos reales del node. El nrefalmacena la referencia al siguiente node, mientras que prefalmacena la referencia al node anterior en la lista doblemente enlazada.

A continuación, necesitamos crear la DoublyLinkedListclase, que contiene diferentes funciones relacionadas con listas doblemente enlazadas. Agrega el siguiente código:

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

A lo largo de este artículo, seguiremos agregando funciones a esta clase.

Insertar elementos en una lista doblemente vinculada

En esta sección, veremos las diferentes formas de insertar elementos en una lista doblemente enlazada.

Insertar elementos en una lista vacía

La forma más sencilla de insertar un elemento en una lista doblemente enlazada es insertar un elemento en la lista vacía. La siguiente secuencia de comandos inserta un elemento al comienzo de la lista doblemente enlazada:

 def insert_in_emptylist(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("list is not empty")

En el script anterior, definimos un método insert_in_emptylist(). El método primero verifica si la self.start_nodevariable lo es Noneo no. Si la variable lo es None, significa que la lista está realmente vacía. A continuación, se crea un nuevo node y su valor se inicializa mediante el valor pasado como parámetro al dataparámetro de la insert_in_emptylist()función. Finalmente, el valor de la self.start_nodevariable se establece en el nuevo node. En caso de que la lista no esté vacía, simplemente se muestra un mensaje al usuario de que la lista no está vacía.

Te puede interesar:Ordenar y fusionar una lista vinculada única

Agregue el insert_in_emptylist()método a la DoublyLinkedListclase que creó anteriormente.

Insertar elementos al principio

Para insertar un elemento al principio de la lista doblemente enlazada, primero tenemos que comprobar si la lista está vacía o no. Si la lista está vacía, simplemente podemos usar la lógica definida en el insert_in_emptylist()para insertar el elemento ya que en una lista vacía, el primer elemento siempre está al principio.

De lo contrario, si la lista no está vacía, debemos realizar tres operaciones:

Para el nuevo node, la referencia al siguiente node se establecerá en self.start_node.
Para el, self.start_nodela referencia al node anterior se establecerá en el node recién insertado.
Finalmente, self.start_nodese convertirá en el node recién insertado.

La siguiente secuencia de comandos inserta un elemento al comienzo de la lista doblemente enlazada:

    def insert_at_start(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            print("node inserted")
            return
        new_node = Node(data)
        new_node.nref = self.start_node
        self.start_node.pref = new_node
        self.start_node = new_node

Agregue el insert_at_start()método a la DoublyLinkedListclase que creó anteriormente.

Insertar elementos al final

Insertar un elemento al final de la lista doblemente enlazada es algo similar a insertar un elemento al principio. Al principio, debemos verificar si la lista está vacía. Si la lista está vacía, simplemente podemos usar el insert_in_emptylist()método para insertar el elemento. Si la lista ya contiene algún elemento, recorremos la lista hasta que la referencia al siguiente node se convierte en None. Cuando la siguiente referencia de node se convierte Noneen, significa que el node actual es el último node.

La referencia anterior para el nuevo node se establece en el último node y la siguiente referencia para el último node se establece en el node recién insertado. El script para insertar un elemento en el último node es el siguiente:

    def insert_at_end(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        new_node = Node(data)
        n.nref = new_node
        new_node.pref = n

Agregue el insert_at_end()método a la DoublyLinkedListclase que creó anteriormente.

Insertar artículo después de otro artículo

Para insertar un elemento después de otro elemento, primero verificamos si la lista está vacía o no. Si la lista está realmente vacía, simplemente mostramos el mensaje de que la «lista está vacía».

De lo contrario, iteramos a través de todos los nodes en la lista doblemente vinculada. En caso de que no se encuentre el node después del cual queremos insertar el nuevo node, mostramos el mensaje al usuario de que el elemento no se encuentra. De lo contrario, si se encuentra el node, se selecciona y realizamos cuatro operaciones:

Establezca la referencia anterior del node recién insertado en el node seleccionado.
Establezca la siguiente referencia del node recién insertado en la siguiente referencia del seleccionado.
Si el node seleccionado no es el último node, establezca la referencia anterior del siguiente node después del node seleccionado en el node recién agregado.
Finalmente, establezca la siguiente referencia del node seleccionado al node recién insertado.

El script para insertar un elemento después de otro es el siguiente:

Te puede interesar:Pilas y colas en Python

    def insert_after_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.pref = n
                new_node.nref = n.nref
                if n.nref is not None:
                    n.nref.prev = new_node
                n.nref = new_node

Agregue el insert_after_item()método a la DoublyLinkedListclase que creó anteriormente.

Insertar artículo antes que otro artículo

Para insertar un elemento antes que otro elemento, primero verificamos si la lista está vacía o no. Si la lista está realmente vacía, simplemente mostramos el mensaje de que la «lista está vacía».

De lo contrario, iteramos a través de todos los nodes en la lista doblemente vinculada. En caso de que no se encuentre el node antes del cual queremos insertar el nuevo node, mostramos el mensaje al usuario de que no se encuentra el elemento. De lo contrario, si se encuentra el node, se selecciona y realizamos cuatro operaciones:

Establezca la siguiente referencia del node recién insertado en el node seleccionado.
Establece la referencia anterior del node recién insertado a la referencia anterior del seleccionado.
Establezca la siguiente referencia del node anterior al node seleccionado, al node recién agregado.
Finalmente, establezca la referencia anterior del node seleccionado al node recién insertado.

El script para agregar un elemento antes de otro elemento en una lista doblemente enlazada es el siguiente:

    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.nref = n
                new_node.pref = n.pref
                if n.pref is not None:
                    n.pref.nref = new_node
                n.pref = new_node

Agregue el insert_before_item()método a la DoublyLinkedListclase que creó anteriormente.

Atravesando una lista doblemente enlazada

Recorrer una lista doblemente vinculada es muy similar a recorrer una única lista vinculada. El guión es el siguiente:

    def traverse_list(self):
        if self.start_node is None:
            print("List has no element")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.item , " ")
                n = n.nref

Agregue el traverse_list()método a la DoublyLinkedListclase que creó anteriormente.

Eliminar elementos de una lista doblemente vinculada

Al igual que la inserción, puede haber varias formas de eliminar elementos de una lista doblemente enlazada. En esta sección, repasaremos algunos de ellos.

Eliminar elementos desde el principio

La forma más sencilla de eliminar un elemento de una lista doblemente enlazada es desde el principio. Para hacerlo, todo lo que tiene que hacer es establecer el valor del node de inicio en el siguiente node y luego establecer la referencia anterior del node de inicio en None. Sin embargo, antes de hacerlo, debemos realizar dos comprobaciones. Primero, necesitamos ver si la lista está vacía. Y luego tenemos que ver si la lista contiene solo un elemento o no. Si la lista contiene solo un elemento, simplemente podemos establecer el node de inicio en None. El siguiente script se puede utilizar para eliminar elementos del inicio de la lista doblemente enlazada.

   def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        self.start_node = self.start_node.nref
        self.start_prev = None;

Agregue el delete_at_start()método a la DoublyLinkedListclase que creó anteriormente.

Eliminar elementos del final

Para eliminar el elemento del final, nuevamente verificamos si la lista está vacía o si la lista contiene un solo elemento. Si la lista contiene un solo elemento, todo lo que tenemos que hacer es establecer el node de inicio en None. Si la lista tiene más de un elemento, iteramos a través de la lista hasta que se alcanza el último node. Una vez que llegamos al último node, establecemos la siguiente referencia del node anterior al último node, al Noneque en realidad elimina el último node. El siguiente script se puede utilizar para eliminar el elemento del final.

Te puede interesar:Automatización de la gestión de AWS EC2 con Python y Boto3

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

Agregue el delete_at_end()método a la DoublyLinkedListclase que creó anteriormente.

Eliminar elementos por valor

Eliminar un elemento por valor es la más complicada de todas las funciones de eliminación en listas doblemente vinculadas, ya que se deben manejar varios casos para eliminar un elemento por valor. Primero veamos cómo se ve la función y luego veremos la explicación de la pieza de código individual.

    def delete_element_by_value(self, x):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return 

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

En el script anterior creamos una delete_element_by_value()función que toma el valor del node como parámetro y borra ese node. Al comienzo de la función, verificamos si la lista está vacía o no. Si la lista está vacía, simplemente le mostramos al usuario que la lista está vacía.

Esta lógica se implementa en el siguiente código:

        if self.start_node is None:
            print("The list has no element to delete")
            return

A continuación, verificamos si la lista tiene un solo elemento y ese elemento es realmente el elemento que queremos eliminar. Si el único elemento es el que queremos eliminar, simplemente establecemos self.start_nodeen, lo Noneque significa que la lista ahora no tendrá ningún elemento. Si solo hay un elemento y ese no es el elemento que queremos eliminar, simplemente mostraremos el mensaje de que no se encuentra el elemento a eliminar.

El siguiente código implementa esta lógica:

        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return

A continuación, manejamos el caso en el que la lista tiene más de un elemento, pero el elemento a eliminar es el primer elemento. En ese caso, simplemente ejecutamos la lógica que escribimos para el método delete_at_start(). El siguiente fragmento de código elimina un elemento desde el principio en el caso de varios elementos:

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

Finalmente, si la lista contiene varios elementos y el elemento a eliminar no es el primer elemento, recorremos todos los elementos de la lista excepto el último y vemos si alguno de los nodes tiene el valor que coincide con el valor que se eliminará. Si se encuentra el node, realizamos las siguientes dos operaciones:

Establezca el valor de la siguiente referencia del node anterior a la siguiente referencia del node que se eliminará.
Establezca el valor anterior del siguiente node a la referencia anterior del node que se eliminará.

Finalmente, si el node a eliminar es el último node, se establece en la siguiente referencia del node anterior al último node None. El siguiente script implementa esta lógica:

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

Agregue el delete_element_by_value()método a la DoublyLinkedListclase que creó anteriormente.

Invertir una lista doblemente vinculada

Para revertir una lista doblemente enlazada, básicamente tienes que realizar las siguientes operaciones:

Te puede interesar:Introducción al módulo de colecciones de Python

La siguiente referencia del node de inicio debe establecerse como ninguna porque el primer node se convertirá en el último node de la lista invertida.
La referencia anterior del último node debe establecerse en Noneya que el último node se convertirá en el node anterior.
Las siguientes referencias de los nodes (excepto el primer y último node) en la lista original deben intercambiarse con las referencias anteriores.

El guión para invertir una lista doblemente enlazada es el siguiente:

    def reverse_linked_list(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        p = self.start_node
        q = p.nref
        p.nref = None
        p.pref = q
        while q is not None:
            q.pref = q.nref
            q.nref = p
            p = q
            q = q.pref
        self.start_node = p

Agregue el reverse_linked_list()método a la DoublyLinkedListclase que creó anteriormente.

Prueba de funciones de lista doblemente enlazadas

En esta sección, probaremos las funciones doblemente vinculadas que creamos en las secciones anteriores.

Primero creemos el objeto de la DoublyLinkedListclase. Ejecute el siguiente script:

new_linked_list = DoublyLinkedList()

Prueba de funciones de inserción

Probemos primero las funciones de inserción. Primero agregaremos elementos en la lista vacía. Ejecute el siguiente script:

new_linked_list.insert_in_emptylist(50)

Ahora, si recorre la lista, debería ver 50 como el único elemento en la lista como se muestra a continuación:

new_linked_list.traverse_list()

Salida:

Ahora agreguemos algunos elementos al principio. Ejecute el siguiente script:

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

Ahora, si recorre la lista, debería ver los siguientes elementos en la lista:

Para agregar los elementos al final, ejecute el siguiente script:

new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

Ahora, si recorre la lista doblemente vinculada, debería ver los siguientes elementos:

Te puede interesar:Administradores de contexto de Python

Insertemos un elemento después de 50.

new_linked_list.insert_after_item(50, 65)

Ahora la lista debería verse así:

Finalmente, agreguemos un elemento antes del artículo 29.

new_linked_list.insert_before_item(29, 100)

La lista en este momento debe contener los siguientes elementos:

Prueba de funciones de eliminación

Probemos ahora las funciones de eliminación en los elementos que insertamos en las últimas secciones. Primero eliminemos un elemento desde el principio.

new_linked_list.delete_at_start()

El elemento 18 se eliminará y la lista se verá así:

De manera similar, la siguiente secuencia de comandos elimina el elemento del final de la lista doblemente vinculada:

new_linked_list.delete_at_end()

Si recorre la lista ahora, se devolverán los siguientes elementos:

Finalmente, también puede eliminar los elementos por valor usando la delete_element_by_value()función como se muestra a continuación:

new_linked_list.delete_element_by_value(65)

Si recorre la lista ahora, verá que el elemento 65 se eliminará de la lista.

Prueba de la función inversa

Finalmente, invirtamos la lista usando la reverse_linked_list()función. Ejecute el siguiente script:

Te puede interesar:Introducción a los iteradores de Python

new_linked_list.reverse_linked_list()

Ahora, si recorre la lista, verá la lista enlazada invertida:

Conclusión

La lista doblemente vinculada es extremadamente útil específicamente cuando tiene que realizar muchas inserciones y operaciones de eliminación. Los enlaces a los nodes anterior y siguiente facilitan la inserción y eliminación de nuevos elementos sin realizar un seguimiento de los nodes anteriores y siguientes.

En este artículo, vimos cómo se puede implementar una lista doblemente enlazada con Python. También vimos diferentes formas de realizar operaciones de inserción y eliminación en una lista doblemente vinculada. Finalmente, estudiamos cómo revertir una lista doblemente enlazada.

Rate this post