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 de enlaces individuales. En este artículo, comenzaremos nuestra discusión acerca de la lista doblemente enlazada, que en realidad es una extensión de la lista enlazada única.
En la lista de enlaces individuales, cada nodo de la lista tiene dos componentes, el valor real del nodo y la referencia al siguiente nodo en la lista vinculada. En la lista doblemente enlazada, cada nodo tiene tres componentes: el valor del nodo, la referencia al nodo anterior y la referencia al siguiente nodo. Para el nodo de inicio de la lista doblemente enlazada, la referencia al nodo anterior es nula. De manera similar, para el último nodo en la lista doblemente enlazada, la referencia al siguiente nodo es nula.

Pros y contras de una lista doblemente vinculada

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

Pros

  • A diferencia de una sola lista enlazada, 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 hacia adelante, mientras que las referencias a los nodos anteriores permiten el recorrido en la dirección hacia atrás.
  • Las operaciones básicas, como la inserción y la eliminación, son más fáciles de implementar en las listas con doble enlace, ya que, a diferencia de las listas con un solo enlace, no es necesario pasar al 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 con doble enlace 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.

Implementando la lista doblemente vinculada con Python

En esta sección, veremos cómo podemos crear una lista doblemente enlazada 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 creamos una clase para el nodo único en la lista. Agregue el siguiente código a su 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: itemnref, y prefLa itemvariable almacenará los datos reales para el nodo. Las nreftiendas de la referencia a la siguiente nodo, mientras que prefalmacena la referencia al nodo anterior en la lista doblemente enlazada.
A continuación, debemos crear la DoublyLinkedListclase, que contiene diferentes funciones relacionadas con la lista de enlaces dobles. Agregue 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 la 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 es Noneo no. Si la variable es None, significa que la lista está realmente vacía. A continuación, se crea un nuevo nodo 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 nodo. En caso de que la lista no esté vacía, simplemente se mostrará un mensaje al usuario indicando que la lista no está vacía.
Agregue el insert_in_emptylist()método a la DoublyLinkedListclase que creó anteriormente.
Insertar elementos al inicio
Para insertar un elemento al comienzo 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()el elemento 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 que la self.start_nodereferencia al nodo anterior se establezca en el nodo recién insertado.
  3. Finalmente, self.start_nodese convertirá en el nodo recién insertado.
La siguiente secuencia de comandos inserta un elemento al comienzo de la lista con doble enlace:
    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 comienzo. Al principio, necesitamos 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, atravesaremos la lista hasta que la referencia al siguiente nodo se convierta en NoneCuando la siguiente referencia de nodo se convierte None, 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. La secuencia de comandos para insertar un elemento en el último nodo es la 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, 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 deseamos insertar el nuevo nodo, le mostraremos al usuario el mensaje de que no se encontró 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 en el 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.
La secuencia de comandos para insertar un elemento después de otro elemento es la 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 de otro artículo
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, le mostraremos al usuario el mensaje de que no se encontró 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 en el nodo seleccionado.
  2. Establezca la referencia anterior del nodo recién insertado en la referencia anterior del seleccionado.
  3. Establezca la siguiente referencia del nodo anterior al nodo seleccionado, al nodo recién agregado.
  4. Finalmente, configure 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:
    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 vinculada

Atravesar una lista doblemente enlazada es muy similar a atravesar una lista enlazada única. 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 la lista doblemente vinculada

Al igual que en la inserción, puede haber varias formas de eliminar elementos de una lista con doble enlace. En esta sección, revisaremos algunos de ellos.
Eliminar 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 NoneSin embargo antes de que hagamos eso necesitamos realizar dos verificaciones. 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 NoneLa siguiente secuencia de comandos se puede utilizar para eliminar elementos desde el inicio de la lista con doble enlace.
   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.
Borrar 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 nodo de inicio en NoneSi la lista tiene más de un elemento, recorreremos la lista hasta llegar al último nodo. Una vez que llegamos al último nodo, establecemos la siguiente referencia del nodo anterior al último nodo, a la Noneque en realidad elimina el último nodo. La siguiente secuencia de comandos 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 con doble enlace, ya que deben manejarse varios casos para eliminar un elemento por valor. Primero veamos cómo se ve la función y luego veremos la explicación de cada pieza de código.
    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 nodo como parámetro y elimina ese nodo. 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 fragmento de 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 en realidad el elemento que queremos eliminar. Si el único elemento es el que queremos eliminar, simplemente establecemos el self.start_nodeque Nonelo que significa que la lista ya no tendrá ningún artículo. 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 que se eliminará.
El siguiente fragmento de 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 que se va 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 del inicio en caso de que haya 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 que se va a eliminar no es el primer elemento, recorreremos todos los elementos de la lista excepto el último y veremos 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 que se eliminará.
  2. Establezca el valor anterior del siguiente nodo en la referencia anterior del nodo que se va a eliminar.
Finalmente, si el nodo que se va a eliminar es el último nodo, la siguiente referencia del nodo anterior al último nodo se establece en NoneEl 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 tiene que realizar las siguientes operaciones:
  1. La siguiente referencia del nodo de inicio debe establecerse en ninguno porque el primer nodo se convertirá en el último nodo en la lista invertida.
  2. La referencia anterior del último nodo debe establecerse en, Noneya que el último nodo se convertirá en el nodo anterior.
  3. Las siguientes referencias de los nodos (excepto el primero y el último nodo) en la lista original deben intercambiarse con las referencias anteriores.
La secuencia de comandos para revertir una lista doblemente enlazada es la 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 de enlace doble

En esta sección, probaremos las funciones con doble enlace que creamos en las secciones anteriores.
Primero creamos el objeto de la DoublyLinkedListclase. Ejecuta el siguiente script:
new_linked_list = DoublyLinkedList()  
Pruebas de funciones de inserción
Probemos primero las funciones de inserción. Primero agregaremos elementos en la lista vacía. Ejecuta el siguiente script:
new_linked_list.insert_in_emptylist(50)  
Ahora, si recorres la lista, deberías ver 50 como el único elemento de la lista como se muestra a continuación:
new_linked_list.traverse_list()  
Salida:
50  
Ahora vamos a agregar algunos elementos al comienzo. Ejecuta 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 recorres la lista, deberías 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 atraviesa la lista doblemente enlazada, 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 punto del tiempo, debe contener los siguientes elementos:
18  
5  
10  
50  
65  
100  
29  
39  
49  
Pruebas de funciones de eliminación
Ahora probemos 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 artículo 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 con doble enlace:
new_linked_list.delete_at_end()  
Al atravesar 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 utilizando la delete_element_by_value()función que 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 función inversa
Finalmente, invirtamos la lista usando la reverse_linked_list()función. Ejecuta el siguiente script:
new_linked_list.reverse_linked_list()  
Ahora, si recorres la lista, verás la lista enlazada invertida:
39  
29  
100  
50  
10  
5  

Conclusión

La lista doblemente enlazada es extremadamente útil específicamente cuando tiene que realizar muchas inserciones y eliminar operaciones. Los enlaces a los nodos anteriores y siguientes hacen que sea muy fácil insertar y eliminar nuevos elementos sin tener que realizar un seguimiento de los nodos anteriores y siguientes.
En este artículo, vimos cómo se puede implementar la lista de enlaces dobles con Python. También vimos diferentes formas de realizar operaciones de inserción y eliminación en una lista con doble enlace. Finalmente estudiamos cómo revertir una lista doblemente enlazada.

Acerca de: Programator

Somos Instinto Programador

0 comentarios:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Con tecnología de Blogger.