Ordenar y fusionar listas enlazadas únicas

En el último artículo, comenzamos nuestra discusión sobre la lista enlazada. Vimos qué es la lista enlazada junto con sus ventajas y desventajas. También estudiamos...

En el último artículo, comenzamos nuestra discusión sobre la lista enlazada. Vimos qué es la lista enlazada junto con sus ventajas y desventajas. También estudiamos algunos de los métodos de lista enlazada más utilizados, como el recorrido, la inserción, la eliminación, la búsqueda y el recuento de un elemento. Finalmente, vimos cómo invertir una lista enlazada.

En este artículo, continuaremos desde donde lo dejamos en el último artículo y veremos cómo ordenar un enlace lista usando burbuja y clasificación por combinación, y cómo fusionar dos listas enlazadas ordenadas.

Antes de continuar, es imperativo mencionar que debe crear las clases Node y LinkedList que creamos en el último artículo.

Ordenar una lista enlazada usando Bubble Sort

Hay dos formas de ordenar una lista vinculada usando [clasificación de burbujas] (https://en.wikipedia.org/wiki/Bubble_sort):

  1. Intercambio de datos entre nodos
  2. Modificando los enlaces entre nodos

En esta sección, veremos cómo funcionan estos dos enfoques. Usaremos el algoritmo de ordenación de burbujas para ordenar primero la lista vinculada cambiando los datos, y luego veremos cómo podemos usar la ordenación de burbujas para cambiar los vínculos a fin de ordenar la lista vinculada.

Clasificación de la lista enlazada mediante el intercambio de datos {#clasificación de la lista enlazada mediante el intercambio de datos}

Para ordenar una lista enlazada mediante el intercambio de datos, necesitamos declarar tres variables p, q y end.

La variable p se inicializará con el nodo de inicio, mientras que end se establecerá en Ninguno.

Es importante recordar que para ordenar la lista con n elementos usando la ordenación de burbujas, necesita n-1 iteraciones.

Para implementar la ordenación de burbujas, necesitamos dos bucles while. El ciclo while externo se ejecuta hasta que el valor de la variable end es igual a self.start_node.

El ciclo while interno se ejecuta hasta que p se vuelve igual a la variable end. Dentro del bucle while externo, el valor de p se establecerá en self.start_node, que es el primer nodo. Dentro del bucle while interno, el valor de q se establecerá en p.link, que en realidad es el nodo junto a q. Luego, los valores de p y q se compararán si p es mayor que q, los valores de ambas variables se intercambiarán y luego p apuntará a p.ref, que es el siguiente nodo. Finalmente, al fin se le asignará el valor de p. Este proceso continúa hasta que se ordena la lista enlazada.

Entendamos este proceso con la ayuda de un ejemplo. Supongamos que tenemos la siguiente lista:

1
8,7,1,6,9

Implementemos nuestro algoritmo para ordenar la lista. Veremos qué sucederá durante cada iteración. El propósito de la ordenación de burbujas es que durante cada iteración, el valor más grande se debe empujar hasta el final, por lo tanto, al final de todas las iteraciones, la lista se ordenará automáticamente.

Antes de que se ejecute el bucle, el valor de end se establece en Ninguno.

En la primera iteración, p se establecerá en 8 y q se establecerá en 7. Dado que p es mayor que q, los valores se intercambiarán y p se convertirá en p.ref. En este momento, la lista enlazada se verá así:

1
7,8,1,6,9

Dado que en este momento p no es igual a end, el bucle continuará y ahora p se convertirá en 8 y q se convertirá en 1. Dado que de nuevo p es mayor que q, los valores se intercambiarán de nuevo y p volverá a ser p.ref. La lista se verá así:

1
7,1,8,6,9

Aquí nuevamente, p no es igual a end, el ciclo continuará y ahora p se convertirá en 8 y q se convertirá en 6. Como nuevamente p es mayor que q, los valores serán cambiado de nuevo y p volverá a ser p.ref. La lista se verá así:

1
7,1,6,8,9

De nuevo p no es igual a end, el bucle continuará y ahora p se convertirá en 8 y q se convertirá en 9. Aquí, dado que p no es mayor que q, los valores no serán intercambiado y p se convertirá en p.ref. En este momento, la referencia de p apuntará a Ninguno, y end también apuntará a Ninguno. Por lo tanto, el ciclo while interno se romperá y end se establecerá en p.

En el siguiente conjunto de iteraciones, el bucle se ejecutará hasta el 8, ya que el 9 ya está al final. El proceso continúa hasta que la lista está completamente ordenada.

El código de Python para ordenar la lista enlazada usando la ordenación de burbujas intercambiando los datos es el siguiente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    def bub_sort_datachange(self):
        end = None
        while end != self.start_node:
            p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.item, q.item = q.item, p.item
                p = p.ref
            end = p

Agrega el método bub_sort_dataexchange() a la clase LinkedList que creaste en el último artículo.

Una vez que agregue el método a la lista vinculada, cree cualquier conjunto de nodos usando la función make_new_list() y luego use bub_sort_dataexchange() para ordenar la lista. Deberías ver la lista ordenada cuando ejecutas la función traverse_list().

La ordenación de burbujas también se puede usar para ordenar una lista vinculada modificando los vínculos en lugar de cambiar los datos. El proceso sigue siendo bastante similar a ordenar la lista intercambiando datos, sin embargo, en este caso, tenemos una variable adicional r que siempre corresponderá al nodo anterior al nodo p.

Tomemos un ejemplo simple de cómo intercambiaremos dos nodos modificando enlaces. Supongamos que tenemos una lista enlazada con los siguientes elementos:

1
10,45,65,35,1

Y queremos intercambiar 65 y 35. En este momento p corresponde al nodo 65 y q corresponde al nodo 35. La variable r corresponderá al nodo 45 (anterior al nodo p). Ahora, si el nodo p es mayor que el nodo q, que es el caso aquí, p.ref se establecerá en q.ref y q.ref se establecerá en p. Del mismo modo, r.ref se establecerá en q. Esto intercambiará los nodos 65 y 35.

El siguiente método implementa la clasificación de burbujas para la lista enlazada mediante la modificación de enlaces:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def bub_sort_linkchange(self):
        end = None
        while end != self.start_node:
            r = p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.ref = q.ref
                    q.ref = p
                    if p != self.start_node:
                        r.ref = q
                    else:
                        self.start_node = q
                    p,q = q,p
                r = p
                p = p.ref
            end = p

Agrega el método bub_sort_linkchange() a la clase LinkedList que creaste en el último artículo.

Una vez que agregue el método a la lista vinculada, cree cualquier conjunto de nodos usando la función make_new_list() y luego use bub_sort_linkchange() para ordenar la lista. Deberías ver la lista ordenada cuando ejecutas la función traverse_list().

Fusión de lista enlazada ordenada

En esta sección, veremos cómo podemos fusionar dos listas enlazadas ordenadas de manera que la lista enlazada resultante también esté ordenada. Hay dos enfoques para lograr esto. Podemos crear una nueva lista enlazada que contenga listas ordenadas individualmente o simplemente podemos cambiar los enlaces de las dos listas enlazadas para unir las dos listas enlazadas ordenadas. En el segundo caso, no tenemos que crear una nueva lista enlazada.

Primero veamos cómo podemos fusionar dos listas vinculadas creando una nueva lista.

Fusión de listas enlazadas ordenadas mediante la creación de una nueva lista

Primero ejecutemos el algoritmo en seco para ver cómo podemos fusionar dos listas enlazadas ordenadas con la ayuda de una nueva lista.

Supongamos que tenemos las siguientes dos listas enlazadas ordenadas:

hoja1:

1
10,45,65,

lista2:

1
5,15,35,68

Estas son las dos listas que queremos fusionar. El algoritmo es sencillo. Todo lo que necesitaremos son tres variables, p, q y em, y una lista vacía newlist.

Al comienzo del algoritmo, ‘p’ apuntará al primer elemento de la ’lista1’, mientras que ‘q’ apuntará al primer elemento de la ’lista2’. La variable em estará vacía. Al inicio del algoritmo, tendremos los siguientes valores:

1
2
3
4
p = 10
q = 5
em = none
newlist = none

A continuación, compararemos el primer elemento de lista1 con el primer elemento de lista2, en otras palabras, compararemos los valores de p y q y el valor menor se almacenará en la variable em que se convertirá en el primer nodo de la nueva lista. El valor de em se agregará al final de newlist.

Después de la primera comparación tendremos los siguientes valores:

1
2
3
4
p = 10
q = 15
em = 5
newlist = 5

Dado que q era menor que p, por lo tanto, almacenamos el valor de q en em movido 'q' un índice a la derecha. En la segunda pasada, tendremos los siguientes valores:

1
2
3
4
p = 45
q = 15
em = 10
newlist = 5, 10

Aquí, dado que p era más pequeño, agregamos el valor de p a newlist, y establecemos em en p y luego movimos p un índice a la derecha. En la siguiente iteración tenemos:

1
2
3
4
p = 45
q = 35
em = 15
newlist = 5, 10, 15

Del mismo modo, en la siguiente iteración:

1
2
3
4
p = 45
q = 68
em = 35
newlist = 5, 10, 15, 35

Y en la próxima iteración, p será nuevamente menor que q, por lo tanto:

1
2
3
4
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

Finalmente,

1
2
3
4
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

Cuando uno de la lista se convierte en Ninguno, todos los elementos de la segunda lista se agregan al final de la nueva lista. Por lo tanto, la lista final será:

1
2
3
4
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

El script de Python para fusionar dos listas ordenadas es el siguiente:

 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
30
31
32
33
34
35
    def merge_helper(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
        return merged_list

    def merge_by_newlist(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                p = p.ref
            else:
                em.ref = Node(q.item)
                q = q.ref
            em = em.ref

        while p is not None:
            em.ref = Node(p.item)
            p = p.ref
            em = em.ref

        while q is not None:
            em.ref = Node(q.item)
            q = q.ref
            em = em.ref

        return startNode

En el script anterior tenemos dos métodos: merge_helper() y merge_by_newlist(). El primer método merge_helper() toma una lista enlazada como parámetro y luego pasa la clase self, que es una lista enlazada en sí misma y la lista enlazada se le pasa como parámetro, al método merge_by_newlist().

El método merge_by_newlist() fusiona los dos enlaces creando una nueva lista enlazada y devuelve el nodo de inicio de la nueva lista enlazada. Agregue estos dos métodos a la clase LinkedList. Cree dos nuevas listas enlazadas, ordénelas usando los métodos bub_sort_datachange() o bub_sort_linkchange() que creó en la última sección y luego use merge_by_newlist() para ver si puede fusionar dos listas enlazadas ordenadas o no.

En este enfoque, no se utiliza una nueva lista enlazada para almacenar la fusión de dos listas enlazadas ordenadas. Más bien, los enlaces de las dos listas enlazadas se modifican de tal manera que las dos listas enlazadas se fusionan ordenadamente.

Veamos un ejemplo simple de cómo podemos hacer esto. Supongamos que tenemos las mismas dos listas list1 y list2:

hoja1:

1
10,45,65,

lista2:

1
5,15,35,68

Queremos fusionarlos de manera ordenada reorganizando los enlaces. Para ello necesitamos las variables p, q y em. Inicialmente, tendrán los siguientes valores:

1
2
3
4
p = 10
q = 5
em = none
newlist = none

A continuación, compararemos el primer elemento de lista1 con el primer elemento de lista2, en otras palabras, compararemos los valores de p y q y el valor menor se almacenará en la variable em que se convertirá en el primer nodo de la nueva lista.

Después de la primera comparación tendremos los siguientes valores:

1
2
3
4
p = 10
q = 15
start = 5
em = start

Después de la primera iteración, dado que q es menor que p, el nodo de inicio apuntará hacia q y q se convertirá en q.ref. El em será igual al inicio. El em siempre se referirá al nodo recién insertado en la lista fusionada.

1
2
3
p = 45
q = 15
em = 10

Aquí, dado que p era más pequeño que q, la variable em ahora apunta hacia el valor original de p y p se convierte en p.ref.

1
2
3
p = 45
q = 35
em = 15

Aquí, dado que q era más pequeño que p, em apunta hacia q y q se convierte en q.ref.

1
2
3
p = 45
q = 68
em = 35

Del mismo modo em aquí apunta hacia q.

1
2
3
4
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

Y aquí em apunta hacia se convierte en p.

1
2
3
4
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

Cuando una de las listas se convierte en Ninguna, los elementos de la segunda lista simplemente se agregan al final.

1
2
3
4
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

El script que contiene funciones para fusionar dos listas sin crear una nueva lista es el siguiente:

 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
30
31
32
    def merge_helper2(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
        return merged_list

    def merge_by_linkChange(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                em = em.ref
                p = p.ref
            else:
                em.ref = Node(q.item)
                em = em.ref
                q = q.ref


        if p is None:
            em.ref = q
        else:
            em.ref = p

        return startNode

En el script anterior tenemos dos métodos: merge_helper2() y merge_by_linkChange(). El primer método merge_helper2() toma una lista enlazada como parámetro y luego pasa la clase propia, que es una lista enlazada en sí misma y la lista enlazada le pasó como parámetro, a merge_by_linkChange(), que fusiona los dos vinculado modificando los vínculos y devuelve el nodo de inicio de la lista fusionada. Agregue estos dos métodos a la clase LinkedList. Cree dos nuevas listas enlazadas, ordénelas usando los métodos bub_sort_datachange() o bub_sort_linkchange() que creó en la última sección y luego use merge_by_newlist() para ver si puede fusionar dos listas enlazadas ordenadas o no. Veamos este proceso en acción.

Cree una nueva lista enlazada utilizando el siguiente script:

1
2
new_linked_list1 = LinkedList()
new_linked_list1.make_new_list()

El script le pedirá el número de nodos a ingresar. Ingrese tantos nodos como desee y luego agregue valores para cada nodo como se muestra a continuación:

1
2
3
4
5
How many nodes do you want to create: 4
Enter the value for the node:12
Enter the value for the node:45
Enter the value for the node:32
Enter the value for the node:61

A continuación, cree otra lista enlazada repitiendo el proceso anterior:

1
2
new_linked_list2 = LinkedList()
new_linked_list2.make_new_list()

A continuación, agregue algunos nodos ficticios con la ayuda del siguiente script:

1
2
3
4
5
How many nodes do you want to create: 4
Enter the value for the node:36
Enter the value for the node:41
Enter the value for the node:25
Enter the value for the node:9

El siguiente paso es ordenar ambas listas. Ejecute el siguiente script:

1
2
new_linked_list1. bub_sort_datachange()
new_linked_list2. bub_sort_datachange()

Finalmente, el siguiente script fusiona las dos listas enlazadas:

1
list3 = new_linked_list1.merge_helper2(new_linked_list2)

Para ver si las listas realmente se han fusionado, ejecute el siguiente script:

1
list3.traverse_list()

La salida se ve así:

1
2
3
4
5
6
7
8
9
12
25
32
36
41
45
61

Conclusión

En este artículo continuamos desde donde lo dejamos en el Artículo anterior. Vimos cómo podemos ordenar las listas de combinación cambiando los datos y luego modificando los enlaces. Finalmente, también estudiamos diferentes formas de fusionar dos listas enlazadas ordenadas.

En el próximo artículo veremos cómo construir y realizar operaciones en listas doblemente enlazadas.