En la entrada anterior vimos como abordar un problema habitual en informática, la necesidad de generar una colección que permita modificar la cantidad de elementos almacenados, mediante un array de tamaño dinámico.
En esta entrada vamos a ver otra forma clásica y muy habitual de resolver este problema, mediante el empleo de una Linked List.
¿Qué es una Linked List?
Una Linked List es una colección de nodos, cada uno de los cuales contiene el elemento almacenado y una referencia (un puntero) a otro nodo.
Estos nodos se componen de formando una especie de “cadena”, de forma que cada nodo apunta al nodo siguiente.
Este tipo de estructura de nodos apuntando a otros nodos, es muy potente y habitual en informática, y se emplean tanto para listas dinámicas como para árboles.
La principal ventaja de una Linked List es que las inserciones de elementos son, en general, muy eficientes. Únicamente tenemos que generar un nuevo nodo, cambiar las referencias del nodo anterior (si existe) para que apunte a nuestro nuevo nodo, y apuntar el nuevo nodo al nodo posterior (si existe). Por así decirlo, “partimos la cadena” e insertamos un nuevo nodo.
Por tanto, las inserciones al principio y al final de la Linked List son O(1). Las inserciones en medio de una Linked List también son O(1), si bien debemos tener en cuenta que encontrar el lugar de inserción puede ser costoso, como veremos a más adelante.
Una Linked List tiene la ventaja de poder añadir elementos mientras quede memoria en el sistema. Además, emplearemos únicamente la memoria que estamos utilizando a diferencia de un array dinámico donde normalmente tenemos un exceso de capacidad para acoger nuevos elementos sin necesidad de redimensionar.
Por supuesto, una Linked List también tiene ciertas desventajas. La principal, frente a un array, es que perdemos la capacidad de acceder a un elemento intermedio por su índice, lo que nos obliga a recorrer toda la Linked List “saltando” de nodo en nodo hasta llegar el elemento deseado. Por tanto, los accesos por índice para lectura, escritura o inserción son O(n) y, para empeorar las cosas, la operación de “salto” de nodo a nodo es relativamente lenta.
Otra desventaja es que requiere más memoria que un simple array ya que, en lugar de elementos, almacenamos nodos que contienen el elemento y una referencia. Si almacenamos elementos de gran tamaño no resulta demasiado importante, pero en casos simples (como números) el tamaño requerido por una Linked List puede ser más del doble del requerido por los elementos.
Por tanto, una Linked List resulta adecuada cuando tengamos que añadir elementos al principio o final de la lista (colas y filas) y el acceso a elementos se realice principalmente de forma secuencial. No son adecuadas cuando necesitemos acceder frecuentemente a un elemento por su índice, en cuyo caso resulta más conveniente una solución basada en array o un solución híbrida.
No obstante, existen formas de mejorar el rendimiento de una Linked List. Una de ellas es aplicar un “cache”, es decir, un nodo que apunta a la última posición a la que hemos accedido. Si realizamos una operación en un índice posterior al de cache, la iteración comienza desde el nodo cache, evitando tener que recorrer toda la Linked List.
De esta forma se mejora considerablemente el rendimiento de ciertas operaciones. Por ejemplo, si tenemos que realizar múltiples lecturas o escrituras en un mismo índice, el cache permite que se realicen con O(n).
Otras variantes posibles de una Linked List son una doble linked list en la que cada nodo contiene referencias al nodo anterior y posterior, lo que permite recorrer la Linked List en ambas direcciones, con la desventaja de aumentar el tamaño de cada nodo. O la Jump List, que es una Linked List que dispone de una capa de nodos que permiten un acceso rápido a cualquier elemento, con la desventaja de requerir el doble de nodos para realizar el mapeo.
Implementar una Linked list en Arduino
Aquí tenemos una implementación ligera de una Linked List para ilustrar su funcionamiento básico.
Por un lado, tenemos la definición del nodo como una estructura que contiene el elemento (en este ejemplo un int) y un puntero al siguiente nodo.
Las funciones InsertHead() e InsertTail() insertan un nodo al principio o final de la Linked List, respectivamente. Por su parte, las funciones RemoveHead() y RemoveTail() eliminan el primer o último nodo.
struct node {
int value;
node *next;
};
node *head;
size_t listSize;
// Crea una linkedlist con un único elemento
void createLinkedList(int value)
{
listSize = 1;
head = new node();
head->next = nullptr;
head->value = value;
}
// Añade un elemento al principio de la linkedlist
void insertHead(int value)
{
node* newHead = new node();
newHead->next = head;
newHead->value = value;
head = newHead;
listSize++;
}
// Añade un elemento al final de la linkedlist
void insertTail(int value)
{
node* newTail = new node();
newTail->next = nullptr;
newTail->value = value;
node *enumerator = head;
for (size_t index = 0; index < listSize - 1; index++)
enumerator = enumerator->next;
enumerator->next = newTail;
listSize++;
}
void removeHead()
{
if(listSize <= 1) return;
node* newHead = head->next;
delete(head);
head = newHead;
listSize--;
}
void removeTail()
{
if(listSize <= 1) return;
node *enumerator = head;
for (size_t index = 0; index < listSize - 2; index++)
enumerator = enumerator->next;
delete enumerator->next;
enumerator->next = nullptr;
listSize--;
}
// Muestra la linkedlist por Serial
void printLinkedList()
{
Serial.print("Size:");
Serial.print(listSize);
Serial.print(" Items:");
node *enumerator;
enumerator = head;
for (size_t index = 0; index < listSize; index++)
{
Serial.print(enumerator->value);
Serial.print(' ');
enumerator = enumerator->next;
}
Serial.println();
}
void setup()
{
Serial.begin(9600);
Serial.println("Lista con elemento 3");
createLinkedList(3);
printLinkedList();
Serial.println();
Serial.println("Añadir 4 y 5 al final");
insertTail(4);
insertTail(5);
printLinkedList();
Serial.println();
Serial.println("Añadir 1 y 2 al principio");
insertHead(2);
insertHead(1);
printLinkedList();
Serial.println();
Serial.println("Eliminar 1 y 5");
removeHead();
removeTail();
printLinkedList();
}
void loop()
{
}Si ejecutamos este código el resultado es el siguiente.
Linked List en una librería
Como es costumbre, esto no se puede quedar así. Aquí tenéis la librería LinkedList, que implementa una Linked List completa en Arduino.
Esta librería permite almacenar cualquier tipo de objetos, tiene métodos para añadir, insertar y eliminar cualquier nodo, y cache para mejorar la eficiencia. ¡A disfrutar!
Descarga el código
Todo el código de esta entrada está disponible para su descarga en Github. 