Biblioteca de Python para lista enlazada

La lista enlazada es una estructura de datos simple en programación, que obviamente se usa para almacenar datos y recuperarlos en consecuencia. Para que sea más fácil de imaginar, se parece más a una array dinámica en la que los elementos de datos se vinculan a través de punteros (es decir, el registro actual apunta a su siguiente registro y el siguiente apunta al registro que viene después, esto continúa hasta que el extremo de la estructura) en lugar de estar muy apretado.

Hay dos tipos de lista enlazada:

1. Lista de enlace único: en esta, los Nodes apuntan al Node inmediatamente posterior.
2. Lista doblemente enlazada: en esta, los Nodes no solo hacen referencia al Node contiguo sino también al Node anterior.

Lista vinculada en Python:

Para empezar, Python no tiene una biblioteca de listas enlazadas integrada como los lenguajes de programación clásicos. Python tiene una lista de tipos incorporada que funciona como una array dinámica, pero su funcionamiento no debe confundirse con una función típica de una lista vinculada. Esto no significa que uno no pueda implementar una lista enlazada en Python, puede hacerlo, pero no será directo. Los siguientes métodos se pueden usar para implementar una lista enlazada en Python, ya que no tiene una biblioteca incorporada para ello:

Método 1: Usar el paquete deque() .
Esta es una clase incorporada en Python, obviamente utilizada para eliminar la cola, pero se puede implementar de tal manera que funcione como una lista enlazada bajo ciertas condiciones. 

A continuación se muestra la implementación de la lista enlazada:

# importing module
import collections
  
# initialising a deque() of arbitrary length
linked_lst = collections.deque()
  
# filling deque() with elements
linked_lst.append('first')
linked_lst.append('second')
linked_lst.append('third')
  
print("elements in the linked_list:")
print(linked_lst)
  
# adding element at an arbitrary position
linked_lst.insert(1, 'fourth')
  
print("elements in the linked_list:")
print(linked_lst)
  
# deleting the last element
linked_lst.pop()
  
print("elements in the linked_list:")
print(linked_lst)
  
# removing a specific element
linked_lst.remove('fourth')
  
print("elements in the linked_list:")
print(linked_lst)

 Producción:

elements in the linked_list:
deque(['first', 'second', 'third'])
elements in the linked_list:
deque(['first', 'fourth', 'second', 'third'])
elements in the linked_list:
deque(['first', 'fourth', 'second'])
elements in the linked_list:
deque(['first', 'second'])

¿Cuándo usar deque() como una lista enlazada?

• Insertar y eliminar elementos en la parte delantera y trasera respectivamente es la única necesidad. Insertar y quitar elementos del medio lleva mucho tiempo.
• Inversión en el lugar ya que Python ahora permite que los elementos se inviertan en el lugar mismo.
• Se prefiere el almacenamiento al rendimiento y no todos los elementos obtienen un Node independiente propio

Método 2: Usar el paquete llist .

llist es un módulo de extensión para CPython que proporciona estructuras de datos de listas enlazadas básicas. El tipo se proporciona debajo del comando en su línea de comando: 

pip install llist

A continuación se muestra la implementación de la lista enlazada:

# importing packages
import llist
from llist import sllist,sllistnode
  
# creating a singly linked list
lst = sllist(['first','second','third'])
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
  
# adding and inserting values
lst.append('fourth')
node = lst.nodeat(2)
  
lst.insertafter('fifth',node)
  
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
  
# popping a value
#i.e. removing the last entry 
# of the list
lst.pop()
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()
  
# removing a specific element
node = lst.nodeat(1)
lst.remove(node)
print(lst)
print(lst.first)
print(lst.last)
print(lst.size)
print()

 Producción: 

sllist([first, second, third])
sllistnode(first)
sllistnode(third)
3

sllist([first, second, third, fifth, fourth])
sllistnode(first)
sllistnode(fourth)
5

sllist([first, second, third, fifth])
sllistnode(first)
sllistnode(fifth)
4

sllist([first, third, fifth])
sllistnode(first)
sllistnode(fifth)
3

Método 3: Usando el paquete StructLinks

StructLinks se utiliza para acceder fácilmente y visualizar diferentes estructuras de datos, incluidas listas vinculadas, listas doblemente vinculadas, árboles binarios, gráficos, pilas y colas.

Los módulos structlinks.LinkedList y structlinks.DoublyLikedList podrían usarse para hacer listas enlazadas. Todas las operaciones que se pueden realizar con una lista también se pueden realizar con la clase structlinks.LinkedList.

Click para ir a la documentación 

Escriba el comando en su línea de comando:

pip install structlinks

A continuación se muestra la implementación de algunos métodos de la lista enlazada:

import structlinks
from structlinks import LinkedList
  
# create an empty linked list
lst = LinkedList()
  
# create a linked list with initial values
lst = LinkedList([1, 10.0, 'string'])
  
print(lst)
  
print()
  
print('Elements of list:')
  
# elements of the list
element0 = lst[0]
element1 = lst[1]
element2 = lst[2]
  
print(f'first element : {element0}')
print(f'second element : {element1 }')
print(f'third element : {element2}')
  
print()
  
print('Length of list:')
  
# Length of the list
length = len(lst)
  
print(f'size of the list : {length}')
  
print()
  
print('Set item:')
  
# Set item
lst[0] = 10
  
print(f'list after setting lst[0] to 10 : {lst}')
  
print()
  
print('Append And Insert:')
  
# Append And Insert
lst.append('another string')
lst.insert(1, 0.0)
  
print(f'list after appending and inserting: {lst}')
  
print()
  
print('Pop and Remove')
  
# Pop and Remove 
element = lst.pop(0)
lst.remove(10.0)
  
print(f'list after popping and removing : {lst}')
print(f'pop function also returns the element : {element}')
  
# This code is contributed by eeshannarula29

Producción: 

[1 -> 10.0 -> string]

Elements of list:
1
10.0
string

Length of list:
3

Set item:
list after setting lst[0] to 10 : [10 -> 10.0 -> string]

Append and Insert:
list after appending and inserting: [10 -> 0.0 -> 10 -> string -> another string]

Pop and Remove:
list after popping and removing: [0.0 -> string -> another string]