Google+ Seguidores

domingo, 1 de julio de 2018

Linked List: Listas enlazadas - Implementación en Python

Introducción:

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.

Resultado de imagen para linked list

¿Que es un Linked Lists?

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.


Las listas enlazadas se encuentran entre las estructuras de datos más simples y comunes. Se pueden usar para implementar muchos otros tipos de datos abstractos comunes , incluyendo listas , pilas , colas , matrices asociativas y expresiones S , aunque no es raro implementar esas estructuras de datos directamente sin utilizar una lista vinculada como base.

El beneficio principal de una lista vinculada en una matriz convencional es que los elementos de la lista pueden insertarse o eliminarse fácilmente sin reasignar o reorganizar toda la estructura porque los elementos de datos no necesitan almacenarse contiguamente en la memoria o en el disco, mientras reestructuran una matriz en el tiempo de ejecución es una operación mucho más costosa. Las listas vinculadas permiten la inserción y eliminación de nodos en cualquier punto de la lista, y permiten hacerlo con un número constante de operaciones al mantener el enlace anterior al enlace que se agrega o elimina en la memoria durante el recorrido de la lista.

Cada nodo tiene un valor (datos) y una referencia al siguiente nodo. La referencia es típicamente un puntero o una dirección de memoria donde se puede encontrar el siguiente valor. En la imagen de ejemplo de una lista vinculada, "2" es el valor, mientras que "2184" es el puntero al siguiente nodo, que es "4". Luego "4" tiene un valor de puntero de "3225" que apunta a la siguiente el valor del nodo de "6", etc. Dado que "7" es el último nodo, el puntero es Nulo ya que no hay ningún valor después de "7".
Para la inserción de un nodo, lo insertamos al final de la lista enlazada. Para la eliminación de un nodo, primero encontramos el nodo, lo elimina y luego vuelve a conectar la lista vinculada. Veremos más en detalle en la sección de implementación.

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 .

Implementación de Linked list en Python:

Para la implementación, seguiremos los siguientes pasos:

Clase de nodo

Primero creamos una clase Node. Recuerde que cada nodo tiene un valor y un puntero al siguiente.

Clase Linked List

Ahora crearemos una clase de lista vinculada.

Método para insertar

Ahora crearemos la clase para insertar elementos.


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.

1 comentario :
Write comentarios

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .