Una lista enlazada es una de las estructuras de datos más comunes que se utilizan en informática. También es uno de los más simples y también es fundamental para estructuras de nivel superior como pilas, búferes circulares y colas.
En términos generales, una lista es una colección de elementos de datos individuales que están conectados mediante referencias. Los programadores de C conocen esto como punteros. Por ejemplo, un elemento de datos puede constar de datos de direcciones, datos geográficos, datos geométricos, información de enrutamiento o detalles de transacciones. Normalmente, cada elemento del lista enlazada tiene el mismo tipo de datos que es específico de la lista.
Un solo elemento de la lista se llama node. Los nodes no son como matrices que se almacenan secuencialmente en la memoria. En cambio, es probable que los encuentre en diferentes segmentos de memoria, que puede encontrar siguiendo los indicadores de un node al siguiente. Es común marcar el final de la lista con un elemento NIL, representado por el equivalente de Python None.
Figura 1: Lista de un solo enlace
Existen dos tipos de listas: simple y listas de doble enlace. Un node en una lista de un solo enlace solo apunta al siguiente elemento de la lista, mientras que un node en una lista de doble enlace también apunta al node anterior. La estructura de datos ocupa más espacio porque necesitará una variable adicional para almacenar la referencia adicional.
Figura 2: Lista de doble enlace
Una lista de un solo enlace se puede recorrer de la cabeza a la cola, mientras que recorrer hacia atrás no es tan fácil como eso. Por el contrario, una lista de doble enlace permite atravesar los nodes en ambas direcciones al mismo costo, sin importar con qué node comience. Además, la adición y eliminación de nodes, así como la división de listas de un solo enlace, se realiza en no más de dos pasos. En una lista de doble enlace, deben cambiarse cuatro punteros.
El lenguaje Python no contiene un tipo de datos predefinido para listas vinculadas. Para hacer frente a esta situación, tenemos que crear nuestro propio tipo de datos o tenemos que hacer uso de módulos de Python adicionales que proporcionan una implementación de dicho tipo de datos.
En este artículo, repasaremos los pasos para crear nuestra propia estructura de datos de lista vinculada. Primero creamos una estructura de datos correspondiente para el node. En segundo lugar, aprenderá a implementar y utilizar tanto una lista de enlace único como, finalmente, una lista de enlace doble.
Paso 1: node como estructura de datos
Contenido
- 1 Paso 1: node como estructura de datos
- 2 Paso 2: creación de una clase para una lista unificada
- 3 Paso 3: agregar nodes
- 4 Paso 4: búsqueda en la lista
- 5 Paso 5: eliminar un artículo de la lista
- 6 Paso 6: creación de una lista de enlace doble
- 7 Paso 7: creación de listas de doble enlace con deque
- 8 Conclusión
Para tener una estructura de datos con la que podamos trabajar, definimos un node. Un node se implementa como una clase llamada ListNode. La clase contiene la definición para crear una instancia de objeto, en este caso, con dos variables: data para mantener el valor del node, y next para almacenar la referencia al siguiente node de la lista. Además, un node tiene los siguientes métodos y propiedades:
__init_(): inicializa el node con los datosself.data: el valor almacenado en el nodeself.next: el puntero de referencia al siguiente nodehas_value(): compara un valor con el valor del node
Estos métodos aseguran que podamos inicializar un node correctamente con nuestros datos (__init__()), y cubren tanto la extracción como el almacenamiento de datos (a través del self.data propiedad), así como obtener la referencia al node conectado (a través del self.next propiedad). El método has_value() nos permite comparar el valor del node con el valor de un node diferente.
Listado 1: La clase ListNode
class ListNode:
def __init__(self, data):
"constructor to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Crear un node es tan simple como eso, y crea una instancia de un objeto de clase. ListNode:
Listado 2: Creación de instancias de nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
Una vez hecho esto, tenemos disponibles tres instancias del ListNode clase. Estas instancias representan tres nodes independientes que contienen los valores 15 (entero), 8.2 (flotante) y «Berlín» (cadena).
Paso 2: creación de una clase para una lista unificada
Como segundo paso, definimos una clase llamada SingleLinkedList que cubre los métodos necesarios para administrar nuestros nodes de lista. Contiene estos métodos:
__init__(): iniciar un objetolist_length(): devuelve el número de nodesoutput_list(): genera los valores del nodeadd_list_item(): agrega un node al final de la listaunordered_search(): busca en la lista los nodes con un valor especificadoremove_list_item_by_id(): elimina el node según su id
Repasaremos cada uno de estos métodos paso a paso.
los __init__() El método define dos variables de clase internas llamadas head y tail. Representan los nodes inicial y final de la lista. Inicialmente, ambos head y tail tener el valor None siempre que la lista esté vacía.
Listado 3: La clase SingleLinkedList (parte uno)
class SingleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
Paso 3: agregar nodes
La adición de elementos a la lista se realiza mediante add_list_item(). Este método requiere un node como parámetro adicional. Para asegurarse de que sea un node adecuado (una instancia de clase ListNode) el parámetro se verifica primero usando la función incorporada de Python isinstance(). Si tiene éxito, el node se agregará al final de la lista. Si item no es un ListNode, entonces se crea uno.
En caso de que la lista esté (todavía) vacía, el nuevo node se convierte en el encabezado de la lista. Si un node ya está en la lista, entonces el valor de tail se ajusta en consecuencia.
Listado 4: La clase SingleLinkedList (segunda parte)
def add_list_item(self, item):
"add an item at the end of the list"
if not isinstance(item, ListNode):
item = ListNode(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
los list_length() El método cuenta los nodes y devuelve la longitud de la lista. Para pasar de un node al siguiente en la lista, la propiedad del node self.next entra en juego y devuelve el enlace al siguiente node. El conteo de los nodes se realiza en un bucle while siempre que no lleguemos al final de la lista, que está representada por un None enlace al siguiente node.
Listado 5: La clase SingleLinkedList (tercera parte)
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
El método output_list() genera los valores del node utilizando la propiedad del node data. Nuevamente, para ir de un node al siguiente se utiliza el enlace que se proporciona a través de next propiedad.
Listado 6: La clase SingleLinkedList (cuarta parte)
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
Basado en la clase SingleLinkedList podemos crear una lista adecuada llamada tracky juegue con sus métodos como ya se describió anteriormente en los listados 3-6. Por lo tanto, creamos cuatro nodes de lista, los evaluamos en un for bucle y muestra el contenido de la lista. El Listado 7 le muestra cómo programar eso, y el Listado 8 muestra la salida.
Listado 7: Creación de nodes y salida de lista
# create four single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)
track = SingleLinkedList()
print("track length: %i" % track.list_length())
for current_item in [node1, node2, item3, node4]:
track.add_list_item(current_item)
print("track length: %i" % track.list_length())
track.output_list()
El resultado es el siguiente y muestra cómo crece la lista:
Listado 8: Agregar nodes a la lista
$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15
Paso 4: búsqueda en la lista
La búsqueda en toda la lista se realiza mediante el método unordered_search(). Requiere un parámetro adicional para buscar el valor. El encabezado de la lista es el punto de partida.
Mientras buscamos contamos los nodes. Para indicar una coincidencia usamos el número de node correspondiente. El método unordered_search() devuelve una lista de números de node que representan las coincidencias. Como ejemplo, tanto el primer como el cuarto node contienen el valor 15. La búsqueda de 15 da como resultado una lista con dos elementos: [1, 4].
Listado 9: El método de búsqueda unordered_search ()
def unordered_search (self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
Paso 5: eliminar un artículo de la lista
Eliminar un node de la lista requiere ajustar solo una referencia: la que apunta al node que se eliminará ahora debe apuntar al siguiente. Esta referencia la conserva el node que se va a eliminar y debe reemplazarse. En segundo plano, el recolector de basura de Python se encarga de los objetos sin referencia y los ordena.
El siguiente método se llama remove_list_item_by_id(). Como parámetro se refiere al número del node similar al valor devuelto por unordered_search().
Listado 10: Eliminar un node por número de node
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
previous_node = None
while current_node is not None:
if current_id == item_id:
# if this is the first node (head)
if previous_node is not None:
previous_node.next = current_node.next
else:
self.head = current_node.next
# we don't have to look any further
return
# needed for the next iteration
previous_node = current_node
current_node = current_node.next
current_id = current_id + 1
return
Paso 6: creación de una lista de enlace doble
Para crear una lista de doble enlace, se siente natural solo extender el ListNode class creando una referencia adicional al node anterior. Esto afecta los métodos para agregar, eliminar y ordenar nodes. Como se muestra en el Listado 11, una nueva propiedad llamada previous se ha agregado para almacenar el puntero de referencia al node anterior en la lista. Cambiaremos nuestros métodos para usar esta propiedad para rastrear y atravesar nodes también.
Listado 11: Clase de node de lista extendida
class ListNode:
def __init__(self, data):
"constructor class to initiate this object"
# store data
self.data = data
# store reference (next item)
self.next = None
# store reference (previous item)
self.previous = None
return
def has_value(self, value):
"method to compare the value with the node data"
if self.data == value:
return True
else:
return False
Ahora podemos definir una lista de doble enlace de la siguiente manera:
Listado 12: una clase DoubleLinkedList
class DoubleLinkedList:
def __init__(self):
"constructor to initiate this object"
self.head = None
self.tail = None
return
def list_length(self):
"returns the number of list items"
count = 0
current_node = self.head
while current_node is not None:
# increase counter by one
count = count + 1
# jump to the linked node
current_node = current_node.next
return count
def output_list(self):
"outputs the list (the value of the node, actually)"
current_node = self.head
while current_node is not None:
print(current_node.data)
# jump to the linked node
current_node = current_node.next
return
def unordered_search (self, value):
"search the linked list for the node that has this value"
# define current_node
current_node = self.head
# define position
node_id = 1
# define list of results
results = []
while current_node is not None:
if current_node.has_value(value):
results.append(node_id)
# jump to the linked node
current_node = current_node.next
node_id = node_id + 1
return results
Como se describió anteriormente, agregar nodes requiere un poco más de acción. El Listado 13 muestra cómo implementar eso:
Listado 13: Agregar nodes en una lista de doble enlace
def add_list_item(self, item):
"add an item at the end of the list"
if isinstance(item, ListNode):
if self.head is None:
self.head = item
item.previous = None
item.next = None
self.tail = item
else:
self.tail.next = item
item.previous = self.tail
self.tail = item
return
Eliminar un artículo de la lista deben tenerse en cuenta costos similares. El Listado 14 muestra cómo hacer eso:
Listado 14: Eliminar un elemento de una lista de doble enlace
def remove_list_item_by_id(self, item_id):
"remove the list item with the item id"
current_id = 1
current_node = self.head
while current_node is not None:
previous_node = current_node.previous
next_node = current_node.next
if current_id == item_id:
# if this is the first node (head)
if previous_node is not None:
previous_node.next = next_node
if next_node is not None:
next_node.previous = previous_node
else:
self.head = next_node
if next_node is not None:
next_node.previous = None
# we don't have to look any further
return
# needed for the next iteration
current_node = next_node
current_id = current_id + 1
return
El Listado 15 muestra cómo usar la clase en un programa Python.
Listado 15: Creación de una lista de doble enlace
# create three single nodes
node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)
track = DoubleLinkedList()
print("track length: %i" % track.list_length())
for current_node in [node1, node2, node3, node4]:
track.add_list_item(current_node)
print("track length: %i" % track.list_length())
track.output_list()
results = track.unordered_search(15)
print(results)
track.remove_list_item_by_id(4)
track.output_list()
Como puede ver, podemos usar la clase exactamente como antes, cuando era solo una lista de un solo enlace. El único cambio es la estructura de datos interna.
Paso 7: creación de listas de doble enlace con deque
Dado que otros ingenieros se han enfrentado al mismo problema, podemos simplificar las cosas para nosotros y utilizar una de las pocas implementaciones existentes disponibles. En Python, podemos usar el deque objeto del collections módulo. Según la documentación del módulo:
Los deques son una generalización de pilas y colas (el nombre se pronuncia «baraja» y es la abreviatura de «cola de dos extremos»). Los Deques admiten agregados y estallidos seguros para subprocesos y eficientes en memoria desde cualquier lado del deque con aproximadamente el mismo rendimiento O (1) en cualquier dirección.
Por ejemplo, este objeto contiene los siguientes métodos:
append(): agrega un elemento al lado derecho de la lista (final)append_left(): agrega un elemento al lado izquierdo de la lista (encabezado)clear(): eliminar todos los elementos de la listacount(): cuenta el número de elementos con un valor determinadoindex(): encuentra la primera aparición de un valor en la listainsert(): inserta un elemento en la listapop(): eliminar un elemento del lado derecho de una lista (final)popleft(): eliminar un elemento del lado izquierdo de una lista (encabezado)remove(): eliminar un elemento de la listareverse(): invertir la lista
La estructura de datos subyacente de deque es una lista de Python que tiene un doble enlace. El primer node de la lista tiene el índice 0. Usando deque conduce a una simplificación significativa de la ListNode clase. Lo único que conservamos es la variable de clase. data para almacenar el valor del node. El Listado 16 es el siguiente:
Listado 16: Clase ListNode con deque (simplificado)
from collections import deque
class ListNode:
def __init__(self, data):
"constructor class to initiate this object"
# store data
self.data = data
return
La definición de nodes no cambia y es similar al Listado 2. Con este conocimiento en mente, creamos una lista de nodes de la siguiente manera:
Listado 17: Creando una lista con deque
track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
print(item.data)
Agregar un elemento al principio de la lista funciona con el append_left() método como muestra el Listado 18:
Listado 18: Agregar un elemento al comienzo de una lista
# add an item at the beginning
node4 = ListNode(15)
track.append_left(node4)
print("four items (added as the head):")
for item in track:
print(item.data)
Similar, append() agrega un node al final de la lista como muestra el Listado 19:
Listado 19: Agregar un elemento al final de la lista
# add an item at the end
node5 = ListNode("Moscow")
print("five items (added at the end):")
track.append(node5)
for item in track:
print(item.data)
Conclusión
Las listas enlazadas como estructuras de datos son fáciles de implementar y ofrecen una gran flexibilidad de uso. Se hace con unas pocas líneas de código. Como mejora, puede agregar un contador de nodes, una variable de clase que simplemente contiene el número de nodes en la lista. Esto reduce la determinación de la longitud de la lista a una sola operación con O (1) y no tiene que recorrer toda la lista.
Para obtener más información e implementaciones alternativas, puede echar un vistazo aquí:
llist– Tipos de datos de listas vinculadas para Python (https://pythonhosted.org/llist/)collections– Tipos de datos de contenedor (https://docs.python.org/3.6/library/collections.html)
