Listas vinculadas de Python

L

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í:

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad