Lista doblemente enlazada con ejemplos de Python

Este es el tercer artículo de una serie de artículos sobre la implementación de listas enlazadas con Python. En la Parte 1 y la Parte 2 de la serie, estudiamos la lista enlazada única en...

Este es el tercero de una serie de artículos sobre la implementación de listas enlazadas con Python. En Parte 1 y [Parte 2](/ordenar-y-combinar-una-single-linked-list /) de la serie estudiamos la lista enlazada única en detalle. 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 la lista enlazada única, cada nodo de la lista tiene dos componentes, el valor real del nodo y la referencia al siguiente nodo en la lista enlazada. En la lista doblemente enlazada, cada nodo tiene tres componentes: el valor del nodo, la referencia al nodo anterior y la referencia al nodo siguiente. Para el nodo inicial de la lista doblemente enlazada, la referencia al nodo anterior es nula. De manera similar, para el último nodo de la lista doblemente enlazada, la referencia al siguiente nodo es nula.

Pros y contras de una lista doblemente enlazada

Los siguientes son algunos de los pros y los contras de una lista doblemente enlazada:

Ventajas

  • A diferencia de una lista enlazada única, la lista doblemente enlazada se puede recorrer y buscar en ambas direcciones. La referencia al siguiente nodo ayuda a atravesar el nodo en la dirección de avance, mientras que las referencias a los nodos anteriores permiten el recorrido en la dirección de retroceso.
  • Las operaciones básicas como la inserción y la eliminación 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 nodo predecesor y almacenar su referencia. Más bien, en una lista doblemente enlazada, la referencia del nodo predecesor se puede recuperar del nodo 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 nodo.
  • Se requieren algunos pasos adicionales para realizar las operaciones de inserción y eliminación.

Implementación de la lista doblemente enlazada con Python {#implementación de la lista doblemente enlazada con Python}

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

Como siempre, primero vamos a crear una clase para el único nodo de la lista. Agregue el siguiente código a su archivo:

1
2
3
4
5
class Node:
    def __init__(self, data):
        self.item = data
        self.nref = None
        self.pref = None

Puede ver en el código anterior, creamos una clase Node con tres variables miembro: item, nref y pref. La variable item almacenará los datos reales del nodo. nref almacena la referencia al siguiente nodo, mientras que pref almacena la referencia al nodo anterior en la lista doblemente enlazada.

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

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

A lo largo de este artículo seguiremos añadiendo funciones a esta clase.

Inserción de elementos en una lista doblemente enlazada

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

Inserción de 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. El siguiente script inserta un elemento al comienzo de la lista doblemente enlazada:

1
2
3
4
5
6
 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 variable self.start_node es Ninguna o no. Si la variable es Ninguno, significa que la lista está realmente vacía. A continuación, se crea un nuevo nodo y su valor se inicializa con el valor pasado como parámetro al parámetro data de la función insert_in_emptylist(). Finalmente, el valor de la variable self.start_node se establece en el nuevo nodo. 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 método insert_in_emptylist() a la clase DoublyLinkedList que creó anteriormente.

Inserción de elementos al inicio

Para insertar un elemento al principio de la lista doblemente enlazada, primero debemos verificar si la lista está vacía o no. Si la lista está vacía, simplemente podemos usar la lógica definida en 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:

  1. Para el nuevo nodo, la referencia al siguiente nodo se establecerá en self.start_node.
  2. Para self.start_node, la referencia al nodo anterior se establecerá en el nodo recién insertado.
  3. Finalmente, self.start_node se convertirá en el nodo recién insertado.

El siguiente script inserta un elemento al comienzo de la lista doblemente enlazada:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    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 método insert_at_start() a la clase DoublyLinkedList que creó anteriormente.

Inserción de elementos al final

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    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 método insert_at_end() a la clase DoublyLinkedList que creó anteriormente.

Insertar elemento después de otro elemento

Para insertar un elemento después de otro, 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 nodos en la lista doblemente enlazada. En caso de que no se encuentre el nodo después del cual queremos insertar el nuevo nodo, mostramos el mensaje al usuario de que no se encuentra el elemento. De lo contrario, si se encuentra el nodo, se selecciona y realizamos cuatro operaciones:

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    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 método insert_after_item() a la clase DoublyLinkedList que creó anteriormente.

Insertar elemento antes de otro elemento

Para insertar un elemento antes de otro, 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 nodos en la lista doblemente enlazada. En caso de que no se encuentre el nodo antes del cual queremos insertar el nuevo nodo, mostramos el mensaje al usuario de que no se encuentra el elemento. De lo contrario, si se encuentra el nodo, se selecciona y realizamos cuatro operaciones:

  1. Establezca la siguiente referencia del nodo recién insertado al nodo seleccionado.
  2. Establezca la referencia anterior del nodo recién insertado a la referencia anterior del seleccionado.
  3. Establezca la siguiente referencia del nodo anterior al nodo seleccionado, al nodo recién agregado.
  4. Finalmente, establezca la referencia anterior del nodo seleccionado al nodo recién insertado.

La secuencia de comandos para agregar un elemento antes de otro elemento en una lista doblemente enlazada es la siguiente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    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 método insert_before_item() a la clase DoublyLinkedList que creó anteriormente.

Atravesando una lista doblemente enlazada {#atravesando una lista doblemente enlazada}

Recorrer una lista doblemente enlazada es muy similar a recorrer una lista con un solo enlace. El guión es el siguiente:

1
2
3
4
5
6
7
8
9
    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 método traverse_list() a la clase DoublyLinkedList que creó anteriormente.

Eliminación de elementos de la lista doblemente enlazada

Al igual que la inserción, puede haber varias formas de eliminar elementos de una lista doblemente vinculada. En este apartado repasaremos algunos de ellos.

Eliminación de elementos desde el inicio

La forma más fácil 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 nodo de inicio en el siguiente nodo y luego establecer la referencia anterior del nodo de inicio en Ninguno. 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 nodo de inicio en Ninguno. La siguiente secuencia de comandos se puede utilizar para eliminar elementos desde el inicio de la lista doblemente enlazada.

1
2
3
4
5
6
7
8
9
   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 método delete_at_start() a la clase DoublyLinkedList que creó anteriormente.

Eliminación de elementos desde el final

Para eliminar el elemento del final, volvemos a verificar 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 nodo de inicio en Ninguno. Si la lista tiene más de un elemento, iteramos a través de la lista hasta llegar al último nodo. Una vez que llegamos al último nodo, establecemos la siguiente referencia del nodo anterior al último nodo, en Ninguno, lo que en realidad elimina el último nodo. El siguiente script se puede utilizar para eliminar el elemento del final.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    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 método delete_at_end() a la clase DoublyLinkedList que creó anteriormente.

Eliminación de elementos por valor

La eliminación de un elemento por valor es la más complicada de todas las funciones de eliminación en listas doblemente enlazadas, 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    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 la función delete_element_by_value() que toma el valor del nodo como parámetro y elimina ese nodo. Al principio de la función comprobamos si la lista está vacía o no. Si la lista está vacía, simplemente mostramos al usuario que la lista está vacía.

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

1
2
3
        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_node en Ninguno, lo que significa que la lista ahora no tendrá ningún elemento. Si sólo hay un elemento y no es el que queremos eliminar, simplemente mostraremos el mensaje de que no se encuentra el elemento a eliminar.

El siguiente fragmento de código implementa esta lógica:

1
2
3
4
5
6
        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 que se eliminará es el primero. 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:

1
2
3
4
        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 que se va a eliminar no es el primero, recorremos todos los elementos de la lista excepto el último y vemos si alguno de los nodos tiene el valor que coincide con el valor que se eliminará. Si se encuentra el nodo, realizamos las siguientes dos operaciones:

  1. Establezca el valor de la siguiente referencia del nodo anterior a la siguiente referencia del nodo a eliminar.
  2. Establezca el valor anterior del siguiente nodo en la referencia anterior del nodo que se eliminará.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
        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 método delete_element_by_value() a la clase DoublyLinkedList que creó anteriormente.

Inversión de una lista doblemente enlazada

Para invertir una lista doblemente enlazada, básicamente debe realizar las siguientes operaciones:

  1. La siguiente referencia del nodo de inicio debe configurarse como ninguno porque el primer nodo se convertirá en el último nodo de la lista invertida.
  2. La referencia anterior del último nodo debe establecerse en Ninguno ya que el último nodo se convertirá en el nodo anterior.
  3. Las siguientes referencias de los nodos (excepto el primer y último nodo) en la lista original deben intercambiarse con las referencias anteriores.

El script para invertir una lista doblemente enlazada es el siguiente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    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 método reverse_linked_list() a la clase DoublyLinkedList que creó anteriormente.

Prueba de funciones de listas doblemente enlazadas

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

Primero vamos a crear el objeto de la clase DoublyLinkedList. Ejecute el siguiente script:

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

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

1
new_linked_list.traverse_list()

Producción:

1
50

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

1
2
3
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:

1
2
3
4
18
5
10
50

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

1
2
3
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 enlazada, debería ver los siguientes elementos:

1
2
3
4
5
6
7
18
5
10
50
29
39
49 

Insertemos un elemento después de 50.

1
new_linked_list.insert_after_item(50, 65)

Ahora la lista debería verse así:

1
2
3
4
5
6
7
8
18
5
10
50
65
29
39
49 

Finalmente, agreguemos un elemento antes del elemento 29.

1
new_linked_list.insert_before_item(29, 100)

La lista en este momento, debe contener los siguientes elementos:

1
2
3
4
5
6
7
8
9
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.

1
new_linked_list.delete_at_start()

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

1
2
3
4
5
6
7
8
5
10
50
65
100
29
39
49 

De manera similar, el siguiente script elimina el elemento del final de la lista doblemente enlazada:

1
new_linked_list.delete_at_end()

Recorrer la lista ahora devolverá los siguientes elementos:

1
2
3
4
5
6
7
5
10
50
65 
100 
29
39

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

1
new_linked_list.delete_element_by_value(65)

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

Probando la función inversa

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

1
new_linked_list.reverse_linked_list()

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

1
2
3
4
5
6
39
29
100
50
10
5 

Conclusión

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

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 enlazada. Finalmente estudiamos cómo revertir una lista doblemente enlazada.