Listas vinculadas de Python

Una lista enlazada es una de las estructuras de datos más comunes utilizadas en informática. También es uno de los más simples, y también es fundamental para la alta ...

Una lista enlazada es una de las estructuras de datos más comunes utilizadas en informática. También es uno de los más simples y 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 únicos que están conectados a través de referencias. Los programadores de C conocen esto como punteros. Por ejemplo, un elemento de datos puede consistir en datos de direcciones, datos geográficos, datos geométricos, información de enrutamiento o detalles de transacciones. Por lo general, cada elemento de la lista enlazada tiene el mismo tipo de datos que es específico de la lista.

Un solo elemento de la lista se llama nodo. Los nodos 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 punteros de un nodo al siguiente. Es común marcar el final de la lista con un elemento NIL, representado por el equivalente de Python Ninguno.

Lista de enlace único{.img-responsive}

Figura 1: lista de un solo enlace

Existen dos tipos de listas - single y listas de doble enlace. Un nodo en una lista de enlace único solo apunta al siguiente elemento de la lista, mientras que un nodo en una lista de enlace doble también apunta al nodo anterior. La estructura de datos ocupa más espacio porque necesitará una variable adicional para almacenar la referencia adicional.

Lista con doble enlace{.img-responsive}

Figura 2: Lista de doble enlace

Una lista de un solo enlace se puede recorrer de principio a fin, mientras que recorrer hacia atrás no es tan fácil como eso. Por el contrario, una lista de doble enlace permite atravesar los nodos en ambas direcciones al mismo costo, sin importar con qué nodo comience. Además, agregar y eliminar nodos, así como dividir listas de un solo enlace, se realiza en no más de dos pasos. En una lista doblemente enlazada, se deben cambiar cuatro punteros.

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

En este artículo, seguiremos los pasos para crear nuestra propia estructura de datos de lista enlazada. Primero creamos una estructura de datos correspondiente para el nodo. En segundo lugar, aprenderá a implementar y utilizar una lista de enlace simple y, finalmente, una lista de enlace doble.

Paso 1: Nodo como estructura de datos

Para tener una estructura de datos con la que podamos trabajar, definimos un nodo. Un nodo 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 nodo y siguiente para almacenar la referencia al siguiente nodo en la lista. Además, un nodo tiene los siguientes métodos y propiedades:

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

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

Listado 1: La clase ListNode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 nodo es tan simple como eso, e instancia un objeto de la clase ListNode:

Listado 2: Instanciación de nodos

1
2
3
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

Habiendo hecho eso, tenemos disponibles tres instancias de la clase ListNode. Estas instancias representan tres nodos independientes que contienen los valores 15 (entero), 8.2 (flotante) y "Berlín" (cadena).

Paso 2: creación de una clase para una lista de enlace único {#paso2creacióndeunaclaseparaunalistadeenlace único}

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

  • __init__(): iniciar un objeto
  • list_length(): devuelve el número de nodos
  • output_list(): muestra los valores del nodo
  • add_list_item(): agrega un nodo al final de la lista
  • unordered_search(): busca en la lista los nodos con un valor específico
  • remove_list_item_by_id(): elimina el nodo según su id

Revisaremos cada uno de estos métodos paso a paso.

El método __init__() define dos variables de clase internas llamadas head y tail. Representan los nodos inicial y final de la lista. Inicialmente, tanto cabeza como cola tienen el valor Ninguno siempre que la lista esté vacía.

Listado 3: La clase SingleLinkedList (primera parte)

1
2
3
4
5
6
7
class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

Paso 3: agregar nodos

La adición de elementos a la lista se realiza mediante add_list_item(). Este método requiere un nodo como parámetro adicional. Para asegurarse de que es un nodo adecuado (una instancia de la clase ListNode), el parámetro primero se verifica utilizando la función integrada de Python isinstance(). Si tiene éxito, el nodo 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 nodo se convierte en el encabezado de la lista. Si un nodo ya está en la lista, el valor de la cola se ajusta en consecuencia.

Listado 4: La clase SingleLinkedList (segunda parte)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    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

El método list_length() cuenta los nodos y devuelve la longitud de la lista. Para pasar de un nodo al siguiente en la lista, entra en juego la propiedad del nodo self.next y devuelve el enlace al siguiente nodo. El conteo de nodos se realiza en un ciclo while siempre que no lleguemos al final de la lista, que se representa mediante un enlace Ninguno al siguiente nodo.

Listado 5: La clase SingleLinkedList (parte tres)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
    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 nodo usando la propiedad del nodo data. De nuevo, para pasar de un nodo al siguiente se utiliza el enlace que se proporciona a través de la propiedad siguiente.

Listado 6: La clase SingleLinkedList (parte cuatro)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    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

Basándonos en la clase SingleLinkedList podemos crear una lista adecuada llamada pista y jugar con sus métodos como ya se describió anteriormente en Listados 3-6. Por lo tanto, creamos cuatro nodos de lista, los evaluamos en un bucle for y generamos el contenido de la lista. Listado 7 muestra cómo programar eso, y Listado 8 muestra el resultado.

Listado 7: Creación de nodos y salida de lista

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 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: Agregando nodos a la lista

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
$ 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 el valor a buscar. El encabezado de la lista es el punto de partida.

Mientras buscamos contamos los nodos. Para indicar una coincidencia usamos el número de nodo correspondiente. El método unordered_search() devuelve una lista de números de nodo que representan las coincidencias. Como ejemplo, tanto el primer como el cuarto nodo 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()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    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 elemento de la lista

Eliminar un nodo de la lista requiere ajustar solo una referencia: la que apunta al nodo que se eliminará ahora debe apuntar al siguiente. Esta referencia la conserva el nodo que se va a eliminar y debe ser reemplazada. En segundo plano, el recolector de basura de Python se ocupa 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 nodo similar al valor devuelto por unordered_search().

Listado 10: Eliminar un nodo por número de nodo

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    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 con doble enlace

Para crear una lista con doble enlace, parece natural extender la clase ListNode creando una referencia adicional al nodo anterior. Esto afecta los métodos para agregar, eliminar y clasificar nodos. Como se muestra en el Listado 11, se ha agregado una nueva propiedad llamada anterior para almacenar el puntero de referencia al nodo anterior en la lista. Cambiaremos nuestros métodos para usar esta propiedad para rastrear y atravesar nodos también.

Listado 11: Clase de nodo de lista extendida

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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 nodos requiere un poco más de acción. Listado 13 muestra cómo implementar eso:

Listado 13: Agregar nodos en una lista de doble enlace

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    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

La eliminación de un elemento de la lista debe tener en cuenta costos similares. Listado 14 muestra cómo hacerlo:

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

 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
    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 de Python.

Listado 15: Construyendo una lista de doble enlace

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# 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 con un solo enlace. El único cambio es la estructura de datos interna.

Paso 7: creación de listas de enlaces dobles con deque

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

Los deques son una generalización de pilas y colas (el nombre se pronuncia "deck" y es la abreviatura de "cola de dos extremos"). Los deques admiten adiciones y elementos emergentes seguros para subprocesos y eficientes en memoria desde cualquier lado del deque con aproximadamente el mismo rendimiento de 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 (fin)
  • append_left(): agrega un elemento al lado izquierdo de la lista (encabezado)
  • clear(): elimina todos los elementos de la lista
  • count(): cuenta el número de elementos con un cierto valor
  • index(): busca la primera aparición de un valor en la lista
  • insert(): inserta un elemento en la lista
  • pop(): elimina un elemento del lado derecho de una lista (fin)
  • popleft(): elimina un elemento del lado izquierdo de una lista (encabezado)
  • remove(): elimina un elemento de la lista
  • reverse(): invertir la lista

La estructura de datos subyacente de deque es una lista de Python con doble enlace. El primer nodo de la lista tiene el índice 0. El uso de deque conduce a una simplificación significativa de la clase ListNode. Lo único que mantenemos es la variable de clase data para almacenar el valor del nodo. Listado 16 es el siguiente:

Listado 16: Clase ListNode con deque (simplificado)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 nodos no cambia y es similar al Listado 2. Con este conocimiento en mente, creamos una lista de nodos de la siguiente manera:

Listado 17: Crear una lista con deque

1
2
3
4
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 método append_left() como muestra el Listado 18:

Listado 18: Agregando un elemento al principio de una lista

1
2
3
4
5
6
# 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)

De manera similar, append() agrega un nodo al final de la lista como muestra el Listado 19:

Listado 19: Agregar un elemento al final de la lista

1
2
3
4
5
6
# 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, podría agregar un contador de nodos, una variable de clase que simplemente contiene la cantidad de nodos en la lista. Esto reduce la determinación de la longitud de la lista a una sola operación con O(1), y no es necesario recorrer toda la lista.

Para obtener más información e implementaciones alternativas, puede consultar aquí:

Agradecimientos

El autor desea agradecer a Geroldo Rupprecht y Mandy Neumeyer por su apoyo y comentarios durante la preparación de este artículo. ulo.