Ordenar y fusionar una lista vinculada única

    En el último artículo, comenzamos nuestra discusión sobre la lista vinculada. Vimos lo que es la lista enlazada junto con sus ventajas y desventajas. También estudiamos algunos de los métodos de listas vinculadas 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 revertir una lista enlazada.

    En este artículo, continuaremos desde donde lo dejamos en el último artículo y veremos cómo ordenar una lista vinculada usando burbujas y fusionar ordenación, y cómo fusionar dos listas vinculadas ordenadas.

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

    Ordenar una lista vinculada usando Bubble Sort

    Hay dos formas de ordenar una lista enlazada usando ordenamiento de burbuja:

    • Intercambio de datos entre nodes
    • Modificar los enlaces entre nodes

    En esta sección, veremos cómo funcionan ambos enfoques. Usaremos el algoritmo de clasificación de burbujas para ordenar primero la lista enlazada cambiando los datos, y luego veremos cómo podemos utilizar la clasificación de burbujas para cambiar los enlaces y ordenar la lista enlazada.

    Clasificación de la lista vinculada mediante el intercambio de datos

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

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

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

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

    El ciclo while interno se ejecuta hasta p se vuelve igual al end variable. Dentro del ciclo externo while, el valor de p se establecerá en self.start_node que es el primer node. Dentro del ciclo interno while, el valor de q se establecerá en p.link que es en realidad el node junto a q. Entonces los valores de p y q será comparado 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 node. Finalmente, el end se le asignará el valor de p. Este proceso continúa hasta que se ordena la lista vinculada.

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

    8,7,1,6,9
    

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

    Antes de que se ejecute el ciclo, el valor de end se establece en None.

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

    7,8,1,6,9
    

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

    7,1,8,6,9
    

    Aqui otra vez, p no es igual a end, el ciclo continuará y ahora p se convertirá en 8 y q se convertirá en 6. Ya que otra vez p es mayor que q, los valores se intercambiarán nuevamente y p se convertirá de nuevo p.ref. La lista se verá así:

    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í desde p no es mayor que q, los valores no se intercambiarán y p se convertirá p.ref. En este momento, la referencia de p apuntará a Noney end también apunta a None. Por lo tanto, el bucle interno while se romperá y end se establecerá en p.

    En el siguiente conjunto de iteraciones, el ciclo se ejecutará hasta 8, ya que 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 vinculada usando la clasificación de burbujas intercambiando los datos es el siguiente:

        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
    

    Añade el bub_sort_dataexchange() método para el LinkedList clase que creó en el último artículo.

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

    La clasificación de burbujas también se puede utilizar 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 node anterior al p node.

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

    10,45,65,35,1
    

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

    El siguiente método implementa la clasificación de burbujas para la lista vinculada modificando los vínculos:

        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
    

    Añade el bub_sort_linkchange() método para el LinkedList clase que creó en el último artículo.

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

    Fusionar 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 lograrlo. Podemos crear una nueva lista vinculada que contenga listas ordenadas individualmente o simplemente podemos cambiar los enlaces de las dos listas vinculadas para unir las dos listas vinculadas ordenadas. En el segundo caso, no tenemos que crear una nueva lista vinculada.

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

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

    Primero ejecutemos el algoritmo 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:

    list1:

    10,45,65,
    

    list2:

    5,15,35,68
    

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

    Al comienzo del algoritmo, p apuntará al primer elemento de la list1 mientras q apuntará al primer elemento de la list2. La variable em estará vacío. Al inicio del algoritmo, tendremos los siguientes valores:

    p = 10
    q = 5
    em = none
    newlist = none
    

    A continuación, compararemos el primer elemento del list1 con el primer elemento de list2, 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 node de la nueva lista. El valor de em se agregará al final de la newlist.

    Tras la primera comparación tendremos los siguientes valores:

    p = 10
    q = 15
    em = 5
    newlist = 5
    

    Ya que q fue menor que p, por lo tanto, almacenamos el valor de q en em movió ‘q’ un índice a la derecha. En la segunda pasada, tendremos los siguientes valores:

    p = 45
    q = 15
    em = 10
    newlist = 5, 10
    

    Aquí desde p era menor, agregamos el valor de p a newlist, y establecer em a p y luego se movió p un índice a la derecha. En la siguiente iteración tenemos:

    p = 45
    q = 35
    em = 15
    newlist = 5, 10, 15
    

    Del mismo modo, en la siguiente iteración:

    p = 45
    q = 68
    em = 35
    newlist = 5, 10, 15, 35
    

    Y en la siguiente iteración, p será de nuevo más pequeño que q, por lo tanto:

    p = 65
    q = 68
    em = 45
    newlist = 5, 10, 15, 35, 45
    

    Finalmente,

    p = None
    q = 68
    em = 65
    newlist = 5, 10, 15, 35, 45, 65
    

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

    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:

        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 el self clase, que es una lista vinculada en sí misma y la lista vinculada que se le pasa como parámetro, merge_by_newlist() método.

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

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

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

    list1:

    10,45,65,
    

    list2:

    5,15,35,68
    

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

    p = 10
    q = 5
    em = none
    newlist = none
    

    A continuación, compararemos el primer elemento del list1 con el primer elemento de list2, en otras palabras, compararemos los valores de p y q y el valor más pequeño se almacenará en la variable em que se convertirá en el primer node de la nueva lista.

    Tras la primera comparación tendremos los siguientes valores:

    p = 10
    q = 15
    start = 5
    em = start
    

    Después de la primera iteración, desde q es menos que p, el node de inicio apuntará hacia q y q se convertirá q.ref. los em será igual para empezar. los em siempre hará referencia al node recién insertado en la lista combinada.

    p = 45
    q = 15
    em = 10
    

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

    p = 45
    q = 35
    em = 15
    

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

    p = 45
    q = 68
    em = 35
    

    similar em aquí apunta hacia q.

    p = 65
    q = 68
    em = 45
    newlist = 5, 10, 15, 35, 45
    

    Y aquí em apunta hacia se convierte p.

    p = None
    q = 68
    em = 65
    newlist = 5, 10, 15, 35, 45, 65
    

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

    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:

        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 vinculada como parámetro y luego pasa la clase propia, que es una lista vinculada en sí misma y la lista vinculada se le pasa como parámetro, a la merge_by_linkChange(), que fusiona los dos enlazados modificando los enlaces y devuelve el node de inicio de la lista fusionada. Agregue estos dos métodos al LinkedList clase. Cree dos nuevas listas vinculadas, ordénelas usando el bub_sort_datachange() o el bub_sort_linkchange() métodos que creó en la última sección y luego use el merge_by_newlist() para ver si puede fusionar dos listas enlazadas ordenadas o no. Veamos este proceso en acción.

    Cree una nueva lista vinculada utilizando el siguiente script:

    new_linked_list1 = LinkedList()
    new_linked_list1.make_new_list()
    

    El script le pedirá la cantidad de nodes para ingresar. Ingrese tantos nodes como desee y luego agregue valores para cada node como se muestra a continuación:

    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 vinculada repitiendo el proceso anterior:

    new_linked_list2 = LinkedList()
    new_linked_list2.make_new_list()
    

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

    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:

    new_linked_list1. bub_sort_datachange()
    new_linked_list2. bub_sort_datachange()
    

    Finalmente, el siguiente script fusiona las dos listas enlazadas:

    list3 = new_linked_list1.merge_helper2(new_linked_list2)
    

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

    list3.traverse_list()
    

    La salida se ve así:

    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.

     

    Etiquetas:

    Deja una respuesta

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