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.

    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:

        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.

        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:

    • 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:

    50
    

    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:

    18
    5
    10
    50
    

    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:

    18
    5
    10
    50
    29
    39
    49 
    

    Insertemos un elemento despu茅s de 50.

    new_linked_list.insert_after_item(50, 65)
    

    Ahora la lista deber铆a verse as铆:

    18
    5
    10
    50
    65
    29
    39
    49 
    

    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:

    18
    5
    10
    50
    65
    100
    29
    39
    49 
    

    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铆:

    5
    10
    50
    65
    100
    29
    39
    49 
    

    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:

    5
    10
    50
    65 
    100 
    29
    39
    

    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:

    new_linked_list.reverse_linked_list()
    

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

    39
    29
    100
    50
    10
    5 
    

    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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *