Listas enlazadas en detalle con ejemplos de Python: Listas enlazadas simples

    Las listas enlazadas son una de las estructuras de datos m谩s utilizadas en cualquier lenguaje de programaci贸n. En este art铆culo, estudiaremos las listas enlazadas en detalle. Veremos cu谩les son los diferentes tipos de listas enlazadas, c贸mo recorrer una lista enlazada, c贸mo insertar y eliminar elementos de una lista enlazada, cu谩les son las diferentes t茅cnicas para ordenar una lista enlazada, c贸mo revertir una lista enlazada, etc. .

    Despu茅s de leer este art铆culo, deber铆a poder descifrar todas las preguntas de la entrevista de la lista vinculada.

    驴Qu茅 es una lista vinculada?

    Antes de estudiar qu茅 son las listas vinculadas, primero revisemos brevemente c贸mo las matrices almacenan datos. En las matrices, los datos se almacenan en ubicaciones de memoria contiguas. Por ejemplo, si el primer elemento de la matriz se almacena en el 铆ndice 10 de la memoria y tiene un tama帽o de 15 bytes, el segundo elemento se almacenar谩 en el 铆ndice 10 + 15 + 1 = 铆ndice 26. Por lo tanto, es sencillo atravesar una matriz.

    Para encontrar el tercer elemento en una matriz, simplemente puede usar el 铆ndice inicial del primer elemento, m谩s el tama帽o del primer elemento, m谩s el tama帽o del segundo elemento, m谩s 1.

    C贸mo almacenan datos las listas enlazadas

    Las listas enlazadas, por otro lado, son diferentes. Listas vinculadas, no almacenan datos en ubicaciones de memoria contiguas. Para cada elemento en la ubicaci贸n de la memoria, la lista vinculada almacena el valor del elemento y la referencia o puntero al siguiente elemento. Un par del elemento de la lista enlazada y la referencia al siguiente elemento constituyen un node.

    Por ejemplo, si un node consta de 34 | 10, significa que el valor del node es 30, mientras que el siguiente elemento se almacena en la ubicaci贸n de memoria “10”. Para recorrer una lista vinculada, solo necesita conocer la ubicaci贸n de la memoria o la referencia del primer node, el resto de nodes se pueden recorrer secuencialmente usando la referencia al siguiente elemento en cada node.

    La referencia al primer node tambi茅n se conoce como node de inicio.

    Listas vinculadas frente a matrices:

    • Una lista vinculada es una estructura de datos din谩mica, lo que significa que la memoria reservada para la lista de v铆nculos se puede aumentar o reducir en tiempo de ejecuci贸n. No se asigna memoria para una estructura de datos de lista enlazada de antemano. Siempre que se requiera agregar un nuevo elemento al enlace, la memoria para el nuevo node se crea en tiempo de ejecuci贸n. Por otro lado, en el caso de la matriz, la memoria debe asignarse por adelantado para un n煤mero espec铆fico de elementos. En los casos en que no hay suficientes elementos disponibles para llenar todo el 铆ndice de la matriz, se desperdicia espacio de memoria.
    • Dado que las matrices requieren ubicaciones de memoria contiguas, es muy dif铆cil quitar o insertar un elemento en una matriz, ya que las ubicaciones de memoria de una gran cantidad de elementos deben actualizarse. Por otro lado, los elementos de la lista vinculada no se almacenan en una ubicaci贸n de memoria contigua, por lo que puede actualizar f谩cilmente las listas vinculadas.
    • Debido a su flexibilidad, una lista vinculada es m谩s adecuada para implementar estructuras de datos como pilas, colas y listas.

    Sin embargo, tambi茅n hay algunas desventajas en la lista vinculada.

    • Dado que cada elemento de la lista vinculada tiene que almacenar la referencia al siguiente elemento, se requiere algo de memoria adicional.
    • A diferencia de las matrices, donde puede acceder directamente a un elemento, no puede acceder directamente a un elemento de la lista vinculada ya que la 煤nica informaci贸n que tiene es la referencia al primer elemento. En t茅rminos de Big O, el tiempo de acceso en el peor de los casos es O (n).

    En esta serie de art铆culos, estudiaremos los siguientes tipos de listas enlazadas junto con sus diferentes funcionalidades.

    • Lista vinculada 煤nica
    • Lista doblemente vinculada
    • Lista enlazada circular
    • Lista vinculada con encabezado
    • Lista vinculada ordenada

    En esta primera parte del art铆culo, nos centraremos en la lista enlazada 煤nica y sus diferentes operaciones.

    Lista vinculada 煤nica
    Creaci贸n de la clase de node
    Creaci贸n de la clase de lista vinculada 煤nica
    Recorrido de elementos de lista vinculada
    Insertar elementos
    Contar elementos
    Buscar elementos
    Crear una lista vinculada
    Eliminar elementos
    Invertir una lista vinculada

    Lista vinculada 煤nica

    Una sola lista vinculada es la m谩s simple de todas las variantes de listas vinculadas. Cada node en una 煤nica lista vinculada contiene un elemento y una referencia al siguiente elemento y eso es todo.

    En esta secci贸n, veremos c贸mo crear un node para la lista vinculada 煤nica junto con las funciones para los diferentes tipos de inserci贸n, recorrido y eliminaci贸n.

    Crear la clase de node

    Lo primero que debe hacer es crear una clase para los nodes. Los objetos de esta clase ser谩n los nodes reales que insertaremos en nuestra lista vinculada. Sabemos que un node para una sola lista vinculada contiene el elemento y la referencia al siguiente node. Por lo tanto, nuestra clase de node contendr谩 dos variables miembro itemy ref. El valor de itemse establecer谩 mediante el valor pasado a trav茅s del constructor, mientras que la referencia se establecer谩 inicialmente en nulo.

    Ejecute el siguiente script:

    class Node:
        def __init__(self, data):
            self.item = data
            self.ref = None
    

    Creaci贸n de la clase de lista vinculada 煤nica

    A continuaci贸n, necesitamos crear una clase para la Lista vinculada. Esta clase contendr谩 los m茅todos para insertar, eliminar, recorrer y ordenar la lista. Inicialmente, la clase solo contendr谩 un miembro start_nodeque apuntar谩 al inicio o al primer node de la lista. El valor de start_nodese establecer谩 en nulo utilizando el constructor, ya que la lista vinculada estar谩 vac铆a en el momento de la creaci贸n. El siguiente script crea una clase para la lista vinculada.

    class LinkedList:
        def __init__(self):
            self.start_node = None
    

    Ahora hemos creado una clase para nuestra lista 煤nica. El siguiente paso es agregar la funci贸n de inserci贸n para insertar elementos en la lista vinculada. Pero antes de eso, agregaremos una funci贸n para recorrer una lista vinculada. Esta funci贸n nos ayudar谩 a leer los datos de nuestra lista.

    Atravesar elementos de lista vinculados

    El c贸digo de Python para la funci贸n transversal es el siguiente. Agregue la funci贸n a continuaci贸n a la LinkedListclase que creamos en la 煤ltima secci贸n.

    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.ref
    

    Veamos qu茅 est谩 sucediendo en la funci贸n anterior. La funci贸n tiene dos partes principales. Primero, verifica si la lista vinculada est谩 vac铆a o no. El siguiente c贸digo comprueba que:

      if self.start_node is None:
            print("List has no element")
            return
    

    Si la lista vinculada est谩 vac铆a, eso significa que no hay ning煤n elemento para iterar. En tales casos, la traverse_list()funci贸n simplemente imprime la declaraci贸n de que la lista no tiene ning煤n elemento.

    De lo contrario, si la lista tiene un elemento, se ejecutar谩 el siguiente c贸digo:

        n = self.start_node
            while n is not None:
                print(n.item , " ")
                n = n.ref
    

    Como dijimos anteriormente, la startvariable contendr谩 una referencia a los primeros nodes. Por lo tanto, inicializamos una variable ncon startvariable. A continuaci贸n, ejecutamos un ciclo que se ejecuta hasta que se nconvierte en ninguno. Dentro del ciclo, imprimimos el elemento almacenado en el node actual y luego establecemos el valor de la nvariable en n.ref, que contiene la referencia al siguiente node. La referencia del 煤ltimo node es Noneporque no hay ning煤n node despu茅s de eso. Por lo tanto, cuando se nconvierte en None, el bucle termina.

    Ahora, tenemos una funci贸n para recorrer una lista vinculada, veamos c贸mo podemos agregar elementos a una sola lista vinculada.

    Insertar elementos

    Dependiendo de la ubicaci贸n donde desee insertar un elemento, existen diferentes formas de insertar elementos en una 煤nica lista vinculada.

    Insertar elementos al principio

    La forma m谩s sencilla de insertar un elemento en una 煤nica lista vinculada es agregar un elemento al principio de la lista. La siguiente funci贸n inserta un elemento al principio de la lista. Agregue esta funci贸n a la LinkedListclase que creamos anteriormente.

        def insert_at_start(self, data):
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node= new_node
    

    En el script anterior, creamos un m茅todo insert_at_start(), el m茅todo acepta un par谩metro, que es b谩sicamente el valor del elemento que queremos insertar. Dentro del m茅todo, simplemente creamos un objeto de la Nodeclase y establecemos su referencia al start_nodeya que start_nodeanteriormente estaba almacenando el primer node, que despu茅s de la inserci贸n de un nuevo node al inicio se convertir谩 en el segundo node.

    Por lo tanto, agregamos la referencia de start_nodea la refvariable del nuevo node. Ahora que new_nodees el primer node, establecemos el valor de la start_nodevariable en new_node.

    Insertar elementos al final

    La siguiente funci贸n se utiliza para agregar un elemento al final de la lista vinculada.

      def insert_at_end(self, data):
            new_node = Node(data)
            if self.start_node is None:
                self.start_node = new_node
                return
            n = self.start_node
            while n.ref is not None:
                n= n.ref
            n.ref = new_node;
    

    En el script anterior, creamos una funci贸n insert_at_end(), que inserta el elemento al final de la lista vinculada. El valor del elemento que queremos insertar se pasa como argumento a la funci贸n. La funci贸n consta de dos partes. Primero comprobamos si la lista enlazada est谩 vac铆a o no, si la lista enlazada est谩 vac铆a, todo lo que tenemos que hacer es establecer el valor de la start_nodevariable en new_nodeobjeto.

    Por otro lado, si la lista ya contiene algunos nodes. Inicializamos una variable ncon el node de inicio. Luego iteramos a trav茅s de todos los nodes en la lista usando un ciclo while como hicimos en el caso de la traverse_listfunci贸n. El ciclo termina cuando llegamos al 煤ltimo node. Luego establecemos la referencia del 煤ltimo node al reci茅n creado new_node.

    Agrega la insert_at_end()funci贸n a la LinkedListclase.

    Insertar art铆culo despu茅s de otro art铆culo

    Es posible que necesitemos agregar un elemento despu茅s de otro elemento en una sola lista vinculada. Para hacerlo, podemos usar la insert_after_item()funci贸n como se define a continuaci贸n:

        def insert_after_item(self, x, data):
    
            n = self.start_node
            print(n.ref)
            while n is not None:
                if n.item == x:
                    break
                n = n.ref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.ref = n.ref
                n.ref = new_node
    

    La insert_after_item()funci贸n acepta dos par谩metros: xy data. El primer par谩metro es el elemento despu茅s del cual desea insertar el nuevo node, mientras que el segundo par谩metro contiene el valor del nuevo node.

    Comenzamos creando una nueva variable ny asign谩ndole una start_nodevariable. A continuaci贸n, recorremos la lista vinculada usando el bucle while. El ciclo while se ejecuta hasta que se nconvierte en None. Durante cada iteraci贸n, verificamos si el valor almacenado en el node actual es igual al valor pasado por el xpar谩metro. Si la comparaci贸n devuelve verdadera, rompemos el ciclo.

    A continuaci贸n, si se encuentra el elemento, la nvariable no lo ser谩 None. La referencia de new_nodese establece en la referencia almacenada por ny la referencia de nse establece en new_node. Agrega la insert_after_item()funci贸n a la LinkesListclase.

    Insertar art铆culo antes que otro art铆culo

        def insert_before_item(self, x, data):
            if self.start_node is None:
                print("List has no element")
                return
    
            if x == self.start_node.item:
                new_node = Node(data)
                new_node.ref = self.start_node
                self.start_node = new_node
                return
    
            n = self.start_node
            print(n.ref)
            while n.ref is not None:
                if n.ref.item == x:
                    break
                n = n.ref
            if n.ref is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.ref = n.ref
                n.ref = new_node
    

    En el script de arriba definimos la insert_before_item()funci贸n. La funci贸n tiene tres partes. Veamos cada parte en detalle.

         if self.start_node is None:
            print("List has no element")
            return
    

    En el script anterior, verificamos si la lista est谩 vac铆a. Si est谩 realmente vac铆o, simplemente imprimimos que la lista no tiene ning煤n elemento y regresamos de la funci贸n.

    A continuaci贸n, comprobamos si el elemento se encuentra en el primer 铆ndice. Mira el siguiente gui贸n:

         if x == self.start_node.item:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
            return
    

    Si el elemento despu茅s del cual queremos insertar un nuevo node se encuentra en el primer 铆ndice. Simplemente establecemos la referencia del node reci茅n insertado en start_nodey luego establecemos el valor de start_nodeen new_node.

    Finalmente, si la lista no lo es Noney el elemento no se encuentra en el primer 铆ndice, creamos una nueva variable ny le asignamos una start_nodevariable. A continuaci贸n, recorremos la lista vinculada usando el bucle while. El ciclo while se ejecuta hasta que se n.refconvierte en None. Durante cada iteraci贸n, verificamos si el valor almacenado en la referencia del node actual es igual al valor pasado por el xpar谩metro. Si la comparaci贸n devuelve verdadera, rompemos el ciclo.

    A continuaci贸n, si se encuentra el elemento, la n.refvariable no lo ser谩 None. La referencia de new_nodese establece en referencia de ny la referencia de nse establece en new_node. Mira el siguiente gui贸n:

        if n.ref is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node
    

    Agrega una insert_before_item()funci贸n a la LinkedListclase.

    Insertar art铆culo en 铆ndice espec铆fico

    A veces, necesitamos insertar un elemento en un 铆ndice espec铆fico, podemos hacerlo con la ayuda del siguiente script:

        def insert_at_index (self, index, data):
            if index == 1:
                new_node = Node(data)
                new_node.ref = self.start_node
                self.start_node = new_node
            i = 1
            n = self.start_node
            while i < index-1 and n is not None:
                n = n.ref
                i = i+1
            if n is None:
                print("Index out of bound")
            else: 
                new_node = Node(data)
                new_node.ref = n.ref
                n.ref = new_node
    

    En el script, primero verificamos si el 铆ndice en el que queremos almacenar el elemento es 1, luego simplemente asignamos start_nodea la referencia de new_nodey luego establecemos el valor de start_nodea new_node.

    A continuaci贸n, ejecute un ciclo while que se ejecutar谩 hasta que el contador isea 鈥嬧媘ayor o igual que el index-1. Por ejemplo, si desea agregar un nuevo node al tercer 铆ndice. Durante la primera iteraci贸n del ciclo while, ise convertir谩 en 2 y el node actualmente iterado ser谩 ‘2’. El bucle no se ejecutar谩 de nuevo ya ique ahora es 2, que es igual a index-1 (3-1 = 2). Por lo tanto, el bucle se romper谩. A continuaci贸n, agregamos un nuevo node despu茅s del node actualmente iterado (que es el node 2), por lo tanto, el nuevo node se agrega en el 铆ndice.

    Es importante mencionar que si el 铆ndice o la ubicaci贸n pasada como argumento es mayor que el tama帽o de la lista vinculada, se le mostrar谩 al usuario un mensaje que indica que el 铆ndice est谩 fuera de rango o fuera de l铆mite.

    Prueba de funciones de inserci贸n

    Ahora que hemos definido todas nuestras funciones de inserci贸n, prob茅moslas.

    Primero, cree un objeto de la clase de lista vinculada de la siguiente manera:

    new_linked_list = LinkedList()
    

    A continuaci贸n, primero llamemos a la insert_at_end()funci贸n para agregar tres elementos a la lista vinculada. Ejecute el siguiente script:

    new_linked_list.insert_at_end(5)
    new_linked_list.insert_at_end(10)
    new_linked_list.insert_at_end(15)
    

    Para ver si los elementos se han insertado realmente, recorramos la lista vinculada usando la funci贸n de recorrido.

    new_linked_list.traverse_list()
    

    Deber铆a ver el siguiente resultado:

    5
    10
    15
    

    A continuaci贸n, agreguemos un elemento al principio:

    new_linked_list.insert_at_start(20)
    

    Ahora, si recorre la lista, deber铆a ver el siguiente resultado:

    20
    5
    10
    15
    

    Agreguemos un nuevo elemento 17 despu茅s del elemento 10:

    new_linked_list.insert_after_item(10, 17)
    

    Atravesar la lista devuelve ahora la siguiente salida:

    20
    5
    10
    17
    15 
    

    Puede ver 17 insertados despu茅s de 10.

    Insertemos ahora otro elemento 25 antes del elemento 17 usando la insert_before_item()funci贸n como se muestra a continuaci贸n:

    new_linked_list.insert_before_item(17, 25)
    

    Ahora la lista contendr谩 los siguientes elementos:

    20
    5
    10
    25
    17
    15
    

    Finalmente, agreguemos un elemento en la tercera ubicaci贸n, que actualmente est谩 ocupada por 10. Ver谩 que 10 mover谩 una ubicaci贸n hacia adelante y el nuevo elemento se insertar谩 en su lugar. La insert_at_index()funci贸n se puede utilizar para este prop贸sito. El siguiente script inserta el elemento 8en el 铆ndice del tercer 铆ndice de la lista.

    new_linked_list.insert_at_index(3,8)
    

    Ahora, si recorre la lista, deber铆a ver el siguiente resultado:

    20
    5
    8
    10
    25
    17
    15
    

    Y con eso, hemos probado todas nuestras funciones de inserci贸n. Actualmente tenemos 7 elementos en nuestra lista. Escribamos una funci贸n que devuelva el n煤mero de elementos en una lista vinculada.

    Contando elementos

    La siguiente funci贸n cuenta el n煤mero total de elementos.

        def get_count(self):
            if self.start_node is None:
                return 0;
            n = self.start_node
            count = 0;
            while n is not None:
                count = count + 1
                n = n.ref
            return count
    

    En el script anterior creamos una get_count()funci贸n que simplemente cuenta el n煤mero de elementos en la lista vinculada. La funci贸n simplemente atraviesa todos los nodes de la matriz e incrementa un contador usando el bucle while. Al final del ciclo, el contador contiene el n煤mero total de elementos en el ciclo.

    Agregue la funci贸n anterior a la LinkedListclase, compile la LinkedListclase y luego inserte algunos elementos en el LinkedListcomo hicimos en la 煤ltima secci贸n. Ten铆amos 7 elementos en nuestra lista vinculada, al final de la 煤ltima secci贸n.

    Usemos la get_count()funci贸n para obtener el n煤mero total de elementos en la lista:

    new_linked_list.get_count()
    

    Deber铆a ver la cantidad de elementos en su lista vinculada en la salida.

    Alternativamente, otra forma de obtener el ‘recuento’ de la lista ser铆a rastrear el n煤mero de elementos insertados y eliminados de la lista en una simple variable de contador perteneciente a la LinkedListclase. Esto funciona bien y es m谩s r谩pido que el get_countm茅todo anterior, si la estructura de datos de la lista subyacente no se puede manipular desde fuera de la clase.

    Elementos de b煤squeda

    La b煤squeda de un elemento es bastante similar a contar o recorrer una lista vinculada, todo lo que tiene que hacer es comparar el valor que se buscar谩 con el valor del node durante cada iteraci贸n. Si se encuentra el valor, imprima que se encuentra el valor y rompa el ciclo. Si el elemento no se encuentra despu茅s de atravesar todos los nodes, simplemente imprima que el elemento no se encuentra.

    El gui贸n para el search_item()es el siguiente:

        def search_item(self, x):
            if self.start_node is None:
                print("List has no elements")
                return
            n = self.start_node
            while n is not None:
                if n.item == x:
                    print("Item found")
                    return True
                n = n.ref
            print("item not found")
            return False
    

    Agregue la funci贸n anterior a la LinkedListclase. Busquemos un elemento en la lista creada anteriormente. Ejecute el siguiente script:

    new_linked_list.search_item(5)
    

    Dado que insertamos 5 en nuestra lista vinculada, la funci贸n anterior devolver谩 verdadero. La salida se ver谩 as铆:

    Item found
    True
    

    Crear una lista vinculada

    Aunque podemos agregar elementos uno por uno usando cualquiera de las funciones de inserci贸n. Creemos una funci贸n que le pida al usuario que ingrese la cantidad de elementos en el node y luego el elemento individual e ingrese ese elemento en la lista vinculada.

        def make_new_list(self):
            nums = int(input("How many nodes do you want to create: "))
            if nums == 0:
                return
            for i in range(nums):
                value = int(input("Enter the value for the node:"))
                self.insert_at_end(value)
    

    En el script anterior, la make_new_list()funci贸n primero le pide al usuario el n煤mero de elementos de la lista. Luego, usando un bucle for, se le pide al usuario que ingrese el valor para cada node, que luego se inserta en la lista vinculada usando la insert_at_end()funci贸n.

    La siguiente captura de pantalla muestra la make_new_list()funci贸n en acci贸n.

    Eliminar elementos

    En esta secci贸n, veremos las diferentes formas de eliminar un elemento de una 煤nica lista vinculada.

    Eliminaci贸n desde el inicio

    Eliminar un elemento o elemento desde el principio de la lista vinculada es sencillo. Tenemos que establecer la referencia del start_nodeal segundo node, lo que podemos hacer simplemente asignando el valor de la referencia del node de inicio (que apunta al segundo node) al node de inicio como se muestra a continuaci贸n:

        def delete_at_start(self):
            if self.start_node is None:
                print("The list has no element to delete")
                return 
            self.start_node = self.start_node.ref
    

    En el script anterior, primero verificamos si la lista est谩 vac铆a o no. Si la lista est谩 vac铆a mostramos el mensaje de que la lista no tiene ning煤n elemento para eliminar. De lo contrario, asignamos el valor de start_node.refal start_node. El start_nodeahora apuntar谩 hacia el segundo elemento. Agrega la delete_at_start()funci贸n a la LinkedListclase.

    Eliminaci贸n al final

    Para eliminar un elemento del final de la lista, simplemente tenemos que iterar a trav茅s de la lista enlazada hasta el pen煤ltimo elemento, y luego debemos establecer la referencia del pen煤ltimo elemento a ninguno, lo que convertir谩 el pen煤ltimo elemento a 煤ltimo elemento.

    El script de la funci贸n delete_at_endes el siguiente:

        def delete_at_end(self):
            if self.start_node is None:
                print("The list has no element to delete")
                return
    
            n = self.start_node
            while n.ref.ref is not None:
                n = n.ref
            n.ref = None
    

    Agregue el script anterior a la LinkedList()clase.

    Eliminaci贸n por valor de art铆culo

    Para eliminar el elemento por valor, primero tenemos que encontrar el node que contiene el elemento con el valor especificado y luego eliminar el node. Encontrar el elemento con el valor especificado es bastante similar a buscar el elemento. Una vez que se encuentra el elemento que se va a eliminar, la referencia del node antes del elemento se establece en el node que existe despu茅s del elemento que se elimina. Mira el siguiente gui贸n:

      def delete_element_by_value(self, x):
        if self.start_node is None:
            print("The list has no element to delete")
            return
    
        # Deleting first node 
        if self.start_node.item == x:
            self.start_node = self.start_node.ref
            return
    
        n = self.start_node
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
    
        if n.ref is None:
            print("item not found in the list")
        else:
            n.ref = n.ref.ref
    

    En el script anterior, primero verificamos si la lista est谩 vac铆a. A continuaci贸n, comprobamos si el elemento a eliminar se encuentra al inicio de la lista enlazada. Si el elemento se encuentra al principio, lo eliminamos estableciendo el primer node en la referencia del primer node (que b谩sicamente se refiere al segundo node).

    Finalmente, si el elemento no se encuentra en el primer 铆ndice, iteramos a trav茅s de la lista vinculada y verificamos si el valor del node que se itera es igual al valor que se eliminar谩. Si la comparaci贸n devuelve verdadera, establecemos la referencia del node anterior al node que existe despu茅s del node que se est谩 eliminando.

    Prueba de funciones de eliminaci贸n

    Probemos las funciones de eliminaci贸n que acabamos de crear. Pero antes de eso, agregue algunos datos ficticios a nuestra lista vinculada usando el siguiente script:

    new_linked_list.insert_at_end(10)
    new_linked_list.insert_at_end(20)
    new_linked_list.insert_at_end(30)
    new_linked_list.insert_at_end(40)
    new_linked_list.insert_at_end(50)
    

    El script anterior inserta 5 elementos en una lista vinculada. Si recorre la lista, deber铆a ver los siguientes elementos:

    10
    20
    30
    40
    50
    

    Primero eliminemos un elemento desde el principio:

    new_linked_list.delete_at_start()
    

    Ahora, si recorre la lista, deber铆a ver el siguiente resultado:

    20
    30
    40
    50 
    

    Eliminemos un elemento del final ahora:

    new_linked_list.delete_at_end()
    

    La lista ahora contiene los siguientes elementos:

    20
    30
    40
    

    Finalmente, eliminemos un elemento por valor, digamos 30.

    new_linked_list.delete_element_by_value(30)
    

    Ahora, si recorre la lista, no deber铆a ver el elemento 30.

    Inversi贸n de una lista vinculada

    Para invertir una lista vinculada, debe tener tres variables prev, ny next. El prevhar谩 un seguimiento del node anterior, el nexthar谩 un seguimiento del siguiente node ny corresponder谩 al node actual.

    Comenzamos un ciclo while asignando el node inicial a la variable ny la prevvariable se inicializa a none. El ciclo se ejecuta hasta que se nconvierte en ninguno. Dentro del ciclo while, debe realizar las siguientes funciones.

    • Asignar el valor de la referencia del node actual a next.
    • Establezca el valor de referencia del node actual nalprev
    • Establece la prevvariable en el node actual n.
    • Establezca el node actual nen el valor de nextnode.

    Al final del ciclo, la prevvariable apuntar谩 al 煤ltimo node, necesitamos convertirlo en el primer node, por lo que establecemos la self.start_nodevariable de valor en prev. El bucle while har谩 que cada node apunte a su node anterior, lo que dar谩 como resultado una lista enlazada invertida. El gui贸n es el siguiente:

        def reverse_linkedlist(self):
            prev = None
            n = self.start_node
            while n is not None:
                next = n.ref
                n.ref = prev
                prev = n
                n = next
            self.start_node = prev
    

    Agregue la funci贸n anterior a la LinkedListclase. Cree una lista vinculada de n煤meros aleatorios y luego vea si puede revertirla usando la reverse_linkedlist()funci贸n.

    Conclusi贸n

    En este art铆culo, comenzamos nuestra discusi贸n sobre una sola lista vinculada. Vimos cu谩les son las diferentes funciones que se pueden realizar en la lista vinculada, como recorrer una lista vinculada, insertar elementos en una lista vinculada, buscar y contar elementos de la lista vinculada, eliminar elementos de una lista vinculada y revertir una sola lista vinculada.

    Esta es la Parte 1 de la serie de art铆culos de la lista vinculada. En la siguiente parte (pr贸ximamente), veremos c贸mo ordenar una sola lista vinculada, c贸mo fusionar listas vinculadas ordenadas y c贸mo eliminar ciclos de una sola lista vinculada.

     

    Etiquetas:

    Deja una respuesta

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