Linked List: Listas enlazadas - Implementación en Python

Hola amigos de Internet, les doy la bienvenida nuevamente a Mi Diario Python, el mejor blog para aprender python.

En el articulo de hoy, veremos ¿Que es un Linked List? y realizaremos una sencilla implementación utilizando el lenguaje de Programación Pyhton.

Una lista enlazada es una estructura de datos dinámica. La cantidad de nodos en una lista no es fija y puede crecer y contraerse a demanda. Cualquier aplicación que tenga que tratar con un número desconocido de objetos necesitará usar una lista vinculada.


Una desventaja de una lista vinculada frente a una matriz es que no permite el acceso directo a los elementos individuales. Si desea acceder a un artículo en particular, debe comenzar por la cabecera y seguir las referencias hasta que llegue a ese artículo.

Desventajas:

• Utilizan más memoria que las matrices debido al almacenamiento utilizado por sus punteros .
• Los nodos en una lista vinculada deben leerse en orden desde el principio, ya que las listas vinculadas son intrínsecamente de acceso secuencial .
• Los nodos se almacenan de forma incontinua, lo que aumenta en gran medida los períodos de tiempo necesarios para acceder a elementos individuales dentro de la lista, especialmente con un caché de CPU .
• Las dificultades surgen en las listas vinculadas cuando se trata de atravesar en reversa. Por ejemplo, las listas vinculadas individualmente son engorrosas para navegar hacia atrás y mientras que las listas doblemente enlazadas son algo más fáciles de leer, la memoria se consume al asignar espacio para un puntero reverso .

Para la implementación, seguiremos los siguientes pasos:

Clase de nodo

Clase Linked List

Método para insertar

Ahora que les parece un escribimos el código? :

# Creamos la clase node
class node:
    def __init__(self, data = None, next = None):
        self.data = data
        self.next = next

# Creamos la clase linked_list
class linked_list: 
    def __init__(self):
        self.head = None
    
    # Método para agregar elementos en el frente de la linked list
    def add_at_front(self, data):
        self.head = node(data=data, next=self.head)  

    # Método para verificar si la estructura de datos esta vacia
    def is_empty(self):
        return self.head == None

    # Método para agregar elementos al final de la linked list
    def add_at_end(self, data):
        if not self.head:
            self.head = node(data=data)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = node(data=data)
    
    # Método para eleminar nodos
    def delete_node(self, key):
        curr = self.head
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if prev is None:
            self.head = curr.next
        elif curr:
            prev.next = curr.next
            curr.next = None

    # Método para obtener el ultimo nodo
    def get_last_node(self):
        temp = self.head
        while(temp.next is not None):
            temp = temp.next
        return temp.data

    # Método para imprimir la lista de nodos
    def print_list( self ):
        node = self.head
        while node != None:
            print(node.data, end =" => ")
            node = node.next


s = linked_list() # Instancia de la clase
s.add_at_front(5) # Agregamos un elemento al frente del nodo
s.add_at_end(8) # Agregamos un elemento al final del nodo
s.add_at_front(9) # Agregamos otro elemento al frente del nodo

s.print_list() # Imprimimos la lista de nodos

9 => 5 => 8 =>

Este seria el resultado.

Puedes ver el código en acción, aquí: https://code.sololearn.com/civQtFrF3Z4B/#py.

¿Alguna duda? Entonces no dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.