Es recomendable tener manejo del lenguaje de programación Python 3, también conocimientos en Programación Orientada a Objetos (POO). No es estrictamente necesario, pero si importante, tener por lo menos nociones del concepto Magic Methods (ó Dundder Methods) de Python.
Introducción
Es muy probable que cundo se hable de organizar datos de manera secuencial tu primera opción sea intentar utilizar un Array (conocido por algunos como Arreglo) o Lista, y bueno, no te culpo, también era el mío antes de conocer por completo el maravilloso mundo de las Estructuras de Datos. No está mal usar dichas estructuras, pero existen otras alternativas para situaciones específicas que harán que tus implementaciones sean más fáciles, seguras y eficientes.
¿Qué es una Linked List?
Linked List o Lista Enlazada (aquí utilizaremos anglicismos 😜) es una estructura de datos lineal, compuesta por objetos llamados Nodos, los cuales están referenciados unos con otros y no necesariamente porque estén ubicados continuamente en bloques de memoria, como pasa tradicionalmente con los Arrays.
Ahora con cucharita 😅: toda la información volátil (que no está almacenada para siempre, sólo mientras corra nuestro código) de nuestra aplicación, así como las variables y objetos, se colocan en un espacio de nuestra memoria volátil (como la RAM), en el caso de los arreglos, se colocan todos los integrantes uno al lado del otro en bloques de memoria continuos. Por ejemplo, supongamos que se tiene lo siguiente:
frutas = ['pizza', 'banana', 'naranja', 'pera', 'piña', 'melón']
La 🍕 no es una fruta pero a veces le echan tanta piña que parece una 😪.
La manera como se aloja en bloques de memoria continuos es la siguiente:
Nota: en la imagen se asume que los caracteres están codificados en UCS-4, lo que implica que se ocupan 4 bytes por caracter.
En el caso de las Linked List, no es necesario, sino, que los integrantes (o Nodos) de dicha lista pueden estar en bloques de memoria bastante alejados o bastante cerca:
Si, ya sé... Te estás preguntando que quiere decir eso, déjame ilustrarte:
Hasta este punto tenemos una explicación más clara que concluye en que las Linked List son un grupo de Nodos que se referencian entre sí. Sin embargo, falta un detalle importante, bueno, dos detalles importantes 😅. Lo primero es que nuestro objeto de Linked List no almacena por si solo los Nodos, sino que esta guarda una referencia sólo al primer Nodo, el cual se llama Head (o cabeza). El Head, a su vez guarda referencia al Nodo siguiente, y así mismo el Nodo siguiente al que le sigue, hasta llegar al último, el cual tiene que apuntar a una dirección de memoria vacía o de valor nulo, esto es porque en una Linked List todos los Nodos deben de estar apuntando a "algo".
Ya que sabemos más o menos los fundamentos, te estarás preguntando sobre las ventajas de sobre las Listas o Arrays, bueno, realmente existen ciertas ventajas que murieron con la utilización de los lenguajes de alto nivel, ya que estos en su mayoría son capaces de ajustar dinámicamente los tamaños de los bloques de memoria, ya que tradicionalmente eran fijos, también permiten tener objetos de diferentes tipos en una misma estructura. No obstante, la verdadera ventaja de esta estructura es el acceso secuencial de la data, lo cual facilita la implementación de otras estructuras muy importantes que veremos más adelante. Ya verás :twink:.
Podemos hacer muchas operaciones como las Linked List, así como insertar elementos, buscar elementos, entre otras más. Sin embargo, la más importante es la de recorrer la Linked List, ya que todas las demás se apoyan en esta, es decir, siempre hay que recorrer la Linked List. Si quieres saber sobre más operaciones que se pueden hacer con las Linked List, te invito a ver esto. También existen otras variantes de Linked List, son fáciles de entender si se aplican los conceptos explicados anteriormente, sin embargo, no las estaremos utilizando a lo largo de esta serie y por eso no me detendré a explicarlas. Si tu aplicación demanda dichas implantaciones, entonces adelante.
Haciendo nuestra propia LinkedList
Cabe destacar que la Estructura de Datos List de Python, puede utilizarse como una Linked List, de hecho tiene métodos para tales fines, también tenemos un módulo llamado Collections que contiene una Estructura llamada Deque, la cual funciona parecido. En nuestro caso, haremos la nuestra para fines de explicación de la implementación. En la vida real, estas estructuras ya construidas por el lenguaje que utilicemos nos ahorran tiempo y son más eficientes.
Primero, empezamos creando los Nodos, estos serán los objetos que almacenaremos en nuestra Linked List, ej.: Pizza, banana, pera, etc.. La estrategia es que el Nodo pueda hacer referencia al objeto que tendrá como valor y al Nodo siguiente.
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
Hasta aqui no creo que la cosa se complique 😬. Tenemos un objeto Nodo que posee un valor y una referencia de quien le sigue. Por lo tanto, si yo creo un Nodo, le doy su valor y el del Nodo que le sigue, si no tienen ningún otro, entonces apunta a None, así voy creando mi Linked List.
Ok, obvio que no es todo... ¿Cómo puedo saber cual es el Head de mi lista?... No puedo poner dicho objeto Hardcoded en mi código porque si cambia en alguna parte de este, tendré un tremendo lío con la referencia. Por lo tanto, tenemos que crear un objeto Linked List que siempre guarde una referencia en el atributo Head (tal como lo habíamos dicho antes) y también efectué todas las operaciones necesarias sobre la lista, tales como recorrerla, voltearla, añadir otros Nodos, extraerlos, etc.
class LinkedList:
def __init__(self, head=None, l=None):
# Referencia al nodo head
self.head = head
# Si se pasó una lista como argumento, se crea una Linked List
if l is not None:
# Selecciona el primer elemento de la lista como la cabeza
self.head = Node(l[0])
current_node = self.head
list_len = len(l)
# Itera sobre la lista, si el elemento en curso es el ultimo
# apunta su siguiente nodo a None
for i in range(1, list_len):
current_node.next = Node(l[i])
if i == list_len:
current_node.next = None
else:
current_node = current_node.next
# Magic method para recorrer la Linked List
# Este metodo se llama cuando se está recorriendo la Linked List
def __iter__(self):
node = self.head
# Retorna cada nodo en la iteración correspondiente
while node is not None:
yield node
node = node.next
# Magic method que retorna la longitud de la lista
def __len__(self):
count = 0
# Itera la Linked List mientras cuenta cada elemento
for node in self:
count += 1
return count
# Magic method que retorna el nodo, dado un indice a la entrada
def __getitem__(self, item):
current = self.head
count = 0
# Retorna el valor del nodo si el item es un entero
while count != idx:
current = current.next
count += 1
return current
# Inserta un nodo al final de la Linked List
def append(self, item: Node):
#Si no hay nodo, entonces lo inserta como Head
if self.head is None:
self.head = item
self.head.next = None
return None
# Busca el último nodo y lo apunta al nodo a insertar
for node in self:
if node.next is None:
node.next = item
item.next = None
Podemos añadir más métodos para hacer más operaciones con nuestra Linked List, pero lo vamos a dejar hasta ahí por el momento para no crearte un Stackoverflow 😫 😵 en el 🧠. La idea es que entiendas el concepto de esta estructura, las demás operaciones las estaremos viendo conforme salgan los otros posts.
Aplicando lo aprendido
Para poner en práctica lo explicado anteriormente, vamos a utilizar nuestro código y haremos un reproductor de tracklists como el de Spotify (más sencillo). En dado caso que no quieras utilizar lo que se creó más arriba, puedes utilizar las estructuras nativas de Python que te mencioné y tomarlo como ejercicio, esto si no sabes sobre POO, más adelante haré una serie al respecto.
Para esto, consumiremos un API de Discogs que nos proporcione los tracklist de acuerdo a releases de los artistas, elegiremos cual queremos reproducir y podremos cambiar de canción o track (avanzar a la siguiente y/o volver a la anterior).
Nota: esto no es un tutorial para consumir APIs, esta parte la puedes obviar, te puedes hacer de cuenta que es una función que llamas y te da una lista de tracks. De todos modos, pondré el código por si alguien se anima a querer entenderlo, no tiene mucha complejidad.
import time
import requests
from random import sample
def get_tracklists(artist_id:int=57620, releases_n:int = 5) -> list:
# Url para obtener los releases
url = "https://api.discogs.com/artists/{}/releases".format(artist_id)
response = requests.request("GET", url,).json()['releases']
releases = [(release['id'], release['title']) for release in response if release['type'] == 'master']
# Filtrando la data y obteniendo el campo de releases
random_rels = sample(releases, k=releases_n)
# Url para obtener información acerca de los releases
url = "https://api.discogs.com/masters/{}"
tracklists_names = []
# Separando los tracklist de cada reseale
for rel in random_rels:
tracklists = requests.request('GET', url.format(rel[0])).json()['tracklist']
# Tiempo de delay para que api.discogs.com no niegue los responses
# debido a la velocidad en un corto lapso de tiempo
time.sleep(0.5)
tracklists_names.append({rel[1]: [track['title'] for track in tracklists if track['type_'] == 'track']})
return tracklists_names
En resumen, la funcion retorna una lista con varios diccionarios, en los cuales cada key es el nombre de un release en específico de un artista en específico (para el ejemplo he cogido a Buddy Rich), el value de cada uno sería una lista de las canciones o tracks pertenecientes a dicho release.
Para crear nuestra app de nuestro reproductor, tendríamos lo siguiente:
from apis import get_tracklists
from linked_list import LinkedList, Node
def app():
# Obtiene la lista de los releases con sus repectivos tracklists
releases = get_tracklists()
current_rel, current_track = 'No release selected', Node('No track selected')
#Linked List para manejar los tracks
tracklist = LinkedList()
# String de las opciones del menu
main_menu = """
Main menu
===================
1. Select Release
2. Next track
3. Previous track
4. Exit
Current Release: {}
Current Track: {}
Select an option: """
while True:
# Guarda la opcion seleccionada en el menu
selection = input(main_menu.format(current_rel, current_track.value))
if selection == '1':
# Construye el menu de releases
# Para fines de este tutorial, no se abundará esta parte
rel_menu = lambda rel_list: ''.join(['{}- {} \n'.format(index, list(rel.keys())[0]) for index, rel in zip(range(1, len(rel_list)+1), rel_list)])
releases_menu = """
Releases Menu
=====================
{}
Select an option: """
# Captura la selección del release
release_selection = input(releases_menu.format(rel_menu(releases)))
# Guarda el release seleccionado en el menu
# El release contiene una lista con los tracklist
rel_dic = releases[int(release_selection)-1]
rel_name = list(rel_dic.keys())[0]
rel_tracks = list(rel_dic.values())[0]
# Actualiza la Linked List a una con el tracklist seleccionado
tracklist = LinkedList(l=rel_tracks)
# Asigna los valores para el release seleccionado,
# y el track en reproduccion como el head de la Linked List
current_rel, current_track = rel_name, tracklist.head
# Para cambiar al siguiente solo se asigna el nodo siguiente al track actual
elif selection == '2':
if current_track.next:
current_track = current_track.next
# Para volver atrás se recorre la lista hasta que el nodo siguiente
# del iterado sea el del track actual
elif selection == '3':
for track in tracklist:
if track.next == current_track:
current_track = track
# Sale de la aplicación
elif selection == '4':
break
Conclusión
La Linked List es una estructura muy poderosa y una alternativa a otras que ya conocemos, sobre todo son útiles en aplicaciones que utilizamos en el día a día, incluyendo los protocolos que se utilizan en nuestros equipos de redes, pero eso no es tema de este post, iremos adentrándonos más adelante.
Te dejo el código en Repl.it del resultado final para que puedas correrlo tu mismo.
Top comments (0)