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)