Listas vinculadas de Python

    Una lista enlazada es una de las estructuras de datos m谩s comunes que se utilizan en inform谩tica. Tambi茅n es uno de los m谩s simples y tambi茅n es fundamental para estructuras de nivel superior como pilas, b煤feres circulares y colas.

    En t茅rminos generales, una lista es una colecci贸n de elementos de datos individuales que est谩n conectados mediante referencias. Los programadores de C conocen esto como punteros. Por ejemplo, un elemento de datos puede constar de datos de direcciones, datos geogr谩ficos, datos geom茅tricos, informaci贸n de enrutamiento o detalles de transacciones. Normalmente, cada elemento del lista enlazada tiene el mismo tipo de datos que es espec铆fico de la lista.

    Un solo elemento de la lista se llama node. Los nodes no son como matrices que se almacenan secuencialmente en la memoria. En cambio, es probable que los encuentre en diferentes segmentos de memoria, que puede encontrar siguiendo los indicadores de un node al siguiente. Es com煤n marcar el final de la lista con un elemento NIL, representado por el equivalente de Python None.

    Figura 1: Lista de un solo enlace

    Existen dos tipos de listas: simple y listas de doble enlace. Un node en una lista de un solo enlace solo apunta al siguiente elemento de la lista, mientras que un node en una lista de doble enlace tambi茅n apunta al node anterior. La estructura de datos ocupa m谩s espacio porque necesitar谩 una variable adicional para almacenar la referencia adicional.

    Figura 2: Lista de doble enlace

    Una lista de un solo enlace se puede recorrer de la cabeza a la cola, mientras que recorrer hacia atr谩s no es tan f谩cil como eso. Por el contrario, una lista de doble enlace permite atravesar los nodes en ambas direcciones al mismo costo, sin importar con qu茅 node comience. Adem谩s, la adici贸n y eliminaci贸n de nodes, as铆 como la divisi贸n de listas de un solo enlace, se realiza en no m谩s de dos pasos. En una lista de doble enlace, deben cambiarse cuatro punteros.

    El lenguaje Python no contiene un tipo de datos predefinido para listas vinculadas. Para hacer frente a esta situaci贸n, tenemos que crear nuestro propio tipo de datos o tenemos que hacer uso de m贸dulos de Python adicionales que proporcionan una implementaci贸n de dicho tipo de datos.

    En este art铆culo, repasaremos los pasos para crear nuestra propia estructura de datos de lista vinculada. Primero creamos una estructura de datos correspondiente para el node. En segundo lugar, aprender谩 a implementar y utilizar tanto una lista de enlace 煤nico como, finalmente, una lista de enlace doble.

    Paso 1: node como estructura de datos

    Para tener una estructura de datos con la que podamos trabajar, definimos un node. Un node se implementa como una clase llamada ListNode. La clase contiene la definici贸n para crear una instancia de objeto, en este caso, con dos variables: data para mantener el valor del node, y next para almacenar la referencia al siguiente node de la lista. Adem谩s, un node tiene los siguientes m茅todos y propiedades:

    • __init_(): inicializa el node con los datos
    • self.data: el valor almacenado en el node
    • self.next: el puntero de referencia al siguiente node
    • has_value(): compara un valor con el valor del node

    Estos m茅todos aseguran que podamos inicializar un node correctamente con nuestros datos (__init__()), y cubren tanto la extracci贸n como el almacenamiento de datos (a trav茅s del self.data propiedad), as铆 como obtener la referencia al node conectado (a trav茅s del self.next propiedad). El m茅todo has_value() nos permite comparar el valor del node con el valor de un node diferente.

    Listado 1: La clase ListNode

    class ListNode:
        def __init__(self, data):
            "constructor to initiate this object"
            
            # store data
            self.data = data
            
            # store reference (next item)
            self.next = None
            return
        
        def has_value(self, value):
            "method to compare the value with the node data"
            if self.data == value:
                return True
            else:
                return False
    

    Crear un node es tan simple como eso, y crea una instancia de un objeto de clase. ListNode:

    Listado 2: Creaci贸n de instancias de nodes

    node1 = ListNode(15)
    node2 = ListNode(8.2)
    node3 = ListNode("Berlin")
    

    Una vez hecho esto, tenemos disponibles tres instancias del ListNode clase. Estas instancias representan tres nodes independientes que contienen los valores 15 (entero), 8.2 (flotante) y “Berl铆n” (cadena).

    Paso 2: creaci贸n de una clase para una lista unificada

    Como segundo paso, definimos una clase llamada SingleLinkedList que cubre los m茅todos necesarios para administrar nuestros nodes de lista. Contiene estos m茅todos:

    • __init__(): iniciar un objeto
    • list_length(): devuelve el n煤mero de nodes
    • output_list(): genera los valores del node
    • add_list_item(): agrega un node al final de la lista
    • unordered_search(): busca en la lista los nodes con un valor especificado
    • remove_list_item_by_id(): elimina el node seg煤n su id

    Repasaremos cada uno de estos m茅todos paso a paso.

    los __init__() El m茅todo define dos variables de clase internas llamadas head y tail. Representan los nodes inicial y final de la lista. Inicialmente, ambos head y tail tener el valor None siempre que la lista est茅 vac铆a.

    Listado 3: La clase SingleLinkedList (parte uno)

    class SingleLinkedList:
        def __init__(self):
            "constructor to initiate this object"
            
            self.head = None
            self.tail = None
            return
    

    Paso 3: agregar nodes

    La adici贸n de elementos a la lista se realiza mediante add_list_item(). Este m茅todo requiere un node como par谩metro adicional. Para asegurarse de que sea un node adecuado (una instancia de clase ListNode) el par谩metro se verifica primero usando la funci贸n incorporada de Python isinstance(). Si tiene 茅xito, el node se agregar谩 al final de la lista. Si item no es un ListNode, entonces se crea uno.

    En caso de que la lista est茅 (todav铆a) vac铆a, el nuevo node se convierte en el encabezado de la lista. Si un node ya est谩 en la lista, entonces el valor de tail se ajusta en consecuencia.

    Listado 4: La clase SingleLinkedList (segunda parte)

        def add_list_item(self, item):
            "add an item at the end of the list"
            
            if not isinstance(item, ListNode):
                item = ListNode(item)
    
            if self.head is None:
                self.head = item
            else:
                self.tail.next = item
    
            self.tail = item
                
            return
    

    los list_length() El m茅todo cuenta los nodes y devuelve la longitud de la lista. Para pasar de un node al siguiente en la lista, la propiedad del node self.next entra en juego y devuelve el enlace al siguiente node. El conteo de los nodes se realiza en un bucle while siempre que no lleguemos al final de la lista, que est谩 representada por un None enlace al siguiente node.

    Listado 5: La clase SingleLinkedList (tercera parte)

        def list_length(self):
            "returns the number of list items"
            
            count = 0
            current_node = self.head
            
            while current_node is not None:
                # increase counter by one
                count = count + 1
                
                # jump to the linked node
                current_node = current_node.next
                
            return count
    

    El m茅todo output_list() genera los valores del node utilizando la propiedad del node data. Nuevamente, para ir de un node al siguiente se utiliza el enlace que se proporciona a trav茅s de next propiedad.

    Listado 6: La clase SingleLinkedList (cuarta parte)

        def output_list(self):
            "outputs the list (the value of the node, actually)"
            
             current_node = self.head
            
            while current_node is not None:
                print(current_node.data)
                
                # jump to the linked node
                current_node = current_node.next
                
            return
    

    Basado en la clase SingleLinkedList podemos crear una lista adecuada llamada tracky juegue con sus m茅todos como ya se describi贸 anteriormente en los listados 3-6. Por lo tanto, creamos cuatro nodes de lista, los evaluamos en un for bucle y muestra el contenido de la lista. El Listado 7 le muestra c贸mo programar eso, y el Listado 8 muestra la salida.

    Listado 7: Creaci贸n de nodes y salida de lista

    # create four single nodes
    node1 = ListNode(15)
    node2 = ListNode(8.2)
    item3 = "Berlin"
    node4 = ListNode(15)
    
    track = SingleLinkedList()
    print("track length: %i" % track.list_length())
    
    for current_item in [node1, node2, item3, node4]:
        track.add_list_item(current_item)
        print("track length: %i" % track.list_length())
        track.output_list()
    

    El resultado es el siguiente y muestra c贸mo crece la lista:

    Listado 8: Agregar nodes a la lista

    $ python3 simple-list.py
    track length: 0
    track length: 1
    15
    track length: 2
    15
    8.2
    track length: 3
    15
    8.2
    Berlin
    track length: 4
    15
    8.2
    Berlin
    15
    

    Paso 4: b煤squeda en la lista

    La b煤squeda en toda la lista se realiza mediante el m茅todo unordered_search(). Requiere un par谩metro adicional para buscar el valor. El encabezado de la lista es el punto de partida.

    Mientras buscamos contamos los nodes. Para indicar una coincidencia usamos el n煤mero de node correspondiente. El m茅todo unordered_search() devuelve una lista de n煤meros de node que representan las coincidencias. Como ejemplo, tanto el primer como el cuarto node contienen el valor 15. La b煤squeda de 15 da como resultado una lista con dos elementos: [1, 4].

    Listado 9: El m茅todo de b煤squeda unordered_search ()

        def unordered_search (self, value):
            "search the linked list for the node that has this value"
            
            # define current_node
            current_node = self.head
            
            # define position
            node_id = 1
            
            # define list of results
            results = []
            
            while current_node is not None:
                if current_node.has_value(value):
                    results.append(node_id)
                    
                # jump to the linked node
                current_node = current_node.next
                node_id = node_id + 1
            
            return results
    

    Paso 5: eliminar un art铆culo de la lista

    Eliminar un node de la lista requiere ajustar solo una referencia: la que apunta al node que se eliminar谩 ahora debe apuntar al siguiente. Esta referencia la conserva el node que se va a eliminar y debe reemplazarse. En segundo plano, el recolector de basura de Python se encarga de los objetos sin referencia y los ordena.

    El siguiente m茅todo se llama remove_list_item_by_id(). Como par谩metro se refiere al n煤mero del node similar al valor devuelto por unordered_search().

    Listado 10: Eliminar un node por n煤mero de node

        def remove_list_item_by_id(self, item_id):
            "remove the list item with the item id"
            
            current_id = 1
            current_node = self.head
            previous_node = None
            
            while current_node is not None:
                if current_id == item_id:
                    # if this is the first node (head)
                    if previous_node is not None:
                        previous_node.next = current_node.next
                    else:
                        self.head = current_node.next
                        # we don't have to look any further
                        return
                
                # needed for the next iteration
                previous_node = current_node
                current_node = current_node.next
                current_id = current_id + 1
            
            return
    

    Paso 6: creaci贸n de una lista de enlace doble

    Para crear una lista de doble enlace, se siente natural solo extender el ListNode class creando una referencia adicional al node anterior. Esto afecta los m茅todos para agregar, eliminar y ordenar nodes. Como se muestra en el Listado 11, una nueva propiedad llamada previous se ha agregado para almacenar el puntero de referencia al node anterior en la lista. Cambiaremos nuestros m茅todos para usar esta propiedad para rastrear y atravesar nodes tambi茅n.

    Listado 11: Clase de node de lista extendida

    class ListNode:
        def __init__(self, data):
            "constructor class to initiate this object"
    
            # store data
            self.data = data
            
            # store reference (next item)
            self.next = None
    
            # store reference (previous item)
            self.previous = None
            return
    
        def has_value(self, value):
            "method to compare the value with the node data"
            if self.data == value:
                return True
            else:
                return False
    
    

    Ahora podemos definir una lista de doble enlace de la siguiente manera:

    Listado 12: una clase DoubleLinkedList

    class DoubleLinkedList:
        def __init__(self):
            "constructor to initiate this object"
    
            self.head = None
            self.tail = None
            return
    
        def list_length(self):
            "returns the number of list items"
            
            count = 0
            current_node = self.head
    
            while current_node is not None:
                # increase counter by one
                count = count + 1
                
                # jump to the linked node
                current_node = current_node.next
            
            return count
    
        def output_list(self):
            "outputs the list (the value of the node, actually)"
            current_node = self.head
    
            while current_node is not None:
                print(current_node.data)
    
                # jump to the linked node
                current_node = current_node.next
            
            return
    
        def unordered_search (self, value):
            "search the linked list for the node that has this value"
    
            # define current_node
            current_node = self.head
    
            # define position
            node_id = 1
    
            # define list of results
            results = []
    
            while current_node is not None:
                if current_node.has_value(value):
                    results.append(node_id)
                
                # jump to the linked node
                current_node = current_node.next
                node_id = node_id + 1
            
            return results
    

    Como se describi贸 anteriormente, agregar nodes requiere un poco m谩s de acci贸n. El Listado 13 muestra c贸mo implementar eso:

    Listado 13: Agregar nodes en una lista de doble enlace

        def add_list_item(self, item):
            "add an item at the end of the list"
    
            if isinstance(item, ListNode):
                if self.head is None:
                    self.head = item
                    item.previous = None
                    item.next = None
                    self.tail = item
                else:
                    self.tail.next = item
                    item.previous = self.tail
                    self.tail = item
            
            return
    

    Eliminar un art铆culo de la lista deben tenerse en cuenta costos similares. El Listado 14 muestra c贸mo hacer eso:

    Listado 14: Eliminar un elemento de una lista de doble enlace

        def remove_list_item_by_id(self, item_id):
            "remove the list item with the item id"
            
            current_id = 1
            current_node = self.head
    
            while current_node is not None:
                previous_node = current_node.previous
                next_node = current_node.next
    
                if current_id == item_id:
                    # if this is the first node (head)
                    if previous_node is not None:
                        previous_node.next = next_node
                        if next_node is not None:
                            next_node.previous = previous_node
                    else:
                        self.head = next_node
                        if next_node is not None:
                            next_node.previous = None
                    # we don't have to look any further
                    return
     
                # needed for the next iteration
                current_node = next_node
                current_id = current_id + 1
                    
            return
    

    El Listado 15 muestra c贸mo usar la clase en un programa Python.

    Listado 15: Creaci贸n de una lista de doble enlace

    # create three single nodes
    node1 = ListNode(15)
    node2 = ListNode(8.2)
    node3 = ListNode("Berlin")
    node4 = ListNode(15)
    
    track = DoubleLinkedList()
    print("track length: %i" % track.list_length())
    
    for current_node in [node1, node2, node3, node4]:
        track.add_list_item(current_node)
        print("track length: %i" % track.list_length())
        track.output_list()
    
    results = track.unordered_search(15)
    print(results)
    
    track.remove_list_item_by_id(4)
    track.output_list()
    

    Como puede ver, podemos usar la clase exactamente como antes, cuando era solo una lista de un solo enlace. El 煤nico cambio es la estructura de datos interna.

    Paso 7: creaci贸n de listas de doble enlace con deque

    Dado que otros ingenieros se han enfrentado al mismo problema, podemos simplificar las cosas para nosotros y utilizar una de las pocas implementaciones existentes disponibles. En Python, podemos usar el deque objeto del collections m贸dulo. Seg煤n la documentaci贸n del m贸dulo:

    Los deques son una generalizaci贸n de pilas y colas (el nombre se pronuncia “baraja” y es la abreviatura de “cola de dos extremos”). Los Deques admiten agregados y estallidos seguros para subprocesos y eficientes en memoria desde cualquier lado del deque con aproximadamente el mismo rendimiento O (1) en cualquier direcci贸n.

    Por ejemplo, este objeto contiene los siguientes m茅todos:

    • append(): agrega un elemento al lado derecho de la lista (final)
    • append_left(): agrega un elemento al lado izquierdo de la lista (encabezado)
    • clear(): eliminar todos los elementos de la lista
    • count(): cuenta el n煤mero de elementos con un valor determinado
    • index(): encuentra la primera aparici贸n de un valor en la lista
    • insert(): inserta un elemento en la lista
    • pop(): eliminar un elemento del lado derecho de una lista (final)
    • popleft(): eliminar un elemento del lado izquierdo de una lista (encabezado)
    • remove(): eliminar un elemento de la lista
    • reverse(): invertir la lista

    La estructura de datos subyacente de deque es una lista de Python que tiene un doble enlace. El primer node de la lista tiene el 铆ndice 0. Usando deque conduce a una simplificaci贸n significativa de la ListNode clase. Lo 煤nico que conservamos es la variable de clase. data para almacenar el valor del node. El Listado 16 es el siguiente:

    Listado 16: Clase ListNode con deque (simplificado)

    from collections import deque
    
    class ListNode:
        def __init__(self, data):
            "constructor class to initiate this object"
            
            # store data
            self.data = data
            
            return
    

    La definici贸n de nodes no cambia y es similar al Listado 2. Con este conocimiento en mente, creamos una lista de nodes de la siguiente manera:

    Listado 17: Creando una lista con deque

    track = deque([node1, node2, node3])
    print("three items (initial list):")
    for item in track:
        print(item.data)
    

    Agregar un elemento al principio de la lista funciona con el append_left() m茅todo como muestra el Listado 18:

    Listado 18: Agregar un elemento al comienzo de una lista

    # add an item at the beginning
    node4 = ListNode(15)
    track.append_left(node4)
    print("four items (added as the head):")
    for item in track:
        print(item.data)
    

    Similar, append() agrega un node al final de la lista como muestra el Listado 19:

    Listado 19: Agregar un elemento al final de la lista

    # add an item at the end
    node5 = ListNode("Moscow")
    print("five items (added at the end):")
    track.append(node5)
    for item in track:
        print(item.data)
    

    Conclusi贸n

    Las listas enlazadas como estructuras de datos son f谩ciles de implementar y ofrecen una gran flexibilidad de uso. Se hace con unas pocas l铆neas de c贸digo. Como mejora, puede agregar un contador de nodes, una variable de clase que simplemente contiene el n煤mero de nodes en la lista. Esto reduce la determinaci贸n de la longitud de la lista a una sola operaci贸n con O (1) y no tiene que recorrer toda la lista.

    Para obtener m谩s informaci贸n e implementaciones alternativas, puede echar un vistazo aqu铆:

    Etiquetas:

    Deja una respuesta

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