Estructura de datos en Python (teoría)

Foto de Alina Grubnyak en Unsplash

Las estructuras de datos, son formas en las que podemos organizar los datos de modo a almacenarlos y acceder a ellos. Es vital conocerlas ya que diferentes estructuras de datos son adecuadas para diferentes tipos de aplicaciones o casos de uso, y nos permite aumentar la eficiencia de nuestros desarrollos.

Si ya estás familiarizado con la programación en Python, y con otros lenguajes, ya conoces las listas y los diccionarios, por lo que ya sabes que las listas y los arreglos (arrays) son estructuras secuenciales a los cuales accedemos mediante índices mientras que a los diccionarios, accedemos a su contenido mediante llaves o claves.

Las estructuras de datos manejan cuatro funciones principales: *

• Entrada de información
• Procesamiento de información
• Mantenimiento de información
• Recuperación de información

La entrada de información se refiere en gran medida a cómo se reciben los datos. ¿Qué tipo de información se puede incluir? ¿Se agregarán los nuevos datos al principio, al final o en algún lugar en medio de los datos existentes? ¿Es necesario actualizar o destruir un punto de datos existente?

El procesamiento se trata de cómo se manipulan los datos en la estructura de datos. Esto puede ocurrir simultáneamente o como resultado de otros procesos que manejan las estructuras de datos. ¿Cómo deben cambiar los datos existentes que se han almacenado para adaptarse a los datos nuevos, actualizados o eliminados?

El mantenimiento se centra en cómo se organizan los datos dentro de la estructura. ¿Qué relaciones deben mantenerse entre los datos? ¿Cuánta memoria debe reservar (asignar) el sistema para acomodar los datos?

La recuperación se dedica a encontrar y devolver los datos almacenados en la estructura. ¿Cómo podemos acceder a esa información de nuevo? ¿Qué pasos debe seguir la estructura de datos para devolvernos la información?

Los diferentes tipos y casos de uso de datos se adaptarán mejor a las diferentes formas de ingreso, procesamiento, almacenamiento y recuperación. Es por eso que tenemos varias estructuras de datos para elegir. _{(*fuente: codecademy.com)}

Nodos

Los nodos son los bloques fundamentales de construcción de muchas estructuras de datos. Gracias a los nodos, se conforman las listas enlazadas, colas, pilas, árboles y muchos más.

Un nodo básicamente contiene:

• un dato (puede ser cualquier tipo de dato u objeto).
• un puntero o link, usado para apuntar a otros nodos.

En el ejemplo de arriba, vemos un ejemplo. El nodo_e tiene como dato un arreglo [33, 45, 63] y un puntero, que lo enlaza con el nodo_f.

Normalmente, las estructuras de datos implementan nodos con uno o más enlaces. Si el link de un nodo, o el puntero hace referencia a Null, significa que este es el fin del nodo o el último nodo del recorrido en la lista o ruta de enlaces que estuvimos recorriendo.

Abajo presentamos diferentes maneras en las que un nodo podría vincularse con otros. (Estos ejemplos no denotan todos los casos posibles).

Enlace de Nodos

_{(fuente: codecademy.com)}

A menudo, debido a la estructura de datos, los nodos solo pueden estar vinculados a otro nodo. Esto hace que sea muy importante considerar cómo implementa la modificación o eliminación de nodos de una estructura de datos.

Si elimina sin darse cuenta el enlace único a un nodo, los datos de ese nodo y los nodos vinculados podrían “perderse” en su aplicación. Cuando esto le sucede a un nodo, se denomina nodo huérfano.

Examine los nodos en el diagrama:

Tenemos que tener en cuenta que a parte de conocer comando básicos y como utilizar las herramientas del lenguaje de programación, también debemos considerar el uso de una adecuada estructura de datos para la solución que estamos desarrollando, ya que de esto dependerá que la misma sea sostenible en el tiempo y eficiente en términos de uso de recursos.

Como implementamos Nodos en Python?

Para el siguiente caso de ejemplo, vamos a diseñar la siguiente implementación.

Detalles de diseño.

• El dato de cada nodo será definido en la instanciación del mismo y será inmutable, es decir que no se podrá actualizar.
• El link del nodo no será definido en la instanciación del nodo y si podrá ser modificado.

¿Que hace que sea inmutable o no? Solamente si es que definimos métodos que permitan actualizar estas propiedades).

Observación: Al momento de su implementación, este ejemplo fue escrito en Python3, en su versión 3.9.2.

EJERCICIO DE EJEMPLO

• Definimos nuestra clase Nodo.
• Definimos el constructor de nuestra clase Nodo.
• Al constructor de nuestra clase le pasamos los parámetros de self (hacemos referencia al objeto actual que estamos instanciando), valor (el valor que estaremos asignando al nodo) y link (notar que le estamos asignando por defecto el valor de None).

class Nodo:
    def __init__(self, valor, link=None):
        self.valor = valor
        self.link = link

A continuación, necesitamos definir los métodos para poder acceder al valor y al link de nuestro nodo.

• Definimos el método ver_valor retornando el valor del objeto nodo actual seleccionado y el método ver_link que retornará el link del mismo.

    def ver_valor(self):
        return self.valor
    
    def ver_link(self):
        return self.link

Agregamos método para modificar el link de nuestro nodo.

• Definimos el método set_link.

    def set_link(self, link):
        self.link = link

Con esto ya tenemos construida nuestra clase Nodo y nuestros métodos. Ahora podemos instanciarlos.

Para este ejemplo, vamos a crear 3 nodos los cuales vamos a linkear de la siguiente manera.

nodo_a(valor: “hola mundo”) >>> nodo_b(valor: 1986) >>> nodo_c(valor: [3, 4, 5, 6])

nodo_a = Nodo("hola mundo")
nodo_b = Nodo(1986)
nodo_c = Nodo([3, 4, 5, 6])

Ahora procedemos a establecer el enlace entre los nodos, utilizando el método de set_link que definimos en nuestra clase Nodo. Recuerda que debemos linkear el nodo_a > nodo_b, y luego el nodo_b > nodo_c.

nodo_a.set_link(nodo_b)
nodo_b.set_link(nodo_c)

De esta manera tenemos los nodos instanciados y linkeados entre sí de la siguiente manera.

Ahora vamos a hacer una prueba accediendo a los valores de los nodos. Noten que pueden acceder a los valores de diferentes maneras, pero en este caso vamos a usar 2 formas prácticas.

La manera directa. Es decir, vamos a “almacenar” el valor de un nodo en una variable, utilizando directamente el método ver_valor.

Mediante link. Vamos a “almacenar” el valor de un nodo en una variable, referenciando al nodo anterior y usando el link para “transportarnos” al siguiente nodo y obtener su valor. Esto lo haremos combinando los métodos que definimos > ver_link().ver_valor()

# A modo de prueba, vamos a crear 3 variables, almacenar los valores de 3 nodos e imprimir los mismos. 
# Si todo está bien, debemos tener impresos los valores en consola. Utilizamos el método ver_valor().

valor_nodo_a = nodo_a.ver_valor()
valor_nodo_b_directo = nodo_b.ver_valor()
valor_nodo_b = nodo_a.ver_link().ver_valor()
valor_nodo_c_directo = nodo_c.ver_valor()
valor_nodo_c = nodo_b.ver_link().ver_valor()

Y ahora imprimimos nuestros resultados para probar que todo haya salido bien.

# imprimimos nuestras variales.

print("El valor del nodo a, es: ", valor_nodo_a)
print("El valor del nodo b, accediendo de forma directa es: ", valor_nodo_b_directo)
print("El valor del nodo b, accdediendo desde el nodo_a usando link es: ", valor_nodo_b)
print("El valor del nodo b, accediendo de forma directa es: ", valor_nodo_c_directo)
print("El valor del nodo b accdediendo desde el nodo_b usando link es: ", valor_nodo_c)

Y tenemos el resultado esperado.

Si quieren ver en mayor detalle que fue lo que hice, les dejo el enlace al archivo de prueba que desarrollamos en este post.

Hacé clic aquí para ir al archivo python.

En el siguientes post, veremos la primera estructura de datos que incorpora Nodos, las Listas Enlazadas.